제5 회 산동 ACM 대회 총결산
단순 포인트:
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2877
주어진 곡선 은 하나의 점 을 정 하고 곡선 상의 특정한 점 에서 x 축 상의 특정한 직선 이 바로 곡선 접선 과 곡선 으로 둘러싸 인 면적 을 구한다.
물 문제, 포 인 트 를 구 해서 풀 면 되 는데 시작 이 틀 렸 어 요. 리 턴 을 PR 이 아니 라 WR 로 판 단 했 어 요. 첫 번 째 문제 가 끊 겨 서 취 했 어 요...
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 100005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
using namespace std;
int main()
{
double a,b,du;
double T,P;
int xx,yy;
int n;
rd(n);
while(n--)
{
rd2(xx,yy);
T=yy,P=xx;
scanf("%lf",&du);
b=tan(du);
a=b*P/(T*T-2*T*P);
double y0=a*T*T+b*T;
double area = 1/3.0*a*T*T*T+1/2.0*b*T*T + 1/2.0*(P-T)*y0;
//cout<<a<<' ' <<y0<<endl;
printf("%.3f
",area);
}
return 0;
}B.Circle
가우스 소원
n 개 수 는 하나의 원 으로 둘러싸 고 번호 0 ~ n - 1 은 하나의 숫자 에서 위의 숫자 와 다음 수의 확률 이 같다 (즉 모두 0.5).n. 0 에서 출발 하여 x 에 필요 한 걸음 수 에 도달 하 기 를 바 라 는 수학 적 기 대 를 드 립 니 다.
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2878
어떤 큰 신 이 소수 에서 규칙 을 찾 았 다.
d[0]=0,d[1]=n-1,d[2]=(n-1)+(n-3),d[3]=(n-1)+(n-3)+(n-5),……。
이렇게 하면 밀어 줄 수 있다.
그러나 이 문 제 는 정 해 가 고 스 소원 인 것 같 지만 성 경기 와 같은 약간 물 점, 특히 수학 과 관련 된 느낌 을 전달 하 는 방식 으로 해 보면 몇 개 를 열거 하면 규칙 을 찾 을 수 있 을 것 이다. 이런 방법 은 바보 처럼 보이 지만 작용 이 비교적 클 때 가 있다 는 것 을 명심 하 라.
고 스 소원 의 방법 을 보충 해서...이 짧 은 코드 를 보고 순간 전달 규칙 이 매 달 려 있 는 것 같 아 요.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 100005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
using namespace std;
int main()
{
int T,x,n;
rd(T);
int dp[1005];
dp[0]=0;
while(T--)
{
rd2(n,x);
for(int i=1,j=1;i<=x;i++,j+=2)
dp[i]=dp[i-1]+(n-j);
printf("%.4f
",(float)dp[x]);
}
return 0;
}C.Colorful Cupcakes
질문
제목 사이트 주소:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2879
ABC 세 가지 색상 의 개 수 를 알려 주 고 인접 색상 이 다 르 고 수미 색상 이 다른 문자열 의 개 수 를 구하 십시오.
생각:
처음에는 검색 이 라 고 생각 했 지만 간단 한 검색 은 시간 을 초과 할 것 이 라 고 생각 했 습 니 다. dp 는 전달 공식 도 찾 지 못 하고 기억 화 된 검색 을 잊 게 만 들 었 습 니 다. 슬 펐 습 니 다.dp [i] [a] [b] [k] 는 앞의 i 위치 A 에 a 개 B 가 b 개 있 고 현재 위치 색 은 k 의 개 수 를 나타 낸다.현재 색상 이 빨간색 이 라 고 가정 하면 0 (스스로 정 함) 입 니 다. dp[i][a][b][k]=∑dp[i−1][a−1][b][ii], ii = 1,2,3. ii != k, ii 는 이전 위치의 색상 으로 k 와 같 을 수 없습니다.
뒤에서 앞으로 수색 하 다.
#include <stack>
#include <cstdio>
#include <list>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <cmath>
using namespace std;
const int MAXN = 50 + 3;
const int MOD = 1e9 + 7;
char str[100];
int cnt[3];
int dp[MAXN][MAXN][MAXN][3];
int lastColor ;
///
int DFS(int pre, int a, int b, int k)/// pre a A b ， k
{
if (dp[pre][a][b][k] != -1) return dp[pre][a][b][k];
if (a < 0 || b < 0 || pre-a-b < 0) return 0;
if (pre == 1 && k == lastColor) return 0; /// ，0
if (pre == 1) return dp[pre][a][b][k] = ((a && k == 0) || (b && k == 1) || (pre-a-b && k == 2));
/// ， 。
///
int ans = 0;
for (int ii = 0; ii < 3; ii++) ///
{
if (k == ii) continue;
if (k == 0) ans = (ans + DFS(pre-1, a-1, b, ii)) % MOD;
if (k == 1) ans = (ans + DFS(pre-1, a, b-1, ii)) % MOD;
if (k == 2) ans = (ans + DFS(pre-1, a, b, ii)) % MOD;
}
return dp[pre][a][b][k] = ans;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", str);
memset(dp,-1,sizeof(dp));
memset(cnt,0,sizeof(cnt));
int len = strlen(str);
for (int i = 0; i < len; i++)
cnt[str[i]-'A']++;
int ans = 0;
for (int i = 0; i < 3; i++) ///
{
memset(dp,-1,sizeof(dp));
lastColor=i;
ans = (ans + DFS(len, cnt[0], cnt[1], i)) % MOD;
for(int i=1;i<=len;i++)
for(int j=1;j<=len;j++)
for(int x=1;x+j<=len;x++)
for(int k=0;k<3;k++)
if(dp[i][j][x][k]!=-1)
cout<<"dp["<<i<<"]["<<j<<"]["<<x<<"]["<<k<<"]"<<dp[i][j][x][k]<<endl;
}
printf("%d
", ans);
}
return 0;
}
뒤에서 앞으로 쓰 는 것 이 약간 빙빙 도 는 것 같 아서 자신 이 뒤에서 쓰 는 것 을 두 드 렸 는데 대동소이 하 다.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 100005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } };
using namespace std;
const int MAXN = 50 + 3;
const int MOD = 1e9 + 7;
char str[100];
int cnt[3];
int dp[MAXN][MAXN][MAXN][3];
int firstColor,len;
///
int DFS(int pre, int a, int b, int k)/// pre a A b B ，k
{
if ((k==0 && a+1 > cnt[0]) || (k==1 && b+1 > cnt[1]) || (k==2 && pre-a-b > cnt[2])) return 0;
if (dp[pre][a][b][k] != -1) return dp[pre][a][b][k];
if (pre == len && k == firstColor) return 0; /// ，0
if (pre == len) return ((a+1<=cnt[0] && k == 0) || (b+1<=cnt[1] && k == 1) || (pre-a-b <= cnt[2] && k == 2));
/// ， 。
///
int ans = 0;
for (int ii = 0; ii < 3; ii++) ///
{
if (k == ii) continue;
if (k == 0) ans = (ans + DFS(pre+1, a+1, b, ii)) % MOD;
if (k == 1) ans = (ans + DFS(pre+1, a, b+1, ii)) % MOD;
if (k == 2) ans = (ans + DFS(pre+1, a, b, ii)) % MOD;
}
return dp[pre][a][b][k] = ans;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", str);
memset(dp,-1,sizeof(dp));
memset(cnt,0,sizeof(cnt));
len = strlen(str);
for (int i = 0; i < len; i++)
cnt[str[i]-'A']++;
int ans = 0;
for (int i = 0; i < 3; i++) ///
{
memset(dp,-1,sizeof(dp));
firstColor=i;
ans = (ans + DFS(1, 0, 0, i)) % MOD;
}
printf("%d
", ans);
}
return 0;
}D. Devour Magic
n 개 단위, 각 단위 마다 1 초 에 1 마 나 를 증가 시 키 고, 특정 시간 에 일부 구간 의 마 나 값 (가 져 간 후 이 구간 의 모든 단위 의 마 나 력 이 0 으로 변 함) 을 가 져 가 얻 은 모든 마 나 값 을 구한다.
원래 의 기초 위 에서 제로 작업 을 추 가 했 지만 이 제로 작업 (실제 코드 에서 도 임의의 값 으로 설정 할 수 있 음) 은 flag 로고 와 하나의 sset 변 수 를 통 해 다음 에 설정 할 수 있 는 수 를 저장 합 니 다. 다른 작업 은 정상 적 인 pushdown 과 마찬가지 로 입력 할 때마다 지난번 에 업 데 이 트 된 시간 last 를 기록 합 니 다. 이번 에는 t - last 를 직접 기록 하면 됩 니 다.
이전의 시간 초과 코드 도 여기에 붙 여 놓 으 세 요. (표 시 된 것 은 많이 찾 았 을 수도 있 습 니 다!!!) 하지만 AC 를 제출 한 코드 는 자신의 생각 과 똑 같 습 니 다. 구체 적 으로 지금 은 문제 가 어디 에 있 는 지 모 르 겠 습 니 다.
시간 초과 코드:
///
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define INF 0x3f3f3f3f
#define MAX 1100000
#define LL long long
using namespace std;
LL n,m;
LL coun=0;
int xx;
struct Tree
{
LL l,r;
LL sum,add;
};
Tree tree[MAX*8];
void pushup(LL x) ///
{
tree[x].sum=tree[ x<<1 ].sum+tree[ (x<<1)+1 ].sum;
}
void pushdown(LL x) /// add
{
if(x>xx){
tree[x].sum = 0;
return ;
}
LL tmp = x<<1 ;
if(tree[x].add == -INF){
// cout<<x<<"----------------------"<<endl;
tree[tmp].add = -INF ; ///
tree[tmp+1].add = -INF;
tree[tmp].sum = 0;
tree[tmp+1].sum = 0;
tree[x].add=0;
tree[x].sum=0;
return ;
}
if( tmp > xx ) return ;
if(tree[tmp].add == -INF ) pushdown(tmp);
if(tree[tmp+1].add == -INF) pushdown(tmp+1);
tree[tmp].add += tree[x].add; ///
tree[tmp].sum += tree[x].add*(tree[tmp].r-tree[tmp].l+1);
tree[tmp+1].add += tree[x].add;
tree[tmp+1].sum += tree[x].add*(tree[tmp+1].r-tree[tmp+1].l+1);
if(tmp>xx) cout<<tmp<<" "<<tree[tmp].add<<" "<<tree[tmp].add<<" "<<tree[tmp].l<<" "<<tree[tmp].r<<endl;
tree[x].add=0;
}
void build(int l,int r,int x)
{
tree[x].l=l , tree[x].r=r , tree[x].add=0;
if(l==r)
{
tree[x].sum = 0; ///
tree[x].add = 0;
return ;
}
int tmp=x<<1;
int mid=(l+r)>>1;
build(l,mid,tmp);
build(mid+1,r,tmp+1);
pushup(x); ///
}
void update(LL l,LL r,LL c,LL x) /// ， ， ，
{
if(r<tree[x].l||l>tree[x].r||x>xx) return ;
if(l<=tree[x].l&&r>=tree[x].r) ///
{
// cout<<"************
";
if(c==-INF){
tree[x].add = -INF;
tree[x].sum = 0;
return ;
}
if(x>xx) return ;
if(tree[x].add == -INF ) pushdown(x);
tree[x].add += c ;
tree[x].sum += c*(tree[x].r-tree[x].l+1); /// *
return ;
}
/// ，
if(tree[x].add ) pushdown(x); /// add
LL tmp=x<<1;
if(tmp>xx){
pushup(x);
return ;
}
update(l,r,c,tmp);
update(l,r,c,tmp+1);
}
LL query(LL l,LL r,LL x)
{
///if(r<tree[x].l||l>tree[x].r) return -INF;// （ ）
if(l<=tree[x].l&&r>=tree[x].r) ///
{
return tree[x].sum;
}
if( tree[x].add&&tree[x].add!=-INF ) pushdown(x); /// add ， add
LL tmp=x<<1;
if(tmp>xx) return 0;
LL mid=(tree[x].l+tree[x].r)>>1;
if(r<=mid) return query(l,r,tmp);
else if(l>mid) return query(l,r,tmp+1);
else return query(l,mid,tmp)+query(mid+1,r,tmp+1);
}
int main()
{
int xxx;
scanf("%d",&xxx);
while(xxx--)
{
scanf("%I64d%I64d",&n,&m);
xx=4*n;
coun=0;
build(1,n,1);
LL last=0;
while(m--)
{
LL l,r,time;
scanf("%I64d%I64d%I64d",&time,&l,&r);
update(1,n,time-last,1);
/*
cout<<" "<<time-last<<endl;
for(int i=1;i<=60;i++)
cout<<i<<":"<<tree[i].add<<' '<<tree[i].sum<<" ";
cout<<endl;*/
last = time ;
coun+=query(l,r,1);
update(l,r,-INF,1);
/*
for(int i=1;i<=60;i++)
cout<<i<<":"<<tree[i].add<<' '<<tree[i].sum<<" ";
cout<<endl;*/
}
printf("%I64d
",coun);
}
return 0;
}
/**************************************
Problem id : SDUT OJ 2880
User name :
Result : Time Limit Exceeded
Take Memory : 0K
Take Time : 2010MS
Submit Time : 2016-04-02 09:36:52
**************************************/
AC 코드:
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define L(root) ((root)<<1)
#define R(root) (((root)<<1)|1)
const int MAXN=1e5+10;//
int numbers[MAXN];//
struct node{
int left,right;///
long long sum;
int add;///
int sset; /// v
bool flag;/// v
int mid(){
return ((right+left)>>1);
}
}tree[MAXN*4];//4
void pushUp(int root){
tree[root].sum=tree[L(root)].sum+tree[R(root)].sum;
}
void pushDown(int root){
int L=L(root),R=R(root);
if(tree[root].flag){
tree[L].add=tree[R].add=0;
tree[L].sset=tree[R].sset=tree[root].sset;
tree[L].flag=tree[R].flag=true;
tree[L].sum=tree[root].sset*(tree[L].right-tree[L].left+1);
tree[R].sum=tree[root].sset*(tree[R].right-tree[R].left+1);
tree[root].flag=false;
}
if(tree[root].add){ /// pushdown
tree[L].add+=tree[root].add;
tree[R].add+=tree[root].add;
tree[L].sum+=tree[root].add*(tree[L].right-tree[L].left+1);
tree[R].sum+=tree[root].add*(tree[R].right-tree[R].left+1);
tree[root].add=0;
}
}
void build(int root,int left,int right){
tree[root].left=left;
tree[root].right=right;
tree[root].add=0;
tree[root].flag=false;
if(left==right){
tree[root].sum=numbers[left];
return;
}
int mid=tree[root].mid();
build(L(root),left,mid);
build(R(root),mid+1,right);
pushUp(root);
}
long long query(int root,int left,int right){
if(tree[root].left==left&&tree[root].right==right) return tree[root].sum;
pushDown(root);
int mid=tree[root].mid();
if(right<=mid) return query(L(root),left,right);
else if(left>mid) return query(R(root),left,right);
else return query(L(root),left,mid)+query(R(root),mid+1,right);
}
void update(int root,int left,int right,int add){
if(tree[root].left==left&&tree[root].right==right){
tree[root].add+=add;
tree[root].sum+=add*(right-left+1);
return;
}
pushDown(root);
int mid=tree[root].mid(),L=L(root),R = R(root);
if(right<=mid) update(L,left,right,add);
else if(left>mid) update(R,left,right,add);
else{
update(L,left,mid,add);
update(R,mid+1,right,add);
}
pushUp(root);
}
void setf(int root,int left,int right,int sset){
if(tree[root].left==left&&tree[root].right==right){
tree[root].add=0;
tree[root].sum=sset*(right-left+1);
tree[root].sset=sset;
tree[root].flag=true;
return;
}
pushDown(root);
int mid=tree[root].mid(),L=L(root),R = R(root);
if(right<=mid) setf(L,left,right,sset);
else if(left>mid) setf(R,left,right,sset);
else{
setf(L,left,mid,sset);
setf(R,mid+1,right,sset);
}
pushUp(root);
}
int main(){
memset(numbers,0,sizeof(numbers));
int T;
int n,m;
int t,l,r;
int i;
int lastTime;
long long sum;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
build(1,1,n);
lastTime=0;
sum=0;
for(i=0;i<m;++i){
scanf("%d%d%d",&t,&l,&r);
update(1,1,n,t-lastTime);
sum+=query(1,l,r);
setf(1,l,r,0);//l r 0
lastTime=t;
}
printf("%lld
",sum);
}
return 0;
}
E. Factorial 물 문제, 단계 곱 하기
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 100005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } };
using namespace std;
int main(){
int n,x;
rd(n);
while(n--){
rd(x);
int sum=1;
for(int i=1;i<=x;i++)
sum*=i;
printf("%d
",sum);
}
return 0;
}F. Full Binary Tree
이 진 트 리 에서 두 노드 의 가장 가 까 운 거 리 를 구하 세 요.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 100005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } };
using namespace std;
int main(){
int n,x,y;
rd(n);
while(n--){
rd2(x,y);
int step=0;
while(x!=y){
x>y?x/=2:y/=2;
step++;
}
printf("%d
",step);
}
return 0;
}G. Hearthstone II
n 경기, m 개 장소, m < = n, 1 경기 에서 1 개 장 소 를 선택 할 수 있 습 니 다. 각 장 소 는 반드시 한 번 사용 해 야 하고 모든 방안 수 를 구 해 야 합 니 다.
dp [i] [j] 는 전 i 경기 에서 j 개 코트 의 상황 수 를 사용 했다 고 밝 혔 다.
dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(m-j+1);
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MOD=1e9+7;
int main(){
int n,m;
long long dp[105][105];//dp[i][j] ： i j
int i,j;
while(~scanf("%d%d",&n,&m)){
memset(dp,0,sizeof(dp));
for(i=1;i<=n;++i) //j=1; i 1 ， m
dp[i][1]=m;
for(i=2;i<=n;++i){
for(j=2;j<=i&&j<=m;++j){
dp[i][j]=((dp[i-1][j]*j)%MOD+(dp[i-1][j-1]*(m-j+1))%MOD)%MOD;
}
}
printf("%lld
",dp[n][m]);
}
return 0;
}H.Painting Cottages
I.Tree
J.Weighted Median
단순 정렬
하지만 여기 에는 0.5 를 처리 하 는 작은 기술 이 있 습 니 다. 먼저 2 를 곱 한 다음 에 정수 에 따라 조작 하면 됩 니 다.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define MAX 10000005
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<string,int>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } };
using namespace std;
struct T{
int x;
int w;
}arr[MAX];
bool cmp(T a,T b){
return a.x<b.x;
}
int main(){
int n;
LL sum,temp;
int s;
while(~rd(n)){
sum=0;
temp=0;
for(int i=0;i<n;i++)
rd(arr[i].x);
for(int i=0;i<n;i++)
rd(arr[i].w);
for(int i=0;i<n;i++)
sum+=arr[i].w,arr[i].w=arr[i].w<<1;
sort(arr,arr+n,cmp);
s=arr[0].x;
for(int i=0;i<n,temp<sum;s = arr[i].x,i++)
temp+=arr[i].w;
printf("%d
",s);
}
return 0;
}Factorial
Tree
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
