hdu1850(nim博弈)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1850

题意：中文题诶～

思路：nim博弈

可以将本题抽象成一般nim博弈，那么有：

1. 对于所有元素异或值为0的情况为P局面

2. 若a1^a2...^ai...^an=m!=0，那么一定存在一个ai'使得a1^a2...^ai'...^an=0；不难算出ai'=num^ai；

即只要我们能将ai变成num^ai，那么对手将面对P局面；又从游戏规则可知ai'<ai(要从ai中拿掉一定数目的牌变成ai')；

所以我们需要做的就是统计num^ai<ai的数目啦；

代码：

 #include <iostream>

 #define MAXN 1010

 using namespace std;

 int a[MAXN];

 int main(void){

     int n;

     while(cin >> n&&n){

         int ans=;

         for(int i=; i<n; i++){

             cin >> a[i];

             ans^=a[i];

         }

         if(!ans){

             cout <<  << endl;

         }else{

             int num=;

             for(int i=; i<n; i++){

                 if((ans^a[i])<a[i]){

                     num++;

                 }

             }

             cout << num << endl;

         }

     }

     return ;

 }

巴特西

hdu1850(nim博弈)

最新文章

热门文章