题解：P11072 Alice and Bob

dci66666 · 2024-09-19 18:39:49 · 题解

众所周知，博弈论题靠蒙，这道给我弄笑了。

题目理解

Alice 和 Bob 在一起玩游戏。

初始时给定一个值域在 0 到 n 之间的整数序列 a，然后他（她）们轮流进行如下操作，Alice 先操作。

• 操作：任意重排 a_{1\sim a_1}。

如果某一个人操作前 a_1=0，则他（她）立刻输，因为他（她）无法进行操作。

如果某次操作结束后某一个人存在两次他（她）的操作满足操作结束后的 a_1 相同，则他（她）立刻输。（摘自原题）

好了，看了看后面的样例，发现第一个人处于劣势。

想想有什么必胜策略吗？有。

首先两种情况极好判断：

1. 这个 a_1=0 这时第二个人胜。
2. 前 a_1 个数中有 0，这时第一个人胜。

还有很多种情况，比如下面这种：

3. 前 a_1 个数中的最大值有 0。

这该怎么办呢？

如果考虑把 0 扔给另一个人肯定是不优的，而且另一个人会把 0 放到 a_1 扔给自己，所以可以把对方的状态复原后还给第一个人，这样既可以保证自己每次改的状态不重复，同时直到第一个人把所有状态取完后输掉。

那怎么证明在操作中没有 0 呢？

因为当我们考虑到这一步时，前 a_1 项一定没有 0。那么对方的调整后的前 a_1 中有 0 时直接扔过去，不然就复原，那么因为 a_1 一定不是 1，（如果是 1 第一个人一定输。）所以有若干种状态，这个数一定会被先手先取完，所以先手一定输。

那么没有 0 也非常简单，还是后手复原就行了。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a[25];
int main(){
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        bool f=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        if(a[1]==0){cout<<"Bob"<<endl;continue;}
        else {
            for(int i=1;i<=a[1];i++){
                if(a[i]==0){
                    cout<<"Alice"<<endl;
                    f=1;
                    break;
                }
            }
        }
        if(!f)cout<<"Bob"<<endl;
    }
}