【HDU 2176】 取(m堆)石子游戏

【题目链接】

           

【算法】

           Nim博弈

           当石子数异或和不为0时，先手必胜，否则先手必败

           设石子异或和为S

           如果S xor ai <= ai，那么，第一步就可以从第i堆石子中取走(S xor ai)个石子

【代码】

           

#include<bits/stdc++.h>
using namespace std;
#define MAXM 200010

int i,m,k,sum;
int a[MAXM];

int main() 
{
        
        while (scanf("%d",&m) && m)
        {
                sum = 0;
                for (i = 1; i <= m; i++)    
                {
                        scanf("%d",&a[i]);
                        sum ^= a[i];        
                }    
                if (sum != 0)
                {
                        printf("Yes\n");
                        for (i = 20; i >= 0; i--)
                        {
                                if (sum & (1 << i))
                                {
                                        k = i;
                                        break;
                                }
                        }
                        for (i = 1; i <= m; i++)
                        {
                                if ((sum ^ a[i]) <= a[i])
                                        printf("%d %d\n",a[i],sum^a[i]);
                        }
                } else printf("No\n");
        }
        
        return 0;
    
}