题解：AT_arc225_b [ARC225B] Independent Nim

· · 题解

简单博弈论。

从最简单的情况开始。

对于全 0 的局面，先手必败。

考虑有很多个不相邻的 1。明显的，先手可以全取完以获得胜利。

考虑只有一个长度为 2 的连续 1 段。（比如 00011000。）

容易发现先手必败。

那如果有很多个长度为 2 的连续 1 段呢？（比如 0011001100。）

容易发现，无论先手怎么去，后手要么重新将其变成有很多个相邻的 1 的局面，要么将其变成只有两个相邻的 1，要么取完。

那如果再加入一些互不相邻的 1 呢？

明显，先手可以全取完从而让后手变成上述局面导致必败。

那如果有 3 个，4 个，甚至 114514 个连续的 1 呢？

无论如何，都可以将其化为很多个两个相邻的 1。

下面给出长度为 3,4,5 的转化成若干长度为 2 的连续 1 段的方法：

111\to110 1111\to 0110 11111\to 11011

发现更往上的都可以通过这三种情况拼接而得。

故先手可以操作局面，使后手进入有很多个长度为 2 的连续 1 段的局面从而必败。

总结：当序列全为 0 或有很多个长度为 2 的连续 1 段时后手胜，否则先手胜。

:::success[Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,t,a,tot,ans,fl;
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        ans=tot=fl=0;
        for(int i=1;i<=n+1;i++)
        {
            if(i<=n) cin>>a;
            else a=0;
            if(a==0)
            {
                if(tot==1) fl=1;
                tot=0;
            }
            else tot++;
            ans=max(ans,tot);
        }
        if((ans==2&&!fl)||!ans) cout<<"Bob\n";
        else cout<<"Alice\n";
    }
    return 0;
}

:::