51NOD 1069 Nim游戏

Description

有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。
例如：3堆石子，每堆1颗。A拿1颗，B拿1颗，此时还剩1堆，所以A可以拿到最后1颗石子。

Input

第1行：一个数N，表示有N堆石子。（1 <= N <= 1000)
第2 - N + 1行：N堆石子的数量。(1 <= A[i] <= 10^9)
Output
如果A获胜输出A，如果B获胜输出B。
Input示例

3

1

1

Output示例

A

题解

博弈真是一门高深的学问，越来越相信玄学了~~2333

神奇的定理： 一个格局记为（x1,x2,…,xn)，且次序无关，此格局为 P-格局 当且仅当 x1^x2^…^xn = 0.其中^是按位异或运算。

神奇的推导（说实话我此时内心想到了线代）：
推导： 对应上述4种情形（为了叙述的简洁，并不十分严谨地证明，而是直接假设结论正确，再说明定理的工作机制）

（1）当（x1,x2,…,xn)中全为0时 ，格局为P-格局，此时x1 ^ x2 ^ … ^ xn = 0成立。

（2）当（x1,x2,…,xn)中只有一个不为0，格局为N-格局，此时x1 ^ x2 ^ … ^ xn = 0不成立。

（3）当（x1,x2,…,xn)是P-格局时，x1,…,xn不全为0.（反证法）
假设x1 ^ x2 ^ … ^ xn = p,且p不为0,记 p 的二进制表示中，最左的1（最高位的1）在从左至右数第 k 位. 由于p是异或运算的结果，那么 x1, x2 , … , xn中至少有一个数第k位为1,不妨设 xi 的第 k 位为1，那么 xi ^ p 第 k 位为0，那么xi > xi^p 显然成立.也就是说，存在某种取法，使i堆的火柴数变化到 xi^p .题设x1 ^ x2 ^ … ^ xn = p，那么x1 ^ x2 ^ … xn ^ p = 0.那么当前格局可以转化到某个P-格局，也就是说当前格局时N-格局，矛盾所以，必有p=0.

(4)当x1 ^ x2 ^ … ^ xn = 0时，如果存在某个移动 xi 变化到 xi ’ ，且x1^x2^….^xi ’ ^…^xn = 0，那么由异或运算的消去律有，xi = xi ’ ，也就是说一根火柴都没取，这不允许的，所以当前格局只能是P格局

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int file, ans = 0;
    long long x;
    scanf("%d", &file);
    while(file--)
    {
        scanf("%lld", &x);
        ans ^= x;
    }
    if(ans) printf("A");
    else printf("B");
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/54851602