题解 AT_agc002_e【[AGC002E] Candy Piles】
zhaoyp
·
·
题解
AGC002E
# Description
> 有 $n$ 堆石子，每堆石子有 $a_i$ 个，两人轮流操作。要么取走石子最多的一堆，要么将每堆石子取走 $1$ 个。谁取走最后 $1$ 个石子，谁就输了。假设两人都足够聪明，求先手必胜还是后手必胜。
# Solution
神仙题。
是一个经典的将博弈过程转化成网格图的模型。
考虑将 $a$ 降序排序，排在一个 $n$ 列的网格图上。初始站在 $(1,1)$ 这个位置上，令站的位置的右上部分是剩余的石子，那么两种操作相当于向上或向右走一格，谁走出去谁就输了。
记 $f_{x,y}$ 表示在 $(x,y)$ 上胜负状态，$1$ 代表先手必胜，$0$ 代表先手必败。
下面我们来证明：$f_{x,y} = f_{x+1,y+1}$。
一个状态是必败态，当且仅当它的所有后继状态都是必胜态；一个状态是必胜态，当且仅当它的后继状态存在一个必败态。
- 若 $(x,y)$ 必胜，则 $(x+1,y),(x,y+1)$ 中至少有一个必败，必败的所有后继状态都是必胜，$(x+1,y+1)$ 都是他们的后继状态，所以 $(x+1,y+1)$ 必胜。
- 若 $(x,y)$ 必败。则 $(x+1,y),(x,y+1)$ 必胜，则 $(x+2,y+1),(x+1,y+2)$ 必胜。所以 $(x+1,y+1)$ 的两个后继状态都是必胜，故 $(x+1,y+1)$ 必败。
于是我们只需要找到 $(1,1)$ 所在对角线上的最后一个点。在这个点上，之后要么一直向上，要么一直向右，两个后继状态的胜负根据剩余步数的奇偶比较好判断。就可以推出 $(1,1)$ 的状态。
时间复杂度 $O(n)$。
# code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,a[maxn],ans;
bool cmp(int a,int b){return a > b;}
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
cin >> a[i];
sort(a + 1,a + 1 + n,cmp);
for(int i = 1;i <= n;i++)
if(i + 1 > a[i + 1])
{
int x = (a[i] - i + 1) & 1,y = 1;
for(int j = i + 1;j <= n&&a[j] >= i;j++)
y ^= 1;
puts(x + y == 2 ? "Second" : "First");
return 0 ;
}
}
```