题解：P11072 Alice and Bob

Vct14 · 2024-09-17 22:07:18 · 题解

本场比赛第二难的题目。

考虑到 Bob 可以选择不动，那么他操作后的 a_1 一定与他操作前 Alice 操作后的 a_1 一样。而为了不让自己输，Alice 会一直选择她曾经没有选择过的 a_1，直到将所有的 a_i 全都选择过一次。此时 Alice 会落败。

那么 Alice 想要反败为胜，只能寄希望于某一次操作后她可以使 a_1=0，也就是操作前存在 i\in [2,a_1]，有 a_i=0。但是由于 Bob 的策略是不动，因此 Alice 只能在前一步操作时就使得存在 i\in [2,a_1]，有 a_i=0。事实上，如果 Alice 这样操作的话，Bob 的下一步就可以直接将 a_1 变成 0 从而获胜。因此，当且仅当一开始就存在 i\in [2,a_1]，有 a_i=0 时 Alice 可以获胜。否则 Bob 都可以获胜。

#include<bits/stdc++.h>
using namespace std;

int a[22];

int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1; i<=n; i++) cin>>a[i];
        bool als=0;
        for(int i=1; i<=a[1]; i++) if(a[i]==0){
            als=true;
            puts("Alice");
            break;
        }
        if(!als) puts("Bob"); 
    }
    return 0;
}