题解 | 浮木博弈

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
void slove()
{
    int n;
    std::cin>>n;
    int f=1;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;i++) 
    {
        std::cin>>a[i];
        if(a[i]==1&&i!=n)
        {
            if(i==1||a[i-1]==1)
            {
                f^=1;
            }
        }
    }
    if(f) std::cout<<"Alice"<<endl;
    else std::cout<<"Bob"<<endl;
    
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1;
    std::cin>>T;
    while(T--)    {
        slove();
    }
    return 0;
}

考虑没有1的情况，不管奇数偶数，Alice都有策略必胜（即拿a【i】-1个让Bob拿最后一个，然后最后一堆直接拿即可），但1则会破坏这一必胜的策略。所以遇到1的时候，我们继续分类：因为拿了1相当于先后手交换，所以作为优势的先手，我们尽可能要让后手拿到1。所以如果某个位置x是1，那么x-1这个位置我们直接全部拿掉就能保证让Bob拿到1了。但还有一个顾虑就是如果x-1这个位置也是1，那么状态还是会改变（所以是和连续1的个数有关），但我们可以遍历模拟这一变换过程即可。注意的是，如果最后一个堆是1，并不会影响结果，因为拿完的人胜利。可配合代码理解模拟过程。