题解：P14629 [2018 KAIST RUN Fall] Game on Plane

· · 题解

赛时我一开始注意到输出只有两种情况，且 N \le 5000，想到打一个 01 表。所以我的思路在于如何在稍微合理的时间内算出所有正确答案。

首先要知道这是一个 ICG 游戏，对于 ICG 游戏，常见使用 SG 定理来求解。不了解相关博弈论知识的同学可以自行去下面 OI Wiki 的这个词条学习，我这里就不提概念了。

[OI Wiki] 公平组合游戏

然后分析一下操作的本质：当我们连接两个点时，这两个点就被“消耗”掉了，不能再被使用。同时，这条线段会将剩下的点分割成两个独立的区域。因为题目要求线段不能相交，所以分割开的两部分点在后续的游戏中是互不干扰的。也就是说，这个游戏是可以分治的，可以被分解成无数个子游戏。那么，假设当前有 i 个点，我们连接两个点后，剩下的 i-2 个点被分成了两部分，数量分别为 j 和 i-2-j，其中 0 \le j \le i-2，后继状态就是这两个子游戏的组合。

根据 SG 定理，组合游戏的 SG 值等于各子游戏 SG 值的异或和。所以，我们可以得到如下的 SG 函数，注明一下，\operatorname{mex}(S) 表示集合 S 中未出现的最小非负整数：

SG(i) = \operatorname{mex} \{ SG(j) \oplus SG(i-2-j) \mid 0 \le j \le i-2 \}

两个边界条件分别是 SG(0) = 0 或 SG(1) = 0，即没有点或只有一个点，必败。

其实场上的时候，做到这里我发现这个预处理的复杂度只有 O(N^2)，也就是说对于 N \le 5000，其实根本不需要打 01 表，直接在代码中跑预处理也非常快，所以最终的赛时代码如下：

#include<bits/stdc++.h>
#define INF 1e18
#define ll long long
#define pii pair<int,int>
using namespace std;
int sg[5005];
int T,N;
int main(){
    sg[0]=0,sg[1]=0;
    for(int i=2;i<=5000;i++){
        set<int> s;
        for(int j=0;j<=i-2;j++) s.insert(sg[j]^sg[i-2-j]);
        int m=0;
        while(s.count(m)) m++;
        sg[i]=m;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        if(sg[N]) printf("First\n");
        else printf("Second\n");
    }
    return 0;
}