AtCoder Beginner Contest 207

2023-12-28 21:08:34

A
排序后模拟即可。

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 20000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int a[3];
int main(){
	scanf("%d%d%d",&a[0],&a[1],&a[2]);sort(a,a+3);printf("%d\n",a[2]+a[1]);
}

B
设\(t\)为次数，那么就是要求最小的\(t\)使得\(A+Bt\leq CDt\)
移项得到\(t(CD-B)\geq A\)
此时如果\(CD\leq B\)显然无解，否则上取整即可。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 20000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
ll A,B,C,D;
int main(){
	scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
	if(C*D-B<=0)printf("-1\n");
	else printf("%lld\n",(ll)ceil(A*1.0/(C*D-B)));
}

[C](https://atcoder.jp/contests/abc207/tasks/abc207_c）
我们可以将开区间设为减去\(eps\)的闭区间。
那么暴力枚举判断即可。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 2000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,m,ans,t;db A[N+5],B[N+5];
int main(){
	re int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%lf%lf",&t,&A[i],&B[i]),(t==2)&&(B[i]-=eps),(t==3)&&(A[i]+=eps),(t==4)&&(B[i]-=eps,A[i]+=eps);
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++) ans+=(max(A[i],A[j])<=min(B[i],B[j]));
	}printf("%d\n",ans);
}

D
我这道题解法大概不是正解。
首先考虑两个点集怎么判断是否匹配。
我们将两个点集按照\(x\)排序，相同按\(y\)排序，然后一一对应看看是不是都小于\(eps\)即可。
然后我们枚举\(i\)每次让\(i\)加上一个小的弧度，然后旋转出第一个点集然后用上面的方法判断即可。
调一下参就能过去。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 100
#define mod 1000000007
#define eps (1e-5)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,A[N+5],B[N+5],flag;db nowx,nowy;
struct point{db A,B;}S[N+5],C[N+5];I bool cmp(point x,point y){return x.A==y.A?(x.B<y.B):(x.A<y.A);}
int main(){
	freopen("1.in","r",stdin);
	re int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]);for(i=1;i<=n;i++) scanf("%lf%lf",&C[i].A,&C[i].B);sort(C+1,C+n+1,cmp);
	for(db i=0;i<=360;i+=(5e-4)){nowx=cos(i);nowy=sin(i);
		for(j=1;j<=n;j++) S[j].A=A[j]*nowx-B[j]*nowy,S[j].B=A[j]*nowy+B[j]*nowx;sort(S+1,S+n+1,cmp);
		flag=0;nowx=S[1].A-C[1].A;nowy=S[1].B-C[1].B;for(j=2;j<=n;j++) if(abs(S[j].A-C[j].A-nowx)>eps||abs(S[j].B-C[j].B-nowy)>eps){flag=1;break;} 
		if(!flag){printf("Yes\n");return 0;}
	}printf("No\n");
}

E
这道题大概是这场比赛中最妙的题目。
首先我们设\(dp_{i,j}\)表示到了第\(i\)个，已经划分了\(j\)段，暴力枚举前面看看能不能转移，这个是\(O(n^3)\)的。
考虑换一个枚举顺序，首先枚举\(j\)，再枚举\(i\)，一个区间\([l,r]\)能够被整除的充要条件是\(Sum_{l-1}\equiv Sum_{r}\pmod j\)
那么我们可以对于同余记录，这样就可以\(O(n^2)\)转移了。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 3000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n;ll A[N+5],dp[N+5][N+5],Sum[N+5],G[N+5],Ans;
int main(){
	freopen("1.in","r",stdin);
	re int i,j;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lld",&A[i]),Sum[i]=Sum[i-1]+A[i];
	for(i=1;i<=n;i++){
		memset(G,0,sizeof(G));if(i==1)G[0]=1;for(j=1;j<=n;j++)
		dp[j][i]=G[Sum[j]%i],G[Sum[j]%i]=(dp[j][i-1]+G[Sum[j]%i])%mod; 
	}
	for(i=1;i<=n;i++)Ans+=dp[n][i];printf("%lld\n",Ans%mod);
}

F
看到这种题容易想到树形dp
设\(dp_{i,j,0/1/2}\)表示\(i\)子树内有\(j\)个被覆盖到且当前点未被选择且不受子树影响/已被选择/未被选择但受子树影响
然后随便转移。注意实现的细节使得这个复杂度是\(O(n^2)\)的。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 3000
#define mod 1000000007
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
using namespace std;
int n,x,y,siz[N+5],in[N+5];ll dp[N+5][N+5][3];
struct yyy{int to,z;};
struct ljb{int head,h[N+5];yyy f[N+5<<1];I void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;}}s;
I void dfs(int x,int last){
	siz[x]=dp[x][0][0]=dp[x][1][1]=1;yyy tmp;re int i,j,h;for(i=s.h[x];i;i=tmp.z){
		tmp=s.f[i];if(tmp.to==last) continue;dfs(tmp.to,x);for(j=0;j<=siz[tmp.to];j++) dp[tmp.to][j][0]%=mod,dp[tmp.to][j][1]%=mod,dp[tmp.to][j][2]%=mod;;
		for(j=siz[x];~j;j--){dp[x][j][0]%=mod;dp[x][j][1]%=mod;dp[x][j][2]%=mod;
			for(h=siz[tmp.to];~h;h--){
				if(h)dp[x][j+h][0]+=dp[x][j][0]*(dp[tmp.to][h][0]+dp[tmp.to][h][2])%mod;
				if(h)dp[x][j+h][1]+=dp[x][j][1]*(dp[tmp.to][h][1]+dp[tmp.to][h][2])%mod;
				dp[x][j+h+1][1]+=dp[x][j][1]*dp[tmp.to][h][0]%mod;
				if(h)dp[x][j+h][2]+=dp[x][j][2]*(dp[tmp.to][h][1]+dp[tmp.to][h][0]+dp[tmp.to][h][2])%mod;
				dp[x][j+h+1][2]+=(dp[x][j][0]*dp[tmp.to][h][1])%mod;
			}dp[x][j][1]=0;
		} siz[x]+=siz[tmp.to];
	}
}
int main(){
	freopen("1.in","r",stdin);
	re int i;scanf("%d",&n);for(i=1;i<n;i++) scanf("%d%d",&x,&y),s.add(x,y),s.add(y,x),in[x]++,in[y]++;
	dfs(1,0);for(i=0;i<=n;i++) printf("%lld\n",(dp[1][i][0]+dp[1][i][1]+dp[1][i][2])%mod);
}
上一篇：AtCoder Beginner Contest 206（Sponsored by Panasonic）（补题）


下一篇：AtCoder Beginner Contest 207 E - Mod i (dp,优化)