首页 > ACM题库 > HDU-杭电 > hdu 2174 Bridged Marble Rings-博弈-[解题报告]C++
2013
12-30

hdu 2174 Bridged Marble Rings-博弈-[解题报告]C++

Bridged Marble Rings

问题描述 :

26 marbles―half yellow and half gray―are distributed between two circles of 13 marbles each. The marbles in each circle can be freely rotated clockwise or counterclockwise. The upper and lower circles are bridged by a smaller circle, which rotates―in the plane of the board―180 degrees, effectively exchanging the three bottommost marbles of the upper circle with the three uppermost marbles of the lower one. The goal is to get all gray marbles to the upper circle and all yellow marbles to the lower one while minimizing the number of times the bridging circle is rotated.

输入:

The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one.

The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

输出:

The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one.

The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

样例输入:

gggggggggggggyyyyyyyyyyyyy
yyyyyggggggggyyyygggggyyyy
gyyygyggyyygyyggyyggggyygg
ygygygygygygygygygygygygyg

样例输出:

0
2
5
6

只是一道NIM(尼姆博弈)题;

尼姆博弈模型,是ACM题中常见的组合游戏中的一种,大致上是这样的:
有3堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取1个,多者不限,最后取光者得胜

这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是必败态,无论谁面对(0,0,0) ,都必然失败;第二种必败态是(0,n,n),自己在某一堆拿走k(k ≤ n)个物品,不论k为多少,对方只要在另一堆拿走k个物品,最后自己都将面临(0,0,0)的局势,必败。仔细分析一下,(1,2,3)也是必败态,无论自己如何拿,接下来对手都可以把局势变为(0,n,n)的情形。

计算机算法里面有一种叫做按位模2加,叫做异或的运算,我们用符号XOR表示这种运算,这种运算和一般加法不同的一点是1 XOR 1 = 0。先看(1,2,3)的按位模2加的结果:
1 = 二进制01
2 = 二进制10
3 = 二进制11  XOR
———————
0 = 二进制00 (注意不进位)
 
对于奇异局势(0,n,n)也一样,结果也是0。
任何奇异局势(a,b,c)都有a XOR b XOR c = 0。

如果我们面对的是一个非必败态(a,b,c),要如何变为必败态呢?假设 a < b < c,我们只要将 c 变为a XOR b,即可。因为有如下的运算结果:
a ^ b ^ (a ^ b)=(a ^ a) ^ (b ^ b) = 0 ^ 0 = 0。
要将c 变为a ^ b,只要对 c进行 c-(a ^ b)这样的运算即可。

尼姆博弈模型可以推广到:有n堆若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这个游戏中的变量是堆数k和各堆的物品数N1,N2,……,Nk。对应的组合问题是,确定先手获胜还是后手获胜以及两个游戏人应该如何取物品才能保证自己获胜(获胜策略)

为了进一步理解Nim取物品游戏,我们考查某些特殊情况。如果游戏开始时只有一堆物品,先手则通过取走所有的物品而获胜。现在设有2堆物品,且物品数量分别为N1和N2。游戏者取得胜利并不在于N1和N2的值具体是多少,而是取决于它们是否相等。设N1!=N2,

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
int num[200024];
int main(  )
{
    int n;
    while( scanf( "%d" ,&n ),n )
    {
        int x = 0;
        for( int i = 0 ; i < n ; i ++ )
        {
             scanf( "%d",&num[i] );
             x ^= num[i];     
        }       
        if( x == 0 ) printf( "No\n" );
        else
        {
            printf( "Yes\n" );
            for( int i = 0; i < n; i ++ )
            {
               int t = x ^ num[i];
               if( t <= num[i] )
               {
                   printf( "%d %d\n",num[i] , t );    
               }     
            }    
        }
    }
    //system( "pause" );
    return 0;
}

 

先手从大堆中取走的物品使得两堆物品数量相等,后手再拿,于是,先手以后每次取子的数量与后手相等而最终获胜。但是如果N1= N2,则:后手只要按着先手拿的数量在另一堆中取相等数量的物品,最终获胜者将会是后手。这样,两堆的取子获胜策略就已经找到了。

现在我们如何从两堆的取子策略扩展到任意堆数中呢?
首先来回忆一下,每个正整数都有对应的一个二进制数,例如:57(10) = 111001(2) ,即:57(10)=25+24+23+20。于是,我们可以认为每一堆物品数由2的幂数的子堆组成。这样,含有57枚物品大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。

解题转自:http://www.cnblogs.com/bo-tao/archive/2012/04/16/2452715.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。