HDU 3032 Nim or not Nim?(SG打表找规律)

Myth丶恋晨 2023-10-11 09:36 13阅读 0赞

题意：

给你n堆石子，你每次只能操作一堆石子

1、拿去任意个，最少1个

2、把这一堆分成两堆，没有要求对半分

解析+代码：

1 //解题思路：
     2 //对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继 },这里的g（x）即sg[x]
     3 //例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？
     4 //sg[0]=0,
     5 //n=1时，可以取走{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg[1]=1;
     6 //n=2时，可以取走{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0；
     7 //n=3时，可以取走{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;
     8 //n=4时，可以取走{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
     9 //n=5时，可以取走{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；
    10 //以此类推.....
    11 //     x  0  1  2  3  4  5  6  7  8....
    12 //sg[x] 0  1  0  1  2  3  2  0  1....
    13 //所以，对于这题：
    14 //sg[0]=0
    15 //sg[1]=mex{sg[0] }=1
    16 //sg[2]=mex{sg[0],sg[1],sg[1,1] }=mex{0,1,1^1}=2;
    17 //sg[3]=mex{sg[0],sg[1],sg[2],sg[1,2]}=mex{0,1,2,1^2}=mex{0,1,2,3}=4;
    18 //sg[4]=mex{sg[0],sg[1],sg[2],sg[3],sg[1,3],sg[2,2]}=mex{0,1,2,4,5,0}=3;
    19 //              ..............................................................................
    20 //
    21 //可以发现：sg[4*k+1]=4*k+1,sg[4*k+2]=4*k+2,  sg[4*k+3]=4*k+4,sg[4*k+4]=4*k+3
    22 //通过SG函数打表可以发现规律。
    23 //当n=4*k时，sg[n] = n-1;
    24 //当n= 4*k+3 时，sg[n] = n+1;
    25 //其余sg[n] = n;
    26 #include <stdio.h>
    27 #include <algorithm>
    28 #include <iostream>
    29 #include <string.h>
    30 using namespace std;
    31 const int MAXN = 10000;
    32 int SG(int x)
    33 {
    34     if(x == 0)return x;
    35     if(x % 4 == 0)return x-1;
    36     if(x % 4 == 3)return x+1;
    37     return x;
    38 }
    39 int main()
    40 {
    41     int T;
    42     int n,a;
    43     int sum;
    44     scanf("%d",&T);
    45     while(T--)
    46     {
    47         scanf("%d",&n);
    48         sum = 0;
    49         for(int i = 0;i < n;i++)
    50         {
    51             scanf("%d",&a);
    52             sum ^= SG(a);
    53         }
    54         if(sum == 0)printf("Bob\n");
    55         else printf("Alice\n");
    56     }
    57     return 0;
    58 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11365164.html