nim游戏
给定n堆物品,第i堆物品有Ai个,两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一件物品的人获胜。
定理:nim游戏先手必胜,当且仅当A1 xor A2 xor … xor An != 0
xor 不进位加法
从无到有的过程是最难的,nim游戏是困扰了多少代人的难题!
定理证明(参考算阶)
#include <iostream>
using namespace std;
int main()
{
int n;cin >> n;
int res = 0;
while(n --)
{
int x; cin >> x;
res ^= x;
}
if(res) puts("Yes");
else cout << "No" << endl;
return 0;
}
Mex运算
Mex运算就是除去本身以外其他非负整数的集合中的最小值,如MEX{1}=0,MEX{0,1,2,4,5}=3
SG函数
在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,···,yk,定义SG(x)为x的后继结点y1,y2,···,yk的SG函数值构成的集合再执行Mex运算的结果,即:
SG(X) = mex({SG(y1), SG(y2),···, SG(yk)})
多个SG游戏的最终结果为每个SG函数值的异或和,异或和为0即为必败点,反之为必胜点
- 集合-Nim游戏
题目
提交记录
讨论
题解
视频讲解
给定 n
堆石子以及一个由 k
个不同正整数构成的数字集合 S
。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S
,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 k
,表示数字集合 S
中数字的个数。
第二行包含 k
个整数,其中第 i
个整数表示数字集合 S
中的第 i
个数 si
。
第三行包含整数 n
。
第四行包含 n
个整数,其中第 i
个整数表示第 i
堆石子的数量 hi
。
输出格式
如果先手方必胜,则输出 Yes。
否则,输出 No。
数据范围
1≤n,k≤100
,
1≤si,hi≤10000
输入样例:
2
2 5
3
2 4 7
输出样例:
Yes
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110, M = 10010;
int n, k;
int s[N], f[M];
//用记忆化搜索实现求sg函数
int sg(int x)
{
//定义一个哈希表存x能到达的所有状态
unordered_set<int>S;
//如果当前状态已经到达过了,我们就直接返回,保证每个状态只到达过一次,这样便能保证每个状态不会重复搜索
if(f[x] != -1) return f[x];
//枚举当前状态能到达的所有状态也就是当前结点的所有后继节点
for(int i = 0; i < n; ++ i)
{
int t = s[i];
if(x - t >= 0) S.insert(sg(x - t));
}
//对当前x的所有后继结点进行mex操作
for(int i = 0; ; ++ i)
if(!S.count(i)) return f[x] = i;
}
int main()
{
cin >> n;
memset(f, -1, sizeof f);
for(int i = 0; i < n; ++ i) cin >> s[i];
cin >> k;
int res = 0;
while(k --)
{
int x;cin >>x;
res ^= sg(x);
}
if(res) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
原文地址:http://www.cnblogs.com/cxy8/p/16844933.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性