[??记录]AT1999 [AGC002E] Candy Piles
command_block
·
·
个人记录
题意 : 初始时有 n 堆石子，第 i 堆有 a_i 个。
两人轮流操作，每次进行下列两个操作中的一个 ：
无法操作者输，问是否先手必胜。
------------
将 $a$ 从大到小排序，绘制直方图，两种操作分别对应去掉一行或一列。
那么问题变为，在这个直方图上，每一步可以向上或向右走，走完最后一步者输。
可以大力递推出 $P/N$ 态，如下图 ：
发现规律 ： 对于某个格子，若右上方有格子，那么状态与右上方的格子相同。可以归纳证明。
于是，我们只需要关心有色部分的状态。
橙色位置的状态是边界，中间的黄色段容易递推得到。
```cpp#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
int n,a[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);reverse(a+1,a+n+1);
int p=0;
for (int i=1;i<=n;i++)
if (a[i]>=i)p=i;
//边界上的点为 (p,p)
if (p!=a[p+1]&&a[p]==p){puts("Second");return 0;}
else {
int c=1;bool fl=0;
for (int i=p;a[i+1]==p;i++)c++;
if (!(c&1))fl|=1;
if (a[p]>p&&((a[p]-p)&1))fl|=1;
puts(fl?"First":"Second");
}return 0;
}
```