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

· · 题解

P14629 [2018 KAIST RUN Fall] Game on Plane

推荐完全没有了解过博弈的友友看一看这个公平组合游戏

初看这道题我还以为是一道 dp 题，数据范围 3 \leq N \leq 5000，首先考虑 O(N^2) 复杂度，从 3 到 5000 一路推过来，后来发现不会写完全可以把平面作图画线段的方式抽象成传统的取石子博弈问题，以下是模型构建过程：

首先，我们要知道什么情况下可以必胜：当一个点已经是两个线段的端点的时候，下一个走的人必然能连成多边形。如图： 可以得出结论 1：只要有一个点为两个线段端点，则下一个人必然可以连成一个三角形，满足凸多边形条件，可以必胜。

其次，我们观察到题目中还有另一个条件，两条线段不能相交，根据凸多边形定义，我们可以观察到每次画线段实际上都是重新分配的过程：

观察到，这条线段将正八边形分开成两块，而且两块之间无法在不穿过中间线段的前提下连接，因此，我们可以认为这条线段将正八边形分割成了两个三角形。以此引申，我们可以将正 n 边形分割成 b 和 n-2-b 边形，从而构建博弈树，又因为分割的起点是正多边形，因此分割后一定是凸多边形，可以看作分割为正 b 和 n-2-b 边形。

结论 2：正 n 边形可以在画完线段后转化为正 b 和正 n-2-b 边形，其中 0 \leq b \leq n-2，0 \leq n-2-b \leq n-2。

因此，我们可以把问题转化为：初始有一堆石子个数为 n，从一堆中取走两个，并且把这堆剩下的石子任意数量分成两堆，如果一个人再也取不了石子则失败。这样就变成了一个简单的取石子问题，我们只需要对于每一种切法的两堆进行 SG 值的异或和，将所有可能的切法取 mex 值就可以了，以下是代码：

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

int t , g[5005] , q;
bool _rec[10005];

void _cal(){
    g[1] = g[0] = 0;
    for(int i = 2 ; i <= 5000 ; i++){
        memset(_rec , false , sizeof(_rec));
        int k = i - 2;
        for(int j = 0 ; j <= k / 2 ; j++){
            int num = g[j] ^ g[k - j];
            _rec[num] = true;
        }
        int mex = 0;
        while(_rec[mex] != 0){
            mex++;
        }
        g[i] = mex;
    }
}

int main(){
    _cal();
    cin >> t;
    for(int i = 1 ; i <= t ; i++){
        cin >> q;
        if(g[q] != 0){
            cout << "First" << endl;
        }
        else{
            cout << "Second" << endl;
        }
    }
    return 0;
}