自己做的网站怎么加入微信支付,长沙网业公司,池州市建设管理处网站,微网站开发 课程标准N i m Nim Nim游戏 n n n堆物品#xff0c;每堆有 a i a_i ai个#xff0c;每个玩家轮流取走任意一堆的任意个物品#xff0c;但不能不取#xff0c;取走最后一个物品的人获胜。 N i m Nim Nim游戏是一种经典的公平组合游戏。现在对它进行分析。
首先定义两个博弈中的状… N i m Nim Nim游戏 n n n堆物品每堆有 a i a_i ai个每个玩家轮流取走任意一堆的任意个物品但不能不取取走最后一个物品的人获胜。 N i m Nim Nim游戏是一种经典的公平组合游戏。现在对它进行分析。
首先定义两个博弈中的状态
必胜状态先手必胜的状态。必败状态先手必败的状态。
对于这两个状态我们可以知道
没有后继状态的状态必然是必败状态。在这个状态中先手的是败者因为他无法通过操作将游戏进行下去了。一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。在这个状态中先手的人可以通过一次操作让对手在必败状态中先手。一个状态的所有后继状态均为必胜状态那么这个状态为必败状态。在这个状态中先手无法避免让对方在必胜状态中先手。
回到 N i m Nim Nim游戏
在 N i m Nim Nim游戏中一个很显然的必败状态就是所有物品堆中物品的数量都为 0 0 0即 [ 0 , 0 , . . . , 0 ] [0, 0, ..., 0] [0,0,...,0]。这个状态也是最终态。可以知道在最终态时所有物品堆中的物品数量的异或和是等于 0 0 0的我们不妨假设状态和物品数量的异或和有关系。
证明有关
一个非 0 0 0的异或和产生最高位的 1 1 1总需要有奇数个数字来提供对应位置的 1 1 1。而我们为了消去这个 1 1 1可以选择任意一个提供这个 1 1 1的数字使其二进制中该位上的数字为 0 0 0,而且修改最高位为 0 0 0后得到的数字永远小于原来的数字也就是说我们可以任意修改其他位上的数字从而使得全部物品数量的异或和为 0 0 0。
而对于一个为 0 0 0的异或和假设存在一个 b ̸ a i b \not a_i bai使得我们将 a i a_i ai修改为 b b b后异或和还是为 0 0 0则有 0 ⊕ a i ⊕ b 0 0 \oplus a_i \oplus b 0 0⊕ai⊕b0为了使这个式子成立 b b b就要等于 a i a_i ai与假设违背。
换句话说对于一个物品数量异或和不为 0 0 0的状态我们可以通过一次操作将物品数量的异或和修改为 0 0 0而对于一个物品数量异或和为 0 0 0的操作我们无法只通过一次操作保持物品数量的异或和不变。
从上可以得出在 N i m Nim Nim游戏中物品数量异或和为 0 0 0的状态是必败状态物品数量异或和不为 0 0 0的状态是必胜状态。
接下来看例题
【模板】Nim 游戏
【模板】Nim 游戏
题目描述
甲乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的地上有 n n n 堆石子每堆石子数量小于 1 0 4 10^4 104每人每次可从任意一堆石子里取出任意多枚石子扔掉可以取完不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手且告诉你这 n n n 堆石子的数量他想知道是否存在先手必胜的策略。
输入格式
本题有多组测试数据。
第一行一个整数 T T T T ≤ 10 T\le10 T≤10表示有 T T T 组数据
接下来每两行是一组数据第一行一个整数 n n n表示有 n n n 堆石子 n ≤ 1 0 4 n\le10^4 n≤104。
第二行有 n n n 个数表示每一堆石子的数量.
输出格式
共 T T T 行每行表示如果对于这组数据存在先手必胜策略则输出 Yes否则输出 No。
样例 #1
样例输入 #1
2
2
1 1
2
1 0样例输出 #1
No
Yes根据刚才的推论我们只需要计算所有数字的异或和就可以得出先手时处在必胜状态还是必败状态。用 O ( n ) O(n) O(n)的复杂度即可得出最后的胜负结果。
#includebits/stdc.h
using namespace std;void solve()
{int n; cin n;int ans 0;for(int i 1; i n; i){int x; cin x;ans ^ x;}cout (ans ? Yes : No) \n;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _; cin _;while(_--) solve();return 0;
}
