首页 > 代码库 > hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。

hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。

 

/**
题目:A Simple Nim
链接:http://acm.hdu.edu.cn/showproblem.php?pid=5795
题意:给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空)
或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。
思路:
组合游戏Nim; 
计算出每一堆的sg值,然后取异或。异或和>0那么先手,否则后手。

对于每一堆的sg值求解方法:

设:sg(x)表示x个石子的sg值。sg(x) = mex{sg(x-1),sg(x-2),...,sg(0),sg(a)^sg(b)^sg(c) |(a+b+c==x)}
当sg(0) = 0;
sg(1) = 1;
sg(2) = 2;
sg(x>=3)就要通过上面式子算出来了。
通过打表可以发现规律。
当x>=3.如果x是8的倍数,那么sg=x-1.
如果(x+1)是8的倍数,那么sg=x+1.


*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1e6+10;
const int mod = 1e9+7;
int T, n;
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        int ans = 0;
        for(int i = 0; i < n; i++){
            int x;
            scanf("%d",&x);
            if(x%8==0&&x!=0){
                ans ^= x-1;
            }else
            {
                if((x+1)%8==0){
                    ans ^= x+1;
                }else
                {
                    ans ^= x;
                }
            }
        }
        printf("%s\n",ans?"First player wins.":"Second player wins.");
    }
    return 0;
}

 

hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。