Codeforces Round #659 (Div. 2)
Common Prefixes （构造）
给出 n 个数 a[i]，输出 n+1 行，使得 第 i 行与第 i+1 行有 a[i] 个相同的字母
const int N=100+5;int n,m,t;int i,j,k;int a[N];
void go()
{for(i=1;i<=n+1;i++){if(i&1) cout<<'a';else cout<<'b';cout<<endl;}
}
int main()
{IOS;rush(){cin>>n;int maxx=0;for(i=1;i<=n;i++) cin>>a[i],maxx=max(maxx,a[i]);a[n+1]=a[n];if(maxx==0){ go(); continue; }string s(maxx,'a');string ans=s;cout<<ans<<endl;char cur='b';for(i=1;i<=n;i++){ans=string{ans.begin(),ans.begin()+a[i]}+string(maxx-a[i],cur);cout<<ans<<endl;if(cur=='z') cur='a';cur++;}}//PAUSE;
}
String Transformation 1 （模拟）
给出两个字符串 a,b，要求每一次操作可以将 a 串中相同的字符 x，全部换成 y，但要求 y>x，最后使得 b=a,求最小操作数
int n,m,t;int i,j,k;int cnt[26][26];int main()
{IOS;rush(){cin>>n;string a,b;cin>>a>>b; bool flag=1;ms(cnt,0);for(i=0;i<n;i++){if(a[i]!=b[i]){if(a[i]<b[i]) cnt[a[i]-'a'][b[i]-'a']++;else flag=0;}}if(flag){int cur,ans=0;for(i=0;i<20;i++){flag=0;for(j=i+1;j<20;j++){if(cnt[i][j]){//找出不同的cur=j;flag=1;break;}}if(flag){ans++;for(j=i+1;j<20;j++){if(cnt[i][j]) cnt[cur][j]=1;}}}cout<<ans<<endl;}else cout<<-1<<endl;}//PAUSE;
}
GameGame （博弈）
有 n 个数，Koa 和另一个人比赛，每个数只能拿一次，两个人手上的值都是 0 ，使得每拿一个数都与自己手上的数进行异或，自己手上的数变成当前异或值，最后谁手上的书最大谁获胜
根据异或的性质，统计所有位上的数字
a 表示当前位上 1 的个数，b 表示当前位上 0 的个数
如果 a 是偶数，无论 b ，这一位上都相同
如果 a 是奇数，
Koa 先拿，现在有 a-1 个 1，为偶数，很容易想到剩余的 1 该如何分
- 若 均分后每个人再分偶数个 即 (a-1)%4=0，也就是说每个人再分到偶数个 1，那么无论 b， Koa 赢
- 若 均分后每个人再分奇数个 即 (a-1)%4=2，那么决定权再对手手里，即通过拿 0 使得 Koa 再拿奇数个 1
- 如果 0 有偶数个，那么 Koa 一定会拿到奇数个 1，一定输
- 如果 0 有奇数个，那么 Koa 通过多拿一个 0 少拿一个 1，使得对手多拿一个 1 ，从而获得胜利
const int N=1e5+5;int n,m,t;int i,j,k;int cnt[32];int a[N];void go()
{for(i=30;i>=0;i--){if(cnt[i]&1){if(cnt[i]%4==1) cout<<"WIN"<<endl;else{if(n&1) cout<<"LOSE";else cout<<"WIN";cout<<endl;}return ;}}cout<<"DRAW"<<endl;
}
int main()
{IOS;rush(){cin>>n;ms(cnt,0);for(i=1;i<=n;i++){cin>>a[i];int tmp=a[i];int cur=0;while(tmp){cnt[cur]+=(tmp&1);cur++;tmp>>=1;}}go();}PAUSE;
}