6
HDU1850 Being a Good Boy in Spring Festival（尼姆博弈）
source link: https://arminli.com/hdu1850/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1850 Being a Good Boy in Spring Festival（尼姆博弈）
March 08, 2016
当尼姆游戏的某个位置：（x1,x2,x3），当且仅当其 x1⊕x2⊕x3 = 0（也就是各部分的异或为 0）)当前位置为必败点，这对于多个堆的情况同样适用。
我们先求出所有堆异或后的值，再用这个值去对每一个堆进行异或，令 res = x1⊕sum(sum 为所有堆的或异值)（这时相当于没有考虑 x1 这堆）
如果 res < x1 的话，当前玩家就从 x1 中取走（x1-res）个，使 x1 剩下 res 这样必然导致所有的堆的异或值为 0，也就是必败点，这就是一种方案 遍历每一个堆，进行上面的断判就可以得到总的方案数。 注意一个必败点不可能导致另一个必败点，因为如果这样的话当前这个必败点就不是必败点了，所以这里对于每个堆的操作至多只有一种方法可以导败必败点，如果 res > x1 的话就无论从这个堆取走多少都不可能导致必败点。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int a[102];
int main(){
//freopen("a.txt", "r", stdin);
int n;
while(cin >> n && n){
int sum = 0;
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
sum ^= a[i];
}
int s, ans = 0;
for(int i = 0; i < n; i++){
s = sum^a[i];
if(s<a[i]) ans++;
}
cout << ans << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK