[ARC151C] 01 Game 题解

qzhwlzy · 2023-03-07 20:33:47 · 题解

题目大意

有 n 个格子，第 i 与 i+1 相邻。初始 m 个格子里有 0 或 1，Takahashi 和 Aoki 轮流在没数字的格子里填 0 或 1，要保证相邻格子的数字不同，求谁赢。

思路

发现整个游戏被若干已存在的棋子分割成为若干个子游戏，考虑分别计算子游戏的 SG 值并计算异或和。

一个子游戏有且仅有四种情况。分别设 f_1(n),f_2(n),f_3(n),f_4(n) 表示长度为 n 的两端都没有、只有一端有、两端相同和两端不同的子游戏，则（注意 f_3(0) 无意义，\oplus 表示异或运算）：

\begin{cases} f_1(n) = \operatorname{mex}_{i=1}^n(f_2(i-1)\oplus f_2(n-i))\\ f_2(n) = \operatorname{mex}_{i=1}^n(f_2(i-1)\oplus f_3(n-i),f_2(i-1)\oplus f_4(n-i))\\ f_3(n) = \operatorname{mex}_{i=1}^n(f_3(i-1)\oplus f_3(n-i),f_4(i-1)\oplus f_4(n-i))\\ f_4(n) = \operatorname{mex}_{i=1}^n(f_3(i-1)\oplus f_4(n-i),f_4(i-1)\oplus f_3(n-i))\\ \end{cases}

打表：

得到：\begin{cases}f_1(n) = n\bmod 2\\f_2(n) = n\\f_3(n) = 1\\f_4(n) = 0\end{cases}。考虑用归纳法证明：显然 n = 0,1 时成立。假如 0\sim n-1 时均成立，那么：

对于 f_1(n) = \operatorname{mex}_{i=1}^n((i-1)\oplus(n-i))：在 n 为奇数时，存在 i = \dfrac{n+1}{2} 使得 (i-1)\oplus(n-i) = \dfrac{n-1}{2}\oplus\dfrac{n-1}{2} = 0，且不存在 i 使得 (i-1)\oplus(n-i) = 1（假设存在，有 \begin{cases}(i-1) + (n-i) = n-1\\(i-1)\oplus(n-i) = 1\end{cases}，得到 n-1 为奇数，矛盾），故此时 f_1(n) = 1；在 n 为偶数时，同理不存在 i 使得(i-1)\oplus(n-i) = 0（假设存在，有 \begin{cases}(i-1) + (n-i) = n-1\\(i-1)\oplus(n-i) = 0\end{cases}，得到 n-1 为偶数，矛盾），故此时 f_1(n) = 0。
对于 f_2(n) = \operatorname{mex}_{i=1}^n((i-1)\oplus 1,(i-1)\oplus 0)：后者刚好取遍 0\sim n-1，又因为前者不可能等于 n（只有 n 为奇数且 i=n 时会等于，但是此时 f_3(n-i) 无意义），所以 f_2(n) = n。
对于 f_3(n) = \operatorname{mex}_{i=1}^n(1\oplus 1,0\oplus 0) = 1；
对于 f_4(n) = \operatorname{mex}_{i=1}^n(1\oplus 0,0\oplus 1) = 0。

得证。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,m,pos,col,lascol,sgs;
int main(){
    scanf("%lld%lld",&n,&m);
    if(m==0){if(n&1) printf("Takahashi"); else printf("Aoki"); return 0;} // 特判 m=0 的情况 
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&pos,&col);
        if(i==1) sgs=pos-1; else sgs^=(col==lascol);
        if(i==m) sgs^=n-pos; lascol=col; // 首尾两段的 SG 为长度，中间的为两端点是否相同 
    } if(sgs==0) printf("Aoki"); else printf("Takahashi");
    return 0;
}