链接：https://ac.nowcoder.com/acm/contest/549/I
来源：牛客网
小A也听说了取石子这个游戏，也决定和小B一起来玩这个游戏。总共有n堆石子，双方轮流取石子，每次都可以从任意一堆中取走任意数量的石子，但是不可以不取。规定谁先取完所有的石子就获胜。但是小A实在是太想赢了，所以在游戏开始之前，小A有一次机会，可以趁小B不注意的时候选择其中一堆石子拿走其中的k个，当然小A也可以选择不拿石子。小A先手。双方都会选择最优的策略，请问在这样的情况下小A有没有必胜的策略，如果有输出YES，否则就输出NO。
思路：Nim游戏的模板题 枚举每一堆，判断取走后能否使必胜（维护前缀异或L数组和后缀异或R数组） 判断 L[i - 1] ^ x ^ R[i + 1] != 0(必胜） #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int a[maxn]; int L[maxn], R[maxn]; int main() { int n, k; cin >> n >> k; int ans = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; ans ^= a[i]; } for (int i = 1; i <= n; i++) { L[i] = L[i - 1] ^ a[i]; } for (int i = n; i >= 1; i--) { R[i] = R[i + 1] ^ a[i]; } if (ans != 0) { cout << "YES" << endl; return 0; } for (int i = 1; i <= n; i++) { if (a[i] >= k) { int x = a[i] - k; if ((L[i - 1] ^ R[i + 1] ^ x) != 0) { cout << "YES" << endl; return 0; } } } cout << "NO" << endl; return 0; }
