取(m堆)石子游戲

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1466 Accepted Submission(s): 853

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

解題思路：

本題和前面寫的那題思路是一樣的。求出在第i堆取完石子後應該剩下多少個 與其它堆相異或等於0，這是留給對手的是必敗態，所以只要求出其它堆的異或值就好了，因為兩個相同的數異或以後才是0,。注意：大於10000的數據輸入要用scanf啊，不然會超時。

代碼：

#include 
#include 
using namespace std;
int n,num[200002];

int main()
{
    while(cin>>n&&n)
    {
        int s=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            s^=num[i];
        }
        if(s==0)//必敗態
        {
            cout<<"No"<left)
            {
                printf("%d %d\n",num[i],left);
            }
        }
    }
    return 0;
}