hdu 4664 划线（SG）

N个平面，每个平面有ni个点两个人玩游戏，划线，他们可以划任意一个平面的两个点，有以下要求：两个人划得线不能交叉，不要划已经划过的线，如果一个平面被划了一个空心的三角形，那么这个平面就不能继续划线了。Carol先来，两个人轮着画，谁没线划了就输了，问你最后谁赢。

一个平面上连接点时，不能连接已经有边的顶点，因为对方只需要再连接一次就可以组成一个三角形了

SG[i] i表示剩余没连线的点

0,1个点都是先手必败 SG=0 2,3个点先手必胜 SG[2] = 1 SG[3] = 1

假如一个平面有4个点则有以下后继状态
状态1 剩余的两点在已划线的同一侧 SG[0]^SG[2] = 1
状态2 剩余的两点分别在已划线的两侧 SG[1]^SG[1] = 0
所以SG[4] = 2 ;

打表后发现前面是无序的后面的SG值会出现长度为34的循环节

Sample Input
2 //T
1 //n
2 //每个平面有多少点
2
2 2

Sample Output
Carol
Dave

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <string>

 # include <cmath>

 # include <queue>

 # include <list>

 # define LL long long

 using namespace std ;

 const int MAXN = ;

 int sg[MAXN];

 bool vis[MAXN];

 int mex(int x)

 {

     if(sg[x]!=-)return sg[x];

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     if(x == )return sg[x] = ;

     memset(vis,false,sizeof(vis));

     for(int i = ;i < x-;i++)

         vis[mex(i)^mex(x-i-)] = true;

     for(int i = ;;i++)

         if(!vis[i])

             return sg[x] = i;

 }

 int SG(int x)

 {

     if(x <= )return sg[x];

     else

     {

         x %= ;

         x += *;

         return sg[x];

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     memset(sg,-,sizeof(sg));

     for(int i = ;i <= ;i++)

     {

         sg[i] = mex(i);

     }

     int T;

     int n;

     int a;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         int sum = ;

         for(int i = ;i < n;i++)

         {

             scanf("%d",&a);

             sum ^= SG(a);

         }

         if(sum)printf("Carol\n");

         else printf("Dave\n");

     }

     return ;

 }

巴特西

hdu 4664 划线（SG）

最新文章

热门文章