题意简述
给你一个长为 $n$ 的 AB
字符串。假设一个球从某一个方向(左或右)到达了一个 A
,该位置将变为 B
且该球会反弹;到达了一个 B
,该位置将变为 A
且该球会穿过该位置。
现在从字符串的最左边扔进去 $k$ 个球,每个球都在上一个球已经弹出字符串之后再放入(可以证明,任何字符串都不能把球永远留在字符串中)。
求最后的字符串。
$1\le n\le 200000, 1\le k\le 10^9$ 。
主要思路
$k$ 这么大,说明最后的复杂度和 $k$ 没大关系。
发现如果扔进去球的时候第一个位置是 A
,则球从左边弹出,只改变第一个位置的值;否则,必然从右边弹出。
考虑球从某个位置的右边弹出时,原先在的位置和弹到的位置的值(注意到弹出时该位置必定为 A
)。
AA
变为BA
;AB
变为AA
;
发现第二个位置的值取反即为最后第一个位置的值。
加以分析,即可得若球从字符串右边弹出,新字符串为原字符串左移一位每位取反后,最后一位补上 A
。
这样就得到了一个 $O(n + k)$ 的做法。
由于球从字符串右边弹出后,字符串最后一位必为 A
,所以球从字符串右边弹出若干次后,字符串有后缀 ...ABABA
。扔入足够多的球后,长度为偶数的字符串将变为 BABA...BABA
并保持稳定;长度为奇数的字符串将在 ABAB...BABA
与 BBAB...BABA
中反复。
显然,扔入两个球后至少有一个是从右边弹出的,故若 $k > 2n$ ,可以直接利用上面的结论得到答案。
这样就得到了 $O(n)$ 做法。
参考代码
1 |
|