两学一做山西答题网站,做网站大图片,cf网站编程,商城网站解决方案【模板】nim 游戏
题目描述
https://www.luogu.com.cn/problem/P2197
甲#xff0c;乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的#xff1a;地上有 n n n 堆石子#xff08;每堆石子数量小于 1 0 4 10^4 104#xff09;#xff0c;每人每次可从任意一堆石子…【模板】nim 游戏
题目描述
https://www.luogu.com.cn/problem/P2197
甲乙两个人玩 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思路
如果初态为必胜态 a 1 ∧ a 2 ∧ a 3 . . . ∧ a n ! 0 a_1 \land a_2 \land a_3 .. . \land a_n!0 a1∧a2∧a3...∧an!0,则先手必胜。
如果初态为必败态即上式结果为0则先手必败
证明
必胜态一定可以给对手留下一个必败态 s a 1 ∧ . . . ∧ a n ! 0 sa_1 \land ... \land a_n!0 sa1∧...∧an!0,设s的二进制为1的最高位为k
那么一定有奇数个 a i a_i ai的二进制位的第k位为1我们使用 a i ∧ s a_i\land s ai∧s替换 a i a_i ai,那么 a 1 ∧ . . . ∧ a i ∧ s . . . ∧ a n s ∧ s 0 a_1 \land ... \land a_i \land s... \land a_ns \land s0 a1∧...∧ai∧s...∧ans∧s0
同时可以保证 a i ∧ s a i a_i \land sa_i ai∧sai
必败态一定给对手留下必胜态
因为必败态 a 1 ∧ a 2 . . . ∧ a n 0 a_1 \land a_2 ... \land a_n0 a1∧a2...∧an0,看二进制位上面1的个数相同位上面1的个数一定是偶数个因此无论减少哪个数异或和都不为0了即给对手一个必胜态
代码
#include bits/stdc.h#define int long long
using namespace std;signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifint t;cin t;while (t--) {int n, x;cin n;int res 0;while (n--) {cin x;res ^ x;}cout (res ? Yes : No) endl;}return 0;
}取火柴游戏
题目描述
https://www.luogu.com.cn/problem/P1247
输入 k k k 及 k k k 个整数 n 1 , n 2 , ⋯ , n k n_1,n_2,\cdots,n_k n1,n2,⋯,nk表示有 k k k 堆火柴棒第 i i i 堆火柴棒的根数为 n i n_i ni接着便是你和计算机取火柴棒的对弈游戏。取的规则如下每次可以从一堆中取走若干根火柴也可以一堆全部取走但不允许跨堆取也不允许不取。
谁取走最后一根火柴为胜利者。
例如 k 2 k2 k2 n 1 n 2 2 n_1n_22 n1n22A 代表你P 代表计算机若决定 A 先取
A ( 2 , 2 ) → ( 1 , 2 ) (2,2) \rightarrow (1,2) (2,2)→(1,2)即从第一堆中取一根。P ( 1 , 2 ) → ( 1 , 1 ) (1,2) \rightarrow (1,1) (1,2)→(1,1)即从第二堆中取一根。A ( 1 , 1 ) → ( 1 , 0 ) (1,1) \rightarrow (1,0) (1,1)→(1,0)。P ( 1 , 0 ) → ( 0 , 0 ) (1,0) \rightarrow (0,0) (1,0)→(0,0)。P 胜利。
如果决定 A A A 后取
P ( 2 , 2 ) → ( 2 , 0 ) (2,2) \rightarrow (2,0) (2,2)→(2,0)。A ( 2 , 0 ) → ( 0 , 0 ) (2,0) \rightarrow (0,0) (2,0)→(0,0)。A 胜利。
又如 k 3 k3 k3 n 1 1 n_11 n11 n 2 2 n_22 n22 n 3 3 n_33 n33 A A A 决定后取
P ( 1 , 2 , 3 ) → ( 0 , 2 , 3 ) (1,2,3) \rightarrow (0,2,3) (1,2,3)→(0,2,3)。A ( 0 , 2 , 3 ) → ( 0 , 2 , 2 ) (0,2,3) \rightarrow (0,2,2) (0,2,3)→(0,2,2)。A 已将游戏归结为 ( 2 , 2 ) (2,2) (2,2) 的情况不管 P 如何取 A 都必胜。
编一个程序在给出初始状态之后判断是先取必胜还是先取必败如果是先取必胜请输出第一次该如何取。如果是先取必败则输出 lose。
输入格式
第一行一个正整数 k k k。
第二行 k k k 个整数 n 1 , n 2 , ⋯ , n k n_1,n_2,\cdots,n_k n1,n2,⋯,nk。
输出格式
如果是先取必胜请在第一行输出两个整数 a , b a,b a,b表示第一次从第 b b b 堆取出 a a a 个。第二行为第一次取火柴后的状态。如果有多种答案则输出 ⟨ b , a ⟩ \lang b,a\rang ⟨b,a⟩ 字典序最小的答案 即 b b b 最小的前提下使 a a a 最小。
如果是先取必败则输出 lose。
样例 #1
样例输入 #1
3
3 6 9样例输出 #1
4 3
3 6 5样例 #2
样例输入 #2
4
15 22 19 10样例输出 #2
lose提示
数据范围及约定
对于全部数据 k ≤ 500000 k \le 500000 k≤500000 n i ≤ 1 0 9 n_i \le 10^9 ni≤109。
思路
与上一题的Nim游戏一样这里需要特殊输出第一次拿走的数量
代码
#include bits/stdc.h#define int long long
using namespace std;signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifint n;cin n;vectorint a(n 1);int res 0;for (int i 1; i n; i) {cin a[i];res ^ a[i];}if (!res) {cout lose;} else {for (int i 1; i n; i) {if ((a[i] ^ res) a[i]) {cout (a[i] - (a[i] ^ res)) i endl;a[i] a[i] ^ res;break;}}for (int i 1; i n; i) {cout a[i] \n[i n];}}return 0;
}取数游戏 II
题目描述
有一个取数的游戏。初始时给出一个环环上的每条边上都有一个非负整数。这些整数中至少有一个 0 0 0。然后将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏两人轮流取数取数的规则如下 选择硬币左边或者右边的一条边并且边上的数非 0 0 0 将这条边上的数减至任意一个非负整数至少要有所减小 将硬币移至边的另一端。
如果轮到一个玩家走这时硬币左右两边的边上的数值都是 0 0 0那么这个玩家就输了。
如下图描述的是 Alice 和 Bob 两人的对弈过程其中黑色节点表示硬币所在节点。 各图的结果为 A \text{A} AAlice 胜 B \text{B} BBob 胜 C \text{C} CAlice 胜 D \text{D} DBob 胜。 D \text{D} D 中轮到 Bob 走时硬币两边的边上都是 0 0 0所以 Alice 获胜。
现在你的任务就是根据给出的环、边上的数值以及起点硬币所在位置判断先走方是否有必胜的策略。
输入格式
第一行一个整数 N N N ( N ≤ 20 ) (N \leq 20) (N≤20)表示环上的节点数。
第二行 N N N 个数数值不超过 30 30 30依次表示 N N N 条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。
输出格式
仅一行。若存在必胜策略则输出 YES否则输出 NO。
样例 #1
样例输入 #1
4
2 5 3 0样例输出 #1
YES样例 #2
样例输入 #2
3
0 0 0样例输出 #2
NO思路
要么一直顺时针走要么一直逆时针走每次走的时候一定是把这条边减小为0否则对手可以反过来走让你变成失败。
找第一个为0的位置看初始点到这个点要走多少次奇数次则先手获胜。
代码
#include bits/stdc.h#define int long long
#define yes cout YES endl;
#define no cout NO endl;
#define IOS cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
#define cxk 1
#define debug(s, x) if (cxk) cout #debug:( s ) x endl;
using namespace std;void solve() {int n;cin n;vectorint a(n 1);for (int i 1; i n; i) {cin a[i];}int cnt1 0, cnt2 0;for (int i 1; i n a[i]; i, cnt1);for (int i n; i 1 a[i]; i--, cnt2);if (cnt1 1 || cnt2 1) {yes} else {no}
}signed main() {IOS
#ifndef ONLINE_JUDGEfreopen(../test.in, r, stdin);freopen(../test.out, w, stdout);
#endifint _ 1;while (_--) solve();return 0;
}
