Nim Game-蒲公英云

Nim Game

博客图片

题目概述

有n堆石子,每堆的数量分别为 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an,两个人轮流取石子,每次可以从一堆石子中取任意数量的石子,交替进行,最后没法取石子的输,两人都采取它们情况下的最优策略,判断是先取的输还是后取的输.

解法

如果只有一堆石子,显然先取的取走所有的石子,获得胜利.如果此时有两堆石子,先取的输还是后取的输取决于这两堆是否相等,与这两堆具体的石子数量无关.对于两堆相同的石子,无论先取的从一堆中取多少石子,后取的总可以通过从另外一堆中取出对应数量的石子,保证两堆石子数量相等的情况不变,直到先取的把另外一堆取完.当两堆石子不相等时,先取的可以从数量较多的石子中取出一定数目的石子,使得剩下的这堆和另外一堆保持相同的数量,从而情况就转化成前面那种,从而最后输掉的一定是后取石子的.

在<组合数学>这本书中针对这个问题给出的一个解法是将每一堆石子的数量展开为对应的二进制数,根据展开中为1的那些位,把这一堆石子分成若干堆,这些子堆的数量是 2 0 , 2 1 , ⋯ 2^0,2^1,\cdots 20,21,⋯,为了后面分析方面,每一堆展开后按照为的长度补零对齐,得到:
a 1 = a s 1 ⋯ a 11 a 01 a 2 = a s 2 ⋯ a 12 a 02 ⋮ ⋯ a_1 = a_{s1}\cdots a_{11}a_{01}\\ a_2 = a_{s2}\cdots a_{12}a_{02}\\ \vdots\\ \cdots a1=as1⋯a11a01a2=as2⋯a12a02⋮⋯
如果 a s 1 + a s 2 + ⋯ a_{s1}+a_{s2}+\cdots as1+as2+⋯是偶数,那么成这个位是平衡位,否则称为非平衡位.如果所有的位都是平衡位,那么称这个Nim游戏是平衡的,否则称为非平衡的.如果游戏是平衡的,那么后取的玩家将会获胜,否则先取的玩家将获胜.
对于处于非平衡状态的Nim游戏,当第一个玩家可以从最大的那个不平衡位的为1的那些堆里面取出一定数量的石子,使得此时剩余的石子处于一个平衡状态,对于后取的玩家来说,无论怎样取,最终留给先取玩家的都是一个非平衡状态,经过这样的不断取,最后一定会出现只有一个状态,先取的只剩下一堆了,也就是说此时每一个非平衡位上有且仅有一个为1,并且这些为1的处于同一行,此时先取的可以把这一行全部取走,也就是取走剩下的这最后一堆.对于平衡状态来说,此时的后取的处于非平衡状态.

对于二进制展开每一位的1的奇偶性的判断可以通过 ⊕ \oplus ⊕来计算,很明显 a s 1 ⊕ a s 2 ⊕ ⋯ a_{s1}\oplus a_{s2}\oplus \cdots as1⊕as2⊕⋯,如果1的个数是偶数个那么结果是0,否则是1可以对展开式中的每一位进行这样的计算,如果每一位的1出现的次数都是偶数,那么最终 a 1 ⊕ a 2 ⊕ ⋯ = 0 , a_1\oplus a_2\oplus \cdots=0, a1⊕a2⊕⋯=0,否则结果不是0.,于是可以很容易的得到Nim Game判断输赢的程序:

ll sum = 0;
    for(int i = 0; i < n; ++i){
        sum ^= a[i];
    }

根据sum是佛是0判断先取的获得胜利还是后取的获得胜利.

题目链接

hdu1850

想法

Nim Game的概念题,唯一的不同就是要求如果胜利,计算第一步的选择,也就是可以计算有几个不平衡位.假设取第i堆,设除去a[i]得到的异或运算的结果为H,则sum = H^a[i],如果第i堆石子的数量不少于H,那么可以通过取石子使得这堆石子剩下的数目为H,从而 H ⊕ H = 0 H\oplus H=0 H⊕H=0转化为平衡状态.异或操作有个比较神奇的性质是 A ⊕ B ⊕ B = A A\oplus B \oplus B=A A⊕B⊕B=A.

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10005;
ll a[N];
void solve(int n){
    ll sum = 0;
    for(int i = 0; i < n; ++i){
        sum ^= a[i];
    }
    if( sum == 0 ){
        printf("0\n");
        return;
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i){
        if( (sum ^ a[i]) <= a[i])
            ++ans;
    }
    printf("%lld\n", ans);
}
int main(int argc, const char** argv) {
    int n;
    while(~scanf("%d",&n) && n ){
        for(int i = 0; i < n; ++i){
            scanf("%lld",&a[i]);
        }
        solve(n);
    }
    return 0;
}