用 \(1\) 表示 A
,\(0\) 表示 B
,观察进行一次操作后字符串会发生什么变化。首先当第一个数为 \(1\) 时,只会将第一个数变为 \(0\)。对于剩下的情况,手玩一下可以发现会将第一个数移到末尾,然后将所有数异或 \(1\)。
先考虑暴力怎么做,可以记一个指针 \(i\) 和当前应该给全体数异或的值 \(c\)。如果 \(a_i\neq c\),则将 \(a_i\) 改为 \(1\),否则将 \(i\) 往后移一位,\(c\) 取反。发现操作等价从左到右将每个数依次跟 \(i\bmod 2\) 比较,如果不同就改正,最多进行 \(2n\) 次操作后就会进入循环。当 \(n\) 为偶数时循环节长度为 \(1\),奇数长度为 \(2\),将 \(k\) 缩小后暴力操作即可,时间复杂度 \(\mathcal O(n)\)。
参考代码:
#include<bits/stdc++.h>
#define mxn 200003
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
int n,k,c,a[mxn];
char s[mxn];
signed main(){
scanf("%d%d%s",&n,&k,s+1);
rep(i,1,n)a[i]=s[i]=='A'?0:1;
if(!(n&1))k=min(k,n*2);
else if(k>=n*4)k=(k-n*2)%(n*2)+n*2;
int r=1;
rept(i,0,k){
if(a[r]==c)a[r]^=1;
else c^=1,r=r%n+1;
}
rept(i,0,n)putchar((a[r]^c)?'B':'A'),r=r%n+1;
return 0;
}
标签:Reflector,int,题解,AGC011D,rept,异或,Half
From: https://www.cnblogs.com/zifanoi/p/18544061