[？？记录]arc137C Distinct Numbers

这段时间第一道没能自己想出来的题。

题意：给定 \(n\) 个数，二人玩游戏，每次把全局最大数减小并改成一个当前未出现的数，不能操作者败。求胜者。

首先我们来研究一次操作时的情景。首先，当其它值不变，最大值大于次大值加一时，当前状态能走到所有最大值为次大值加一时的状态。这是一个有意思的性质，启示我们去看看最大值等于次大值加一的情景。

如果这是一个必胜态，则它能走到一个必败态，则原情况也能走到一个必败态；若这是一个必败态，则原情况可以直接走到这里。所以，原情况是必胜态。

那么情况就明晰了：当最大值大于次大值加一时，当前情况为必胜态；否则，两个人每次操作完全局最大值都等于次大值加一，这个可以直接递推找到胜者。

感觉这题的关键在这个“决策包容性”，即若一个状态能走到另一个状态能走到的所有后继状态，则这样的状态一定是必胜态。这或许是个经典结论，但我才知道。

#include <cstdio>
using namespace std;
const int M = 300005;
int a[M], n;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if(a[n] - a[n-1] >= 2) {printf("Alice\n"); return 0;}
    int res = a[n] - n;
    if(res % 2 == 0) printf("Alice\n");
    else printf("Bob\n");
    return 0;
}