I. Game on Plane（SG函数 博弈论）ccsudeer-

题目链接

题目描述

给你n个节点的凸包（未连线），每次选择两个点连一条线，不能与之前出现的线有相交。当出现一个凸包的时候游戏结束

谁最后无法移动了就输了，现在问 是先手必胜还是后手必胜。

类似题：HDU4664 Triangulation  

HDU描述的是当出现一个三角形时 游戏结束。其实是一个意思,HDU的范围大一点  涉及循环节。

做法：SG函数。如果你是第一次听说SG函数。看链接：知乎

而对于这题的分析呢。

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

那么对于当前局面SG（x），它的后继局面为 任选两个点连接后，得到的局面是被该线分割成两部分，如果下一个人在这条线的两个端点任意一个出发再连一条线，则下下个人就可以连成三角形使得游戏结束，因此下一个人必不会再从这两个端点连线。因此后继局面为sg(i)与sg(x-i-2)  [0<=i<=x-2]

即得到sg函数为：    SG(X)=mex{sg(i)^sg(x-i-2)}  [0<=i<=x-2]

对于GYM的这道题  直接推SG数组即可。

对于HDU 的打表找循环节

由于数据的n很大，打表出前1000项观察可以得到循环节。。。打表

代码参考来自：博客  

 

 /* 因为一条直线把当前局面分割成两个子局面， i-2是连接完直线后剩下的点，所以两个子局面的异或就是sg[j]^sg[i-2-j] */ #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; }

HDU 题 代码参考：博客

 #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; const int MAXN = 1000 + 10; int vis[MAXN]; int SG[MAXN]; int mex(int x) {     if(SG[x] != -1)         return SG[x];     memset(vis, 0, sizeof(vis));     for(int i=0;i<=x-2;i++)         vis[mex(i) ^ mex(x-2-i)] = 1;     for(int i=0;;i++) if(!vis[i])     {         SG[x] = i;         break;     }     return SG[x]; } int main() {     memset(SG, -1, sizeof(SG));     for(int i=0;i<200;i++)         SG[i] = mex(i);     int T;     scanf("%d", &T);     while(T--)     {         int n, x;         scanf("%d", &n);         int ans = 0;         for(int i=0;i<n;i++)         {             int x;             scanf("%d", &x);             if(x < 100) ans ^= (SG[x]);             else             {                 x -= 60;                 x %= 34;                 ans ^= SG[x + 60];             }         }         if(ans) printf("Caroln");         else printf("Daven");     }     return 0; }