当前位置:网站首页>威佐夫博弈
威佐夫博弈
2022-08-11 11:34:00 【Here_SDUT】
描述
有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。
分析
我们用(a,b)来表示某个时刻两堆石子的数量,我们先从简单情况进行分析,当石子数为(0,0)时,则游戏结束,上一局的人获胜。
如果现在局面是(1,2),先手有四种取法:
- 第一堆里取1个,得到(0,2),后手可以一次取完,后手获胜。
- 第二堆里取1个,得到(1,1),后手两堆里分别取一个,后手获胜。
- 第二堆里取2个,得到(1,0),后手获胜。
- 第一堆取1个,第二堆去1个,得到(0,1),后手获胜。
从上面的分析可以看到,无论先手怎么拿。后手都有办法获胜,我们将其称为先手必输态,(1,2)就是一个先手必输态。
按照上述的分析方法往下分析我们可以发现:
(0,0,)
(1,2)
(3,5)
(4,7)
(6,10)
(8,13)
(9,15)
(11,18)
等等都是先手必输态。
寻找上面这些必输态的规律,可以发现:每个必输态的两堆石子数的差值是递增且相差1,并且每个状态的第一个数字都是前面所有状态里未出现的最小自然数。并且,每个状态的第一个值等于当前状态的差值乘上黄金分割率(0.618),关于为什么会是黄金分割率,可以看知乎的一篇文章:传送门
例题
时间限制:1000ms 内存限制:65536KiB
三个蒟蒻一台戏
Description
今天,3个蒟蒻很开心,因为要去参加一年一度的 XCPC 诗词大赛,由于经费有限只能选择乘坐火车前往比赛地点。由于路途遥远,无聊的三人决定玩个游戏来消磨时间。由于对骑士精神的追崇,3人决定采取决斗的方式进行游戏(即1v1),另外一个人作为裁判。由于没有事先准备,手上只有一些纸团,三人想出了一个简单的游戏,规则如下:由裁判选取两堆数量任意的纸团,参与游戏的两个人轮流取走纸团,每次有两种取法:
- 在任意的一堆中取走任意多的纸团。
- 在两堆中同时取走任意多的相同数量的纸团。
最后取完纸团的获胜,由于三人都是游戏高手,所以每次都会采取最优的策略,给出两堆纸团的数量,让你判断先手会胜还是会败,如果会胜,给出先手的第一次取纸团的所有方案。注意每回合至少取一个纸团。
Input
多组输入,每行两个非负整数 n 和 m (0 \le n,m\le100000) ,表示两堆纸团的初始个数,n = m = 0 时退出。测试组数不超过100000。
Output
如果先手会败则输出0,否则输出1,并输出第一次取完纸团后两堆剩下的纸团数,先输出小的一堆数量,在输出多的一堆的数量,中间用一个空格分开。如果有多种策略,按照较小一堆的纸团的数量升序排序后输出。
Sample
Input
1 2
5 8
4 7
2 2
646 583
0 0
Output
0
1
3 5
4 7
0
1
0 0
1 2
1
101 164
360 583
399 646
分析
就是模板题,先判断是否为先手必输态,否则就必胜,对于输出策略,就是输出所有可能的必输态,我们假设第一堆纸团数小于第二堆纸团数,一共三种可能:
- 两堆纸团各取相同多的纸团,这种情况两堆纸团的差值是不变的,所有根据差值判断一下是否有合法的必输态即可。
- 第一堆纸团不变,第二堆纸团取若干个,那么只要第二堆纸团数大于第一堆纸团对应的必输态的另外一堆纸团数即可,这里需要注意的是题目要求先输出小的一堆,再输出多的一堆,所以要先判断一下第二堆取完后和第一堆的大小关系。
- 第二堆纸团不变,第一堆纸团取若干个,那么只要第一堆纸团数大于第二堆纸团对应的必输态的另外一堆纸团数即可。
注意点:由于有1e5组样例,每组最大1e5,所以不能暴力找策略,可以用预处理,比如某个必输态为(a,b),那么可以映射出mp[a] = b,mp[b] = a
。注意输出局面时可能会输出重复局面,记得去重,推荐使用set,既可以去重又可以排序。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int mp[maxn];
double C = (1 + sqrt(5.0)) / 2;//黄金分割的更精确表示
void init() {
for (int i = 0; i < maxn; i++) {
int x = i * C, y = x + i;
mp[x] = y;
if (y > maxn) break;
mp[y] = x;
}
}
int main() {
int m, n;
init();
while (cin >> n >> m && n + m) {
set<PII> ans;
if (n > m) swap(n, m);
if ((int)((m - n) * C) == n)
puts("0");
else {
puts("1");
int x = C * (m - n), y = x + (m - n);
if (n - x == m - y && m - y > 0) ans.insert({x, y});
if (mp[m] < n) ans.insert({mp[m], m});
if (mp[n] < m) {
if (mp[n] < n)
ans.insert({mp[n], n});
else
ans.insert({n, mp[n]});
}
for (auto it : ans) {
printf("%d %d\n", it.first, it.second);
}
}
}
return 0;
}
边栏推荐
- 爆赞!阿里P8首次分享出基于Docker的企业级Redis实战开源笔记
- Hugging Face快速入门(重点讲解模型(Transformers)和数据集部分(Datasets))
- requestAnimationFrame的应用
- C# 调用高德地图API获取经纬度以及定位【万字详解附完整代码】
- 去年今日我凭借这份文档,摇身一变成了被BAT大牛们看中的幸运儿
- 七、一起学习Lua 函数
- Grid 布局介绍
- 资本市场做好为工业互联网“买单”的准备了吗?
- Network Security - nmap
- The ceiling-level microservice boss summed up this 451-page note to tell you that microservices should be learned this way
猜你喜欢
《长津湖》和《三十而已》,不及王一博赚钱?
智能恒等于推荐系统
C# 调用高德地图API获取经纬度以及定位【万字详解附完整代码】
BAT "exclusive" Internet giant Android senior engineer interview questions: 174 questions allow you to do the interview
资本市场做好为工业互联网“买单”的准备了吗?
C语言手写魂斗罗(一)
使用神经网络进行医学影像识别分析
What areas of the deep neural network are related to the human brain neural network?
SM5200原厂SOT23-6 500mA 线性锂电子替代芯片
leetcode:373. 查找和最小的 K 对数字
随机推荐
BAT "exclusive" Internet giant Android senior engineer interview questions: 174 questions allow you to do the interview
Uber的20万容器实践:如何避免容器化环境中的 CPU 节流
SH7001单电池恒压线性充电IC
AWS、Splunk和Symantec牵头成立OCSF开放网络安全架构框架
智能恒等于推荐系统
蚂蚁集团开源密码学基础库 BabaSSL 正式更名“铜锁”
EastWave应用:负折射现象实时演示
锂电池充电芯片IC
闪灯芯片银行塔闪灯IC参数应用
【黑马早报】抖音否认与头部主播签对赌协议;阿迪达斯CEO承认在中国犯了错;网易云社交App心遇被指涉黄;联通董事长称5G资费比点外卖还便宜
【项目篇- 项目团队部分怎么写、如何作图?(两千字图文总结建议)】创新创业竞赛项目计划书、新苗国创(大创)申报书、挑战杯创业计划竞赛
基于数据库实现通用异步缓存系统
Typora表格中常用操作
LeetCode69:牛顿迭代法和二分法求解x的平方根
【医学统计学】二项分布
Jmeter性能测试
怎么了
Volatile关键字的作用
[10点公开课]:AV1编码器的优化及其在流媒体和实时通讯中的应用
目标检测学习笔记——paddleDetection使用