比赛链接:https://codeforces.ml/contest/1672
讲真的,做的挺拉的。A题没读懂,看了题解。BC 每个题都WA了好几次。D题直接看答案了
A题:大意是现有数组a,errorgorn和maomao90分别先后轮流将数组a中的某个元素拆分成两个不小于1的数并加入到数组a中,最终不能再拆分的人为败者。问给定的数组a的情况下,胜者是谁。
反正脑瘫了没读懂,不知道是翻译问题还是我的理解问题。读懂了就很简单了。可分的情况就那么多ai-1呗
code:
void solve() { int n; cin>>n; int x; int ans = 0; for(int i=1;i<=n;i++){ cin>>x; ans+=x-1; } if(ans%2==1) cout<<"errorgorn"<<endl; else cout<<"maomao90"<<endl; }
B题:大意是给出一个空串。你可以往里面任意添加任意好串,好串类似AB,AAB,AAAB。特判一下小于2和末尾B。然后分别记录两个的数量,在某一位置a的数量小于b的数量就no
code:
void solve() { string s; cin>>s; if(s.size()<2||s[s.size()-1]!='B'){ cno; return; } int cnta = 0,cntb = 0; for(int i=0;i<s.size();i++){ if(s[i]=='A') cnta++; else cntb++; if(cnta<cntb){ cno; return; } } cyes; }
C题:大意是给出一堆数,求至少多少次可以使得ai = a[i+1]的次数小于等于1,每次改变使得ai和ai+1变成某一个数。
很简单的一个题,直接去找一下最开始的和最末尾的,中间的数量就是次数。如果l和r相同那么一次,如果l>r,那么0次。否则中间次数。
code:
void solve() { int n; cin>>n; int cnt = 1; bool flag = false; for(int i=1;i<=n;i++){ cin>>a[i]; } int ans = 0; int p = 1; while(a[p]!=a[p+1]&&p<n) p++; int l = p+1; p = n; while(a[p]!=a[p-1]&&p>=0) p--; int r = p-1; if(l>r) ans = 0; else if(l==r) ans = 1; else ans = r-l; cout<<ans<<endl; }
D题:大意是给出长度为n的数组a和数组b,每次可以选择两个相同的数的下标l和r,令l-r内的数全部都左移一位,同时在r的位置记录al的值。求是否可以通过有限次的移动来使得数组a变为数组b。
解决方法:考虑使用双指针做法,每次i和j指到相同的数,那么继续往后找。否则我们先看b数组中和前一个数是否一样,如果一个就可以将这个数移动到前面的任意位置,使得j继续往后走。如果抵消不了,那么我们就需要a数组继续往后找,看看有没有能够抵消掉bj上的元素。
code:
void solve() { int n; cin>>n; for(int i=1;i<=n+1;i++) cnt[i] = 0; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; bool flag = true; int i=1,j=1; while(j<=n){ if(i<=n&&j<=n&&a[i]==b[j]){ i++;j++; continue; } if(cnt[b[j]]>0&&b[j]==b[j-1]){//先想办法抵消 cnt[b[j++]]--; }else if(i<=n){//抵消不了我们就从i中找,让i往后想办法 cnt[a[i++]]++; }else{ flag = false; break; } } if(flag){ assert(i==n+1); for(int i=1;i<=n;i++){ assert(cnt[i]==0); } cyes; } else cno; }