【AtCoder Grand Contest 011 D】Half Reflector | Mrsrz's blog

模拟，暴力。

题目大意：

有两种机器 A 和 B，一个球碰到 A 后会反方向运动，碰到 B 后会按原来方向运动。碰到机器后这个 A 会变为 B，B 会变为 A。

现在给定一排 $n$ 个机器，并且从左边滚 $k$ 个球过去，问最终这些机器的状态。

题解：

滚一个球进去时，我们考虑这些机器的状态变化。

• 若第一个是 A，则把它变成 B。
• 若第一个不是 A，则我们每次碰到连续一段 A 时，它之前那个一定是从 B 变过来的 A。通过手动模拟可以发现，每一段连续的相同字符，除了最后一个字符以外，其他的状态都会取反。可以看成取反后循环左移一位。

那么我们只需要记录当前取反了多少次（奇偶性），还有当前的第一个机器的位置，就可以 $O(1)$ 完成单次修改。

由于单次修改常数非常小，所以 $O(k)$ 的暴力可以通过。

Code：

#include<cstdio>
int n,k;
char s[200005];
bool v[200005];
int main(){
    scanf("%d%d%s",&n,&k,s);
    for(int i=0;i<n;++i)v[i]=s[i]=='A';
    int cur=0,t=0;
    while(k--)
    if(v[t]^cur)v[t]=cur;else cur^=1,t=(t+1==n)?0:t+1;
    for(int i=0;i<n;++i)
    putchar((v[(i+t)%n]^cur)?'A':'B');
    return 0;
}