MYF

HDU 5795 A Simple Nim

Posted on | In | | Visitors

题目链接

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，比这题稍难一些。我的题解传送门

代码

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
46
47
48
49
50
51
52
53
54
55
56
#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.");
    }
}