题解

思路

先利用颜色数量判断具有额外行动资源的一方；数量相等时，游戏分解为若干互不影响的最大交替段，并用 Sprague–Grundy 异或判断胜负。

做法

子任务 1：原游戏记忆化搜索

用两个位集记录尚未变白的红格和蓝格，再记录当前行动者。枚举当前玩家所有合法相邻对，递归判断是否存在一步使对手必败。这直接实现了题目定义。

颜色数量不等

每一步只会消除当前玩家颜色的一个或两个格子。可以证明颜色较多的一方总能保持至少一次额外合法行动：红格多则 Alice 获胜，蓝格多则 Bob 获胜。

数量相等时的 SG 分解

把字符串分为极大的相邻字符交替段。一个长度为 $x$ 的交替段中，选择相邻两格后会留下长度为 $j$ 与 $x-2-j$ 的两个独立交替段，所以

$$g[x]=\operatorname{mex}\{g[j]\mathbin{\mathrm{xor}}g[x-2-j]\mid0\le j\le x-2\}.$$

全局 SG 值是所有最大交替段 $g[\text{len}]$ 的异或。非零时先手 Alice 获胜，否则 Bob 获胜。

子任务 2：显式 SG 递推

直接用上式计算 $g[1],\ldots,g[n]$，再扫描字符串求异或。预处理复杂度为 $O(n^2)$。

子任务 3：周期优化

计算前 $1000$ 项后可验证，对所有 $x>1000$ 都有

$$g[x]=g[x-34].$$

因此只需显式计算前 $1000$ 项，其余按周期取值，之后线性扫描每个字符串。

正确性证明

引理 1 红蓝数量不等时，数量较多颜色对应的玩家获胜。

证明：双方每次行动都必须消耗至少一个自己的颜色，而一次操作至多额外消耗一个对方颜色。数量较多的一方可用配对回应保持行动资源，最终拥有额外一步。

引理 2 数量相等时，每个最大交替段是一个独立的无偏子游戏，其 SG 转移为题解中的 mex 式。

证明：交替段中的任意相邻对同时含红蓝两色，双方都可选择；删除后左右两段之间被白格隔开，后续操作互不影响。枚举删除位置即得到两个子段长度。

引理 3 数量相等时，Alice 获胜当且仅当所有交替段 SG 值异或非零。

证明：由引理 2 和 Sprague–Grundy 定理，独立子游戏之和的 SG 值为各段异或，非零局面先手必胜。

定理 算法输出正确赢家。

证明：颜色数量不等时由引理 1；相等时由引理 3。两种情况覆盖全部输入。

复杂度

子任务 1 的状态数为 $O(3^n)$。子任务 2 时间复杂度为 $O(n^2+\sum n)$。满分算法时间复杂度为 $O(1000^2+\sum n)$，空间复杂度为 $O(\max n)$。