[??记录]AT2340 [AGC011D] Half Reflector

**题意** ： 有一排 $n$ 个机器，每个机器为两种状态之一 ： - $\rm A$ : 反弹滚过来的球。 - $\rm B$ : 允许球通过。 每与球互动一次，机器的状态就会改变。 现在从左侧投入一个球，等待直到球从左侧或者右侧离开。可以证明球一定会离开。 重复投 $k$ 次，问最终机器的状态。 $n\leq 2\times 10^5,k\leq 10^9$ ，时限$\texttt{2s}$。 ------------ 好毒啊，脑补要累死啦……写个暴力观察一下规律。 可以发现，从左侧投入一个球时，机器的改变分为两种情况 ： - 最左侧是 $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; } ```