题解 AT1999 【Candy Piles】

· · 题解

首先先%一下楼上的大佬。不过小蒟蒻看不懂大佬的代码，就只能自己写了。

这题是一个博弈论废话。

我们弄些数据可以先打一个表（此打表非彼打表）找下规律。比如数据

5
12 9 4 3 12

我们应该先对这一堆糖排个序，就变成了

12 12 9 4 3

我们让数据再可视化一点，就变成了（其中每一行中0的个数表示这一堆糖里糖的个数）

000 
0000 
000000000 
000000000000 
000000000000

我们可以发现对于任意一种选法（去掉一堆或每一个去掉一个）相当于把原点（最早在左下角）向右或向上移动一个点。所以对于每一种最终状态，比如

000 
0001 
001100000 
111000000000 
100000000000

原点经过的路径为一条折线。

易知，该图中边缘一圈都是必输态，而且一个点如果上方和右边都是必输态，则当前点为必胜态，其余都为必输态，则该图可转换为（我们把必输态的点变为？，必胜态的点变为！)。

???
!?!?
?!?!?????
!?!?!?!?!???
?!?!?!?!??!?

对于小部分的数据，我们可以模拟建图，但是事实上这是不可能的。所以我们要想办法再找一下规律。

我们可以找到一些点，他的横坐标等于纵坐标且这个点不在边界时，这些点的状态与原点相同。其中横坐标最大的点的状态肯定也和原点相同。（有点绕，自己慢慢理解吧）

所以我们可以枚举横坐标就行了。

再看不懂就看代码吧。

//注意别复制代码，最好自己打一份。
#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;++i){
        if(i+1>a[i+1]){
            int ans=0;
            for(int j=i+1;a[j]=i;++j)ans^=1;
            ans|=(a[i]-i)&1;
            if(ans)puts("First");
            else puts("Second");
            return 0;
        }
    }
}