Nim 游戏

思路

大家可以去哔哩哔哩·看董晓算法讲的

结论

1.Nim 游戏
当堆数的异或和等于零时，则必败 a₁ ^a₂ ^a₃ ^a₄… ^a_n=0
当堆数的异或和不等于零时，则必胜 a₁ ^a₂ ^a₃ ^a₄… ^a_n!=0
2.台阶型Nim游戏
有n个台阶，第i个台阶有a_i个石子，每次都可以将一些k级台阶石子移到下一台阶，移动到地面（0阶）就不能再移动了
当奇数台阶a₁ ^a₃ ^a₅…!=0时则先手必胜，反之则必败

代码

#include <iostream>
#include <algorithm>
using namespace std;
int t, n, a, sum;

int main() {
	cin >> t;
	while (t--) {
		sum=0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a;
			sum ^= a;
		}
		if (sum == 0)
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21