[原创]HDU 3389 Game(博弈 Nim 找规律)

2016-08-12 13:42:04 Tabris_ 阅读数：192

博客爬取于2020-06-14 22:43:50
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52190898

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3389
----------------------.
Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 610 Accepted Submission(s): 426

Problem Description
Bob and Alice are playing a new game. There are n boxes which have been numbered from 1 to n. Each box is either empty or contains several cards. Bob and Alice move the cards in turn. In each turn the corresponding player should choose a non-empty box A and choose another box B that B < A && (A+B)%2=1 && (A+B)%3=0. Then, take an arbitrary number (but not zero) of cards from box A to box B. The last one who can do a legal move wins. Alice is the first player. Please predict who will win the game.

Input
The first line contains an integer T (T<=100) indicating the number of test cases. The first line of each test case contains an integer n (1<=n<=10000). The second line has n integers which will not be bigger than 100. The i-th integer indicates the number of cards in the i-th box.

Output
For each test case, print the case number and the winner’s name in a single line. Follow the format of the sample output.

Sample Input
2
2
1 2
7
1 3 3 2 2 1 2

Sample Output
Case 1: Alice
Case 2: Bob

---------------------------------------------.
题目大意 就是把右边盒子里的的给左边盒子 但要求B < A && (A+B)%2=1 && (A+B)%3=0
谁不能移牌 谁就输了

题目分析 ：
就是 博弈么 找规律 就好 了

根据上面的很容易分析到
1.最后一定会放到 1 3 4这3个盒子里
2.右边最终能移到1 3 4中的哪一个也是能够求的
3.右边的移到左边的步数是偶数个还是奇数个也是可求的 只要经过偶数步数才能到达的 都是必败点

分析每一个的时候可以把其他的盒子当成空的
这样就是N个游戏组合到了一起 然后作为NIM取一下异或值就行了

总的来说就是分情况讨论一下
奇数： %3 == 0 偶数步骤后到达盒子3

%3 == 1 偶数步骤后到达盒子1

%3 == 2 ji步骤后到达盒子2

偶数： %3 == 0 奇数步骤后到达盒子3

%3 == 1 偶数步骤后到达盒子1

%3 == 2 奇数步骤后到达盒子4

之后操作就好了

附本题代码
------------------------------------.

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
# include<bits/stdc++.h>
using namespace std;
# define LL long long int
# define lalal puts("******");

int main()
{
    int _,p=0;
    scanf("%d",&_);
    while(_--)
    {
        int n,ans = 0,x;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);  //没有 xor 的既是偶数步才能到达既定位置的  必败 所以sg值一定为0  不需要 xor 了  打表是一个强有力的工具啊
            if(i % 2 == 1)
                    if(i % 3 == 2) ans ^=x;  //奇数必胜 然后就可以当成 Nim博弈进行操作了
            if(i % 2 == 0)
            {
                if(i % 3 == 2) ans ^=x;
                if(i % 3 == 0) ans ^=x;
            }

        }

        printf("Case %d: ",++p);
        if(ans) puts("Alice");
        else puts("Bob");

    }
    return 0;
}