[??记录]AT2340 [AGC011D] Half Reflector
command_block
·
·
个人记录
题意 ： 有一排 n 个机器，每个机器为两种状态之一 ：
每与球互动一次，机器的状态就会改变。
现在从左侧投入一个球，等待直到球从左侧或者右侧离开。可以证明球一定会离开。
重复投 k 次，问最终机器的状态。
------------
好毒啊，脑补要累死啦……写个暴力观察一下规律。
可以发现，从左侧投入一个球时，机器的改变分为两种情况 ：
- 最左侧是 $A$ ： 最左侧变为 $B$。
- 最左侧不是 $A$ ：整个序列取反后，向左循环移位一次。
不难写出一个 $O(k)$ 的模拟。
继续观察规律，当不断投球时， 形如 `...BABA` 的后缀不会被改变。
最终会稳定在 `BABABA` 或者 `xBABA` （第一位反复横跳）
而且，每投至多两次球，必然会在后方多产生一组 `BA`。
所以我们只需模拟 $2n$ 轮，之后的行为是容易预测的。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 200500
using namespace std;
int n,k;
char s[MaxN];
int main()
{
scanf("%d%d%s",&n,&k,s+1);
for (int i=1;i<=n;i++)s[i]-='A';
if (n&1)k=min(k,2*n+(k&1));
else k=min(k,2*n);
int p=1,fl=0;
while(k--){
if (s[p]^fl){
p=p%n+1;
fl^=1;
}else s[p]=fl^1;
}for (int i=1;i<=n;i++)s[i]=(s[i]^fl)+'A';
for (int i=p;i<=n;i++)putchar(s[i]);
for (int i=1;i<p;i++)putchar(s[i]);
return 0;
}
```