[??记录]AT1999 [AGC002E] Candy Piles

**题意** : 初始时有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。 两人轮流操作，每次进行下列两个操作中的一个 ： - 将每堆石子拿去一个 - 拿去最多的一堆 无法操作者输，问是否先手必胜。 $n\leq 10^5,\ a\leq 10^9$ ，时限$\texttt{2s}$。 ------------ 将 $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; } ```