AtCoder Beginner Contest 210

本文主要是介绍AtCoder Beginner Contest 210，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A
这个东西随便特判一下就好了。
code:

using namespace std;
int n,m,a,x,y;
int main(){
	freopen("1.in","r",stdin);
	re int i;scanf("%d%d%d%d",&n,&a,&x,&y);if(n<=a) printf("%d\n",n*x);
	else printf("%d\n",a*x+(n-a)*y);
} 

B
按照题目意思模拟一下就好了。
我看这题时我都开始质疑自己的英语阅读水平了，连WA三发。
code:

using namespace std;
int n,now;char s[N+5];
int main(){
	freopen("1.in","r",stdin);
	re int i;scanf("%d",&n);scanf("%s",s+1);for(i=1;i<=n;i++)if(s[i]=='1'){now=i;break;}
	printf("%s\n",now&1?"Takahashi":"Aoki");
} 

C
开个map随便维护一下增量即可。
code:

using namespace std;
int n,k,A[N+5],cnt,ans;map<int,int> F;
I void insert(int x){!F[x]&&(cnt++);F[x]++;}
I void del(int x){F[x]--;!F[x]&&(cnt--);}
int main(){
	freopen("1.in","r",stdin);
	re int i;scanf("%d%d",&n,&k);for(i=1;i<=n;i++)scanf("%d",&A[i]);
	for(i=1;i<=k;i++) insert(A[i]);ans=max(ans,cnt);for(i=2;i<=n-k+1;i++) del(A[i-1]),insert(A[i+k-1]),ans=max(ans,cnt);printf("%d\n",ans);
}

D
这个绝对值很烦所以把它拆了，我们枚举\(i\)更大的点去找\(i\)小的点所以只有\(2\)种情况。
然后随便搞搞，处理什么二维前缀min即可。
code:

int n,m,x,y,z;ll Ans=1e18,Maxn[N+5][N+5],A[N+5][N+5],k;
int main(){
	freopen("1.in","r",stdin);
	re int i,j;scanf("%d%d%lld",&n,&m,&k);for(i=1;i<=n;i++) for(j=1;j<=m;j++)scanf("%lld",&A[i][j]);
	Me(Maxn,0x3f);for(i=1;i<=n;i++)for(j=1;j<=m;j++) Maxn[i][j]=min(min(Maxn[i-1][j],Maxn[i][j-1]),A[i][j]-k*(i+j));
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++) Ans=min(Ans,A[i][j]+k*(i+j)+min(Maxn[i][j-1],Maxn[i-1][j]));
	}
	Me(Maxn,0x3f);for(i=1;i<=n;i++)for(j=m;j;j--) Maxn[i][j]=min(min(Maxn[i-1][j],Maxn[i][j+1]),A[i][j]-k*i+k*j);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++) Ans=min(Ans,A[i][j]+k*i-k*j+min(Maxn[i-1][j],Maxn[i][j+1]));
	}printf("%lld\n",Ans);
}

E
我真是太屑了一眼没看出来。
首先肯定先按\(C\)排序。
考虑第一个\(A_i\)如果和\(n\)互质那么形成生成树直接输出即可。
否则会形成\(gcd(A_i,n)\)个连通块。
然后我们将每个连通块看作一个点那么就可以直接继续处理下面的子问题了。
code:

using namespace std;
int m,k; ll n,Ans,now;
struct ques{ll A,C;}S[N+5];I bool cmp(ques x,ques y){return x.C<y.C;}
int main(){
	freopen("1.in","r",stdin); 
	re int i;scanf("%lld%d",&n,&m);for(i=1;i<=m;i++) scanf("%lld%lld",&S[i].A,&S[i].C);sort(S+1,S+m+1,cmp);
	for(i=1;i<=m;i++){
		now=__gcd(n,S[i].A);if(now==1){printf("%lld\n",Ans+1ll*(n-1)*S[i].C);return 0;}
		Ans+=1ll*(n-now)*S[i].C;n=now;
	}printf("-1\n");
}

F
我觉得这道题很板子。
首先每个牌有两个状态:正面和反面，容易想到2-sat。
然后这样的话如果有两个数是不互质的就不能共存。
这样暴力建边是\(O(n^2)\)的。
考虑将每个数分解质因数然后扔到对应的vector中，然后对于每个vector中的点肯定要不共存。
这个东西做的多的就是一个前缀优化建边板子，随便写写，时间复杂度\(O(nlogW+W)\)
code:

using namespace std;
int n,m,k,x,y,z,cnt,dfn[N+5],dh,scc[N+5],A[N+5],B[N+5],low[N+5],st[N+5],sh,vis[N+5],now,pus,Maxn,cnts;
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;/*printf("%d %d\n",x,y);*/}
}s;
I void tarjan(int x){
	vis[x]=1;dfn[x]=low[x]=++dh;st[++sh]=x;yyy tmp;for(int i=s.h[x];i;i=tmp.z){
		tmp=s.f[i];if(!dfn[tmp.to]) tarjan(tmp.to),low[x]=min(low[x],low[tmp.to]);
		else vis[tmp.to]&&(low[x]=min(low[tmp.to],low[x]));
	}
	if(low[x]==dfn[x]){++cnts;while(st[sh+1]^x) scc[st[sh]]=cnts,vis[st[sh--]]=0;}
}
int pr[N+5],ph,fl[N+5],las[N+5],D[N+5],C[N+5],To[N+5];vector<int> G[N+5];
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]),Maxn=max(Maxn,max(A[i],B[i]));cnt=2*n;for(i=1;i<=n;i++) To[i]=i+n;for(i=n+1;i<=2*n;i++) To[i]=i-n;
	for(i=2;i<=Maxn;i++){
		!fl[i]&&(pr[++ph]=i,las[i]=i);for(j=1;j<=ph&&pr[j]*i<=Maxn;j++){
			fl[pr[j]*i]=1;las[pr[j]*i]=pr[j];if(i%pr[j]==0) break;
		}
	}
	for(i=1;i<=n;i++){
		now=A[i];while(now^1) {
			pus=las[now];G[las[now]].push_back(i);while(now%pus==0) now/=pus;
		}
		now=B[i];while(now^1) {
			pus=las[now];G[las[now]].push_back(i+n);while(now%pus==0) now/=pus;
		}
	}
	for(i=1;i<=Maxn;i++){
		for(j=0;j<G[i].size();j++) D[j]=++cnt,C[j]=++cnt,s.add(G[i][j],D[j]),s.add(C[j],To[G[i][j]]);
		for(j=1;j<G[i].size();j++) s.add(D[j-1],D[j]),s.add(C[j],C[j-1]);
		for(j=1;j<G[i].size();j++) s.add(D[j-1],To[G[i][j]]),s.add(G[i][j],C[j-1]);
    }//return 0;
	for(i=1;i<=cnt;i++) !dfn[i]&&(tarjan(i),0);for(i=1;i<=n;i++) if(scc[i]==scc[i+n]){printf("No\n");return 0;}printf("Yes\n");
}

这篇关于AtCoder Beginner Contest 210的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！