ACM-尼姆博弈之取(m堆)石子遊戲——hdu2176

取(m堆)石子遊戲

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1486    Accepted Submission(s): 865

Problem Description m堆石子,兩人輪流取.隻能在1堆中取.取完者勝.先取者負輸出No.先取者勝輸出Yes,然後輸出怎樣取子.例如5堆 5,7,8,9,10先取者勝,先取者第1次取時可以從有8個的那一堆取走7個剩下1個,也可以從有9個的中那一堆取走9個剩下0個,也可以從有10個的中那一堆取走7個剩下3個.   Input 輸入有多組.每組第1行是m,m<=200000. 後面m個非零正整數.m=0退出.

  Output 先取者負輸出No.先取者勝輸出Yes,然後輸出先取者第1次取子的所有方法.如果從有a個石子的堆中取若幹個後剩下b個後會勝就輸出a b.參看Sample Output.

  Sample Input

2
45 45
3
3 6 9
5
5 7 8 9 10
0
        

  Sample Output

No
Yes
9 5
Yes
8 1
9 0
10 3
        

  Author Zhousc   Source ECJTU 2008 Summer Contest   題目： http://acm.hdu.edu.cn/showproblem.php?pid=2176

又是一道尼姆博弈。 這根當初做 威佐夫博弈 一樣，先是做個簡單的判斷，然後就是将非奇異态變成奇異态。 這道題也是改變成奇異态，輸出将哪個數字變成哪個數字。 判斷是否為尼姆博弈，可戳：http://blog.csdn.net/lttree/article/details/24874819 主要就是如何改變：

若a1^a2^...^an!=0，一定存在某個合法的移動，

将ai改變成ai'後滿足a1^a2^...^ai'^...^an=0。

若a1^a2^...^an=k，則一定存在某個ai，

它的二進制 表示在k的最高位上是1（否則k的最高位那個1是怎麼得到的）。

這時ai^k<ai一定成立。

則我們可以将ai改變成ai'=ai^k，此時a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

然後，從第一個位置開始周遊找  ai>ai^k 的情況就可以了。

/**************************************
***************************************
*        Author:Tree                  *
*From :http://blog.csdn.net/lttree    *
* Title : 取(m堆)石子遊戲            *
*Source: hdu 2176                     *
* Hint  : 尼姆博弈                   *
***************************************
**************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[200001];
int main()
{
    int n,i,t,temp;
    while( scanf("%d",&n) && n )
    {
        temp=0;
        for(i=0;i<n;++i)
        {
            scanf("%d",&arr[i]);
            temp^=arr[i];
        }

        if( temp==0 )   printf("No\n");
        else
        {
            printf("Yes\n");
            for(i=0;i<n;++i)
            {
                t=temp^arr[i];
                if( t<arr[i] )
                    printf("%d %d\n",arr[i],t);
            }
        }
    }
    return 0;
}