中文题。
当尼姆游戏的某个位置:(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; }