AGC002E Candy Piles

桌上有 \(n\) 堆糖果，第 \(i\) 堆糖果有 \(a_i\) 个糖。两人在玩游戏，轮流进行，每次进行下列两个操作中的一个:

1. 将当前最大的那堆糖果全部吃完
2. 将每堆糖果吃掉一个

吃完的人输，假设两人足够聪明，问谁有必胜策略？

把序列从大到小排序，观察到 \(2\) 操作后最大值不变，构建一个网格，每次相当于往右或往上走。所有边界就是必胜态，然后可以推出所有状态。这样复杂度爆炸。观察到对角线上的状态相同，这可以归纳证明。于是可以找到右上角的点的状态，这个之后上面和右面有关。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, a[maxn];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	sort(a + 1, a + 1 + n, greater<int>());
	for (int i = 1; i <= n; i++) {
		if (i == n || i + 1 > a[i + 1]) {
			int cnt = 0;
			for (int j = i + 1; j <= n; j++) {
				if (a[j] == i) {
					cnt++;
				}
			}
			if ((cnt & 1) || ((a[i] - i) & 1)) puts("First");
			else puts("Second");
			break;
		}
	}
	return 0;
}