【题解】

题意：给定一个凸n多边形的n点集，要求两个人轮流执行以下操作：选取两个点并连线，要求所连线段不与之前存在的线段相交。如果形成一个凸多边形就结束游戏，最后一个执行操作的人获胜。

思路：每一个点集都可以被一条直线分割成一个包含两部分的子局面，根据SG函数从前往后推即可。

这里推一篇文章 博弈论 SG函数

【代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
int sg[maxn],s[maxn];

void SG()
{
    sg[1]=0,sg[2]=1;
    for(int i=3;i<=5000;i++){
        memset(s,0,sizeof(s));
        for(int j=0;j<=i-2;j++) //所有子局面
            s[(sg[j]^sg[i-2-j])]=1;
        for(int j=0;;j++){
            if(!s[j]){
                sg[i]=j; break;
            }
        }
    }
}
int main()
{
    SG();
    int t; scanf("%d",&t);
    while(t--){
        int n; scanf("%d",&n);
        if(sg[n]) puts("First");
        else puts("Second");
    }
    return 0;
}

【板子】

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void SG(int n)
{
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i=1;i<=n;i++){
        //每一次都要将上一状态的后继集合重置
        memset(S,0,sizeof(S));
        for(j=0;f[j]<=i&&j<=N;j++)
            S[SG[i-f[j]]]=1;  //将后继状态的SG函数值进行标记
        for(j=0;;j++) 
            if(!S[j]){   //查询当前后继状态SG值中最小的非零值
            SG[i]=j; break;
        }
    }
}