题解

思路

记最大的两个数为 $A_{N-1},A_N$。

做法

若 $A_N\ge A_{N-1}+2$，则当前局面必胜：先考察所有把 $A_N$ 降到 $A_{N-1}$ 以下所得的局面，若其中有必败局面，直接转移过去即可；否则把 $A_N$ 改为 $A_{N-1}+1$，此时对手的每一种转移都会到达前述的必胜局面，因而这个相邻局面是必败局面，原局面仍可一步转移到它并获胜。

只需继续处理 $A_N=A_{N-1}+1$ 的情况。根据上述结论，最优对局中不会把一个差至少为 $2$ 的局面留给对手，所以每次操作都恰好使当前最大值减少 $1$。当最大值为 $N-1$ 时，序列只能是 $0,1,\ldots,N-1$，此时无法操作；因此共会操作 $A_N-(N-1)$ 次，该值为奇数时 Alice 获胜，否则 Bob 获胜。

复杂度

读入序列后只需检查最后两项及这个奇偶性，时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。