ARC137C

给你一个排好序的长度为 \(n\) 的自然数数组 \(A\)，保证 \(A_i\) 互不相同，Alice 和 Bob 轮流操作，每次把 \(A_{max}\) 变成一个更小的自然数，需要保证 \(A\) 中仍然没有相同的数，不能操作则输，问谁赢。

\(2 \leq n \leq 3 \times 10^5,\ 0\leq A_i \leq 10^9\)

考虑第一步每个状态之间的转移关系：

如果左边那一大坨有必败状态的话，我们显然可以直接转移过去。

否则由于 \(A_n=A_{n-1}+1\) 这个状态能转移到的全都是必胜状态，所以它自己就是必败状态。

于是我们发现先手必胜，但是要求 \(A_n > A_{n-1} + 1\)。

假如 \(A_n=A_{n-1}+1\)，那两个人永远都不会让 \(A\) 中最大的两个值相差大于等于二，进一步地，我们发现 \(A_{max}\) 每次操作之后都会且仅会减少 \(1\) ，于是我们判断一下 \(A_n-(n-1)\) 的奇偶性即可。

属于是一道加深对 SG 理解的好题。

搬运自 Luogu Blog