放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

POJ 2975 Nim 题解《挑战程序设计竞赛》

目录

挑战程序设计竞赛.jpg

POJ 2975 Nim 

Nim招数:在经典Nim游戏中,先手有多少种取胜方法?

4.2找出游戏的必胜策略 

Nim与Grundy数

经典算法中,XOR=k0^k1^…^kn-1,若为0,则先手必败,否则必胜。在必胜态时,先手要做的就是拿走某堆石头中的m个,使得XOR变为0,将必败态转嫁给后手,题目就是在问有几种使XOR变为0的方法。

假设从第i堆石头拿走m块就是这些方法中的一种,则有(ki-m)^(XOR^ki)=0。这里(ki-m)代表第i堆石头拿走m块剩余的部分,(XOR^ki)代表从XOR中去掉ki这一项,因为一个数连续异或两遍任意数都保持不变。

再来看(ki-m)^(XOR^ki)=0,若两个数异或后结果为0,则说明这两个数相等(每一个比特都相等)。于是ki-m=XOR^ki,也即m=ki-XOR^ki。同时m必须满足1≤m≤ki,所以ki>XOR^ki,如此才能为第i堆石头带来一个可行解。

#include <iostream>
#define MAX_N  1000

int n;
int k[MAX_N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", k + i);
        }

        int XOR = 0;
        for (int i = 0; i < n; ++i)
        {
            XOR ^= k[i];
        }

        int result = 0;
        for (int i = 0; i < n; ++i)
        {
            if (k[i] > (XOR ^ k[i]))
            {
                ++result;
            }
        }
        printf("%d\n", result);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
15544647 hankcs 2975 Accepted 120K 32MS C++ 639B 2016-05-24 09:31:27

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2975 Nim 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机