题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1850

题目描述

一年在外 父母时刻牵挂

春节回家 你能做几天好孩子吗

寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场

悄悄给爸爸买个小礼物

主动地 强烈地 要求洗一次碗

某一天早起 给爸妈用心地做回早餐

如果愿意 你还可以和爸妈说

咱们玩个小游戏吧 ACM课上学的呢~

下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。

现在我们不想研究到底先手为胜还是为负,我只想问大家:

——“先手的人如果想赢,第一步有几种选择呢?”

思路

尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

三堆物品$(a, b, c)$当$a\oplus b=c$($\oplus$为异或,$a\oplus a=0, a\oplus 0=a$)时为奇异局势(即先手必败),显然$(0,0,0)$是奇异局势。

$a\oplus b=c$,即$a\oplus b\oplus c=0$,只需判断所有数异或的结果是否为0即可判断是否必败。

所以从一个非奇异局势转换为奇异局势的方式可以是

1. $a = b\oplus c$
  1. $b = a\oplus c$
  2. $c = a\oplus b$

以上也适用于多堆的情况。

AC代码

/*************************************************************************
    > File Name: 1850.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-26 Sun 15:26:28 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
    int M;
    int h[101];
    while(cin >> M && M) {
        for(int i=0; i<M; ++i)
            cin >> h[i];
        int result = h[0];
        for(int i=1; i<M; ++i)
            result^=h[i]; // 计算所有数的异或结果
        if(result) {
            int ans = 0;
            for(int i=0; i<M; ++i)
                if((result^h[i]) < h[i]) // 例如三堆的情况,$a\oplus (a \oplus b\oplus c)=b\oplus c$,当$b\oplus c<a$的时候,可以转换为奇异局势。
                    ++ans;
            cout << ans << endl;
        }
        else
            cout << 0 << endl;

    }

    return 0;
}