HDU 5795 A Simple Nim （博弈打表找规律）

2022-09-21 14:42:05

A Simple Nim

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5795

Description

Two players take turns picking candies from n heaps,the player who picks the last one will win the game.On each turn they can pick any number of candies which come from the same heap(picking no candy is not allowed).To make the game more interesting,players can separate one heap into three smaller heaps(no empty heaps)instead of the picking operation.Please find out which player will win the game if each of them never make mistakes.

Input

Intput contains multiple test cases. The first line is an integer 1≤T≤100, the number of test cases. Each case begins with an integer n, indicating the number of the heaps, the next line contains N integers s[0],s[1],....,s[n−1], representing heaps with s[0],s[1],...,s[n−1] objects respectively.(1≤n≤106,1≤s[i]≤109)

Output

For each test case,output a line whick contains either"First player wins."or"Second player wins".

Sample Input

2
2
4 4
3
1 2 4

Sample Output

Second player wins.
First player wins.

Source

2016 Multi-University Training Contest 6

##题意：

两人以最优策略对n堆物品进行操作，不能操作者输.
1. 从同一堆中取任意个(不为零).
2. 把一堆分成任意三堆(任一堆非空).

##题解：

变形的Nim博弈. 这里推导部分sg值找规律：
sg[0] = 0;
sg[1] = 1;
sg[2] = mex{sg[0], sg[1]} = mex{0,1} = 2;
sg[3] = mex{sg[0], sg[1], sg[2], sg[1,1,1]} = mex{0,1,2, sg[1]^sg[1]^sg[1] = 1} = 3;
sg[4] = 4;
sg[5] = 5;
sg[6] = 6;
sg[7] = 8;
sg[8] = 7;
sg[9] = 9;
综上，可以看出规律：
sg[0] = 0;
sg[8*k+7] = 8*k+8;
sg[8*k+8] = 8*k+7;
最后异或起来就可以了.

主要是之前做过类似版本：操作2是把一堆分成两堆.
HDU-3032 Nim or not Nim? (http://acm.hust.edu.cn/vjudge/contest/102108#problem/E)
这个版本的结果是sg[4k+3]=4k+4; sg[4k+4]=4k+3;

##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define mid(a,b) ((a+b)>>1)
#define eps 1e-8
#define maxn 2100
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

int n;

int main(int argc, char const *argv[])

{

//IN;

int t; cin >> t;

while(scanf("%d", &n) != EOF)

{

    LL ans = 0;

    for(int i=1; i<=n; i++) {

        LL x; scanf("%I64d", &x);

        if(x % 8LL == 0LL) ans ^= x - 1;

        else if(x % 8LL == 7LL) ans ^= x + 1;

        else ans ^= x;

    }

    if(ans) puts("First player wins.");

    else puts("Second player wins.");

}

return 0;

}

码农公寓