HDU_5795

描述

一个改进版的NIM博弈游戏，就是选手可以把一堆拆成非空的三堆，作为一次操作。

思路

sg函数打表找规律，发现8是循环周期。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
ll n,num,tmp,ans;
const int maxn=1e4+10;
int sg[maxn],vis[maxn];
void init()
{
    int i,j,k;
    sg[0]=0,sg[1]=1;
    for(i=2;i<=100;i++)
    {
        memset(vis,0,sizeof(vis));
        for(j=1;j<i-1;j++)
            for(k=1;k<i-j;k++)
                vis[sg[j]^sg[k]^sg[i-j-k]]=1;  ///拆分分成三堆
        for(j=0;j<i;j++)
        vis[sg[j]]=1;         ///取石子
        for(j=0;;j++)
        if(!vis[j])break;
        sg[i]=j;
    }
    for(i=1;i<50;i++)
    cout<<"i = "<<i<<" "<<sg[i]<<endl;
}
int main(){
// init();
    cin>>n;
    while(n--){
        ans=0;
        cin>>num;
        for(int i=0;i <num; i++){
            scanf("%I64d",&tmp);
            if((tmp+1)%8==0 && (tmp+1)/8!=0)ans ^= (tmp+1);
            else if(tmp%8==0 && tmp/8!=0) ans ^= (tmp-1);
            else ans = ans^tmp;
        }
        if(ans)printf("First player wins.\n");
        else printf("Second player wins.\n");
    }
    return 0;
}