Codeforces Round 868 (Div. 2)
A. A-characteristic
int fac[N]; map<int,int>mp; void init(){ fac[1]=0; mp[0]=1; for(int i=2;i<N;i++){ fac[i]=fac[i-1]+(i-1); mp[fac[i]]=i; } } void solve(){ int n=read(),k=read(),ans=-1; for(int i=0;i<=n;i++){ if(fac[i]+fac[n-i]==k){ ans=i; break; } } puts(ans!=-1?"YES":"NO"); if(ans!=-1){ for(int i=1;i<=ans;i++){ cout<<1<<" "; } for(int i=1;i<=n-ans;i++){ cout<<-1<<" "; } cout<<'\n'; } }
B. Sort with Step
int a[N]; void solve(){ int n=read(),k=read(); int cnt=0; for(int i=1;i<=n;i++){ a[i]=read(); if(abs(a[i]-i)%k)cnt++; } if(cnt==0)cout<<0<<'\n'; else if(cnt==2)cout<<1<<'\n'; else cout<<-1<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
C. Strongly Composite
map<int ,int >mp; void divide(int x){ for (int i = 2; i <= x / i; i ++ ) if (x % i == 0){ int s = 0; while (x % i == 0) x /= i, s ++ ; mp[i]+=s; } if (x > 1) mp[x]++; } void solve(){ mp.clear(); int n=read(); for(int i=1;i<=n;i++){ int x=read(); divide(x); } int ans=0,sig=0; for(auto i=mp.begin();i!=mp.end();i++){ ans+=i->second/2; sig+=i->second%2; } if(ans<=0&&sig<3)cout<<0<<'\n'; else cout<<ans+sig/3<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
D. Unique Palindromes
字符串构造题 主要抓住一个k的值很小 小于字母数量
首先明确一点 n个位置可以构成最多n个回文字串 例如n个a就可以完成n个回文字串
先构造一个“xyz”,如果后来需要新的回文字串就用重复的字母解决,在后面补上xyz
注意,补位的xyz也需要按顺序计数输出 否则过不了题中的倒数第二个样例
int x[N],c[N]; void solve(){ int n=read(),q=read(); for(int i=1;i<=q;i++){ x[i]=read(); } for(int i=1;i<=q;i++){ c[i]=read(); } string s="xyz"; int now=0; x[0]=3;c[0]=3; x[q+1]=n;c[q+1]=c[q]; for(int i=1;i<=q+1;i++){ int len=x[i]-x[i-1]; int par=c[i]-c[i-1]; if(len<par){ cout<<"NO\n"; return ; }else { s+=string(par,'a'-1+i); for(int i=1;i<=len-par;i++){ s+=s[now]; now=(now+1)%3; } } } cout<<"YES\n"; cout<<s<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
标签:868,No,int,void,Codeforces,read,ans,Div From: https://www.cnblogs.com/edgrass/p/17410497.html