2018-河南ACM省赛 Attack City and Capture Territory（尼姆博弈）

桃扇骨 2022-05-23 07:27 111阅读 0赞

##                               Attack City and Capture Territory ##

## 题目描述 ##

The Three Kingdoms period was a relatively famous periodin the history of China. From the Battle of Chibi (AD 211) to the reunificationof China in the Western Jin Dynasty(AD 280). During the period, Cao's WeiState, Liu's Shu State, and Sun's Wu Guo's Three Kingdoms stood together.Therefore, it was called the Three Kingdoms period.

In the last years of the Eastern Han Dynasty, Dong\_ Zspecialized in power , the coalition forces of the world's princes crusadeagainst each other. Among them, Liu\_B and Sun\_Q, who are school students, alsoparticipated in the crusade.

In AD 215 , Liu\_B and Sun\_Q simultaneously attackedJingZhou and directly threatened Dong Z's city. There were N firepower pointson the high wall, each fire point with different s trength Xi . Liu\_B and Sun\_Q looked at the high walls and the stronggates,  they did not attack the city traightaway.  They negotiate  to attack firepower point  alternately. Who breaksthrough the last firepower point, he will win the city.

Because of limited weaponry, weapons of each side canonly attack one firepower at a time. But they can control whether completelydestroy this firepower point or weaken the strength of  firepower point.

Liu\_B has a strong think-tank. After calculation, hefinds out who will attack first , who will more likely win the city .

## 输入 ##

The first line of the inputcontains one integer T, which is the number of  test cases (1<=T<=10).  Each test casespecifies:

\* Line 1:       N                ( 1 ≤ N ≤ 100 )

\* Line 2:      X1 X2… Xn       ( 1 <= Xi<=1000    i=1…. n)

## 输出 ##

For each test case ,  print  “Liu\_B is sure to win.” Or  “Liu\_Bis not sure to win.” ,  suppose Liu\_B first attacks.

## 样例输入 ##

3  
2  
1 3  
2  
3 3  
5  
1 2 3 4 5

## 样例输出 ##

Liu\_B is sure to win.  
Liu\_B is not sure to win.  
Liu\_B is sure to win.

## 题意描述： ##

求出刘备先攻打城门，是否能获胜；两人轮流攻打城门每次最少是一个城门的防御值减一，每次只能打下一个城门的部分防御值或全部防御；最后打下最后一个城门的人获胜。

## 解题思路： ##

此题为随机博弈题目。随机博弈指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：

1〉每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；

2〉如果谁取到最后一枚石子就胜

也就是尼姆博弈（Nimm Game）这种博弈的最终状态是：最后剩下一堆石子，当前取石子的人一次取完剩下的全部石子获胜。当石子剩下两堆，每堆1颗的时候，当前取的人显然必败；再来讨论一种情况，当石子剩下两堆，其中一堆只剩下1颗，另一堆剩下多于1颗石子时，当前取的人只需将多于1颗的那一堆取到剩余1颗，则局面变为刚才提到的必败局面。这个过程就是当前取石子的人如果有必胜策略，那么就迫使局面由必胜局面转化到必败局面，也就是说如果当前的局面是必败局面，那么经过2次取，局面又回到必败局面。无穷下降法不同于反证法之处也在此：在“下降”的过程中，状态一直保持不变（在证明费马猜想n=4的情形时，状态就是该三元组是方程的解）；而在随机博弈过程中，状态即局面，下降的是石子数目，由于石子总数目一直在减少，因此最终会“下降”到终极必败状态：最后一颗石子已经被胜者拿走，当前没有石子剩余。现在的问题是：

1〉确定一个方法（或者称之为一个从某一局面映射集合\{必胜局面，必败局面\}的函数），能够快速判断出当前局面是否为必胜（必败）局面；

2〉是否存在一种满足规则的转化状态方法（或者称之为一个从必胜局面映射到必败局面的函数），满足只要当前不是必败局面，取一次后均可以转化到必败局面。

如果仅仅是两堆石子，那么上述两个问题很好解决：

1〉当两堆石子数目相等的时候，当前局面为必败局面，否则为必胜局面，显然，两堆均为0颗是满足这个方法的；

2〉如果当前局面是必胜局面，那么从石子较多的那一堆里面取，使得两堆石子数相等，这样便转化到了必败局面。

然而，对多于两堆石子，1〉可以照旧，但是这样一来2〉远远没有这么简单，因为不太可能取后使得所有堆数目都一样（除非除了石子最多的一堆之外其它所有堆石子数目都相等）。因此需要找一组更加有效的方法，有个叫张一飞的人作过这个研究，他想到的方法是这样的：

1〉把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为0时当前局面为必败局面，否则为必胜局面；

2〉（定理0）一组自然数中必然存在一个数，它大于等于其它所有数按位异或的结果。因此在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。（在网上找的）。

## 程序代码： ##

#include<stdio.h>
    int main()
    {
        int sum,a[1010],i,t,n;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            sum=0;
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            sum=a[1];
            for(i=2;i<=n;i++)
                sum=sum^a[i];
            if(sum==0)
                printf("Liu_B is not sure to win.\n");
            else
                printf("Liu_B is sure to win.\n");
        }
        return 0;
     }