想到了sort然后写成矩阵的形式，然后就是每个人删掉最下面的行或最左边的列，最后操作的输

于是我就开始naive地贪心，然后wa得不成样子……

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

正解：

还是从大到小sort一下，写成矩阵：就是第\(i\)堆有\(a_i\)个糖就在第\(i\)列放\(a_i\)个1这样子

每次操作就是把最左边的列置为0或最下面的行置为0，换种理解：就是把\((1,1)\)上的1向上或向右移一格

现在考虑点\((x,y)\)的状态：

  • 如果\((x,y)\)为边界，那它一定是必败态
  • 如果\((x,y)\)的上面和右面都是必败态，那\((x,y)\)为必胜态
  • 如果\((x,y)\)的上面和右面有一个是必胜态，那\((x,y)\)为必败态

容易发现，一条对角线的状态是相同的

就处理下坐标最右边点\((x,x)\)的状态就行了

代码：

#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main(){
    int n,i;cin>>n;
    for(i=1;i<=n;++i) cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    for(i=1;i<=n;++i){
        if(a[i+1]<i+1 && a[i]>=i){
            int j=0;
            while(a[j+i+1]==i) j++;
            if((a[i]-i)%2==0 && j%2==0) puts("Second");
            else puts("First");
        }
    }
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄