桌上有 \(n\) 堆糖果,第 \(i\) 堆糖果有 \(a_i\) 个糖。两人在玩游戏,轮流进行,每次进行下列两个操作中的一个:
- 将当前最大的那堆糖果全部吃完
- 将每堆糖果吃掉一个
吃完的人输,假设两人足够聪明,问谁有必胜策略?
把序列从大到小排序,观察到 \(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;
}
标签:Piles,int,Candy,maxn,AGC002E,糖果
From: https://www.cnblogs.com/zcr-blog/p/17461887.html