2018-2019 XIX Open Cup, Grand Prix of Korea (Division 2) GYM 102058 F SG函数

http://codeforces.com/gym/102058/problem/F

题意：平面上n个点两个人轮流在任意两个点之间连一条线但是不能和已有的线相交，先围成一个凸多边形的获胜，先手赢还是后手赢。

解析: 当一个顶点连了两条边，那么就可以再画一笔组成三角形，

三个点先手胜

四个点先手胜

五个点后手胜

.......

画完一笔之后其实变成了两个子局面假设一边大小为 j 那么就分成了 j 和（n-j-2）两个局面我们枚举 i 求出两部分的sg值

再用异或连接起来就是该状态可以到达的状态。

AC代码

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define mp make_pair
 4 #define fi first
 5 #define se second
 6 #define all(a) (a).begin(), (a).end()
 7 #define fillchar(a, x) memset(a, x, sizeof(a))
 8 #define huan printf("
")
 9 #define debug(a,b) cout<<a<<" "<<b<<" "<<endl
10 #define ffread(a) fastIO::read(a)
11 using namespace std;
12 const int maxn = 3e5+50;
13 const int maxm = 1e4+10;
14 const int inf = 0x3f3f3f3f;
15 const int mod = 998244353;
16 const double epx = 1e-6;
17 typedef long long ll;
18 const ll INF = 1e18;
19 const double pi = acos(-1.0);
20 int f[5005],sg[5005],s[5005];
21 int n,m,k;
22 void SG(int x)
23 {
24     fillchar(sg,0);
25     for(int i=1;i<=x;i++)
26     {
27         fillchar(s,0);
28         for(int j=0;j<=i-2;j++)
29         {
30             s[sg[j]^sg[i-2-j]]=1;
31         }
32         for(int j=0;;j++)
33             if(!s[j])
34             {
35                 sg[i]=j;
36                 break;
37             }
38     }
39 }
40 int main()
41 {
42     SG(5000);
43     int t;
44     scanf("%d",&t);
45     while(t--)
46     {
47         scanf("%d",&n);
48         if(sg[n])
49             printf("First
");
50         else
51             printf("Second
");
52     }
53 }