HDU 5795 A Simple Nim

题目链接

HDU 5795

题目类型：sg函数

题目来源：2016 Multi-University Training Contest 6

题目分析

题目大意

一个可以拆堆的Nimm博弈。

现在有 $n$ 堆石子，每个人可以在一堆棋子中取若干个，也可以不取，将任意一堆棋子拆成三堆棋子，三堆棋子中每一堆都至少有一个棋子，两人都选择最优方案操作，问最后谁赢谁输

解析

首先，这个博弈问题可以根据这n堆的sg值的异或和是否为 $0$ 判断胜负，那么我们现在要找的就是对于有 $n$ 个棋子的堆的sg值。

好吧，我们来手推一下。

我们用 $n$ 表示当前堆的棋子数量， $sg[n]$ 表示该堆棋子的sg值，mex(Set S)表示不属于S的最小非负整数。

$n=0$ 时，当前玩家必败， $sg[0]=0$

$n=1$ 时，当前玩家可以选取1个棋子转移到 $n=0$ 的情况， $sg[1]=mex\left{ sg[0]\right}=mex\left{ 0\right}=1$

$n=2$ 时，当前玩家可以选取 $\left{ 1, 2\right}$ 个棋子转移到 $n=\left{ 1, 0\right}$ 的情况， $sg[2]=mex\left{ sg[1], sg[0]\right}=mex\left{ 0, 1\right}=2$

$n=3$ 时，当前玩家可以选取 $\left{ 1, 2, 3\right}$ 个棋子转移到 $n=\left{ 2, 1, 0\right}$ 的情况，还可以将 $3$ 拆成三堆含有 $1$ 个棋子的情况， $sg[3]=mex\left{ sg[2], sg[1], sg[0], sg[1]⨁sg[1]⨁sg[1]\right}=mex\left{ 2, 1, 0, 1\right}=3$

$n=4$ 时，当前玩家可以选取 $\left{ 1, 2, 3, 4\right}$ 个棋子转移到 $n=\left{ 3, 2, 1, 0\right}$ 的情况，还可以将 $4$ 拆成 $1+1+2$ 个棋子的情况， $sg[4]=mex\left{ sg[3], sg[2], sg[1], sg[0], sg[1]⨁sg[1]⨁sg[2]\right}=mex\left{ 3, 2, 1, 0, 2\right}=4$

$n=5$ 时，当前玩家可以选取 $\left{ 1, 2, 3, 4, 5\right}$ 个棋子转移到 $n=\left{ 4, 3, 2, 1, 0\right}$ 的情况，还可以将 $5$ 拆成 $1+2+2$ 或者 $1+1+3$ 个棋子的情况， $sg[5]=mex\left{ sg[4], sg[3], sg[2], sg[1], sg[0], sg[1]⨁sg[2]⨁sg[2], sg[1]⨁sg[1]⨁sg[3]\right}=mex\left{ 4, 3, 2, 1, 0, 1, 3\right}=5$

$n=6$ 时，当前玩家可以选取 $\left{ 1, 2, 3, 4, 5, 6\right}$ 个棋子转移到 $n=\left{ 5, 4, 3, 2, 1, 0\right}$ 的情况，还可以将 $6$ 拆成 $1+2+3$ 或者 $1+1+4$ 或者 $2+2+2$ 个棋子的情况， $sg[6]=mex\left{ sg[5], sg[4], sg[3], sg[2], sg[1], sg[0], sg[1]⨁sg[2]⨁sg[3], sg[1]⨁sg[1]⨁sg[4], sg[2]⨁sg[2]⨁sg[2]\right}=mex\left{ 5, 4, 3, 2, 1, 0, 0, 4, 2\right}=6$

$n=7$ 时，该情况比较特殊，当前玩家可以选取 $\left{ 1, 2, 3, 4, 5, 6, 7\right}$ 个棋子转移到 $n=\left{ 6, 5, 4, 3, 2, 1, 0\right}$ 的情况，还可以将 $7$ 拆成 $1+1+5$ 或者 $1+2+4$ 或者 $1+3+3$ 或者 $2+2+3$ 个棋子的情况， $sg[7]=mex\left{ sg[6], sg[5], sg[4], sg[3], sg[2], sg[1], sg[0], sg[1]⨁sg[1]⨁sg[5], sg[1]⨁sg[2]⨁sg[4], sg[1]⨁sg[3]⨁sg[3], sg[2]⨁sg[2]⨁sg[3]\right}=mex\left{ 6, 5, 4, 3, 2, 1, 0, 5, 7, 1\right}=8$

$n=8$ 时，该情况比较特殊，当前玩家可以选取 $\left{ 1, 2, 3, 4, 5, 6, 7, 8\right}$ 个棋子转移到 $n=\left{ 7, 6, 5, 4, 3, 2, 1, 0\right}$ 的情况，还可以将 $8$ 拆成 $1+1+6$ 或者 $1+2+5$ 或者 $1+3+4$ 或者 $2+2+4$ 或者 $2+3+3$ 个棋子的情况， $sg[8]=mex\left{ sg[7], sg[6], sg[5], sg[4], sg[3], sg[2], sg[1], sg[0], sg[1]⨁sg[1]⨁sg[6], sg[1]⨁sg[2]⨁sg[5], sg[1]⨁sg[3]⨁sg[4], sg[2]⨁sg[2]⨁sg[4], sg[2]⨁sg[3]⨁sg[3]\right}=mex\left{ 8, 6, 5, 4, 3, 2, 1, 0, 6, 6, 6, 4, 2\right}=7$

后面就不一一推了，再找几个数可以发现，当$n = 8 k - 1 $时$ sg[n] = 8 k $，当$ n = 8 k $时，$ sg[n] = 8 k - 1 $，其他情况$ sg[n] = n$

通过上面的方式我们可以求出对于一堆来讲，他的sg值，然后将这 $n$ 堆的sg值异或起来，若为 $0$ 则为必败，否则必胜。

类似的博弈题目还有2016年多校第六场的HDU5724，比这题稍难一些。我的题解传送门

代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int fcnt=120005;
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,tmp,sum=0;
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",&tmp);
            if (tmp%8==7) {
                sum^=(tmp+1);
            }
            else if (tmp%8==0){
                sum^=(tmp-1);
            }
            else
                sum^=tmp;
        }
        if (sum==0) {
            puts("Second player wins.");
        }
        else
            puts("First player wins.");
    }
}