「LuoguP2252」 取石子游戏(威佐夫博弈
题目背景
无
题目描述
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
输入输出格式
输入格式:
输入共一行。
第一行共两个数a, b,表示石子的初始情况。
输出格式:
输出共一行。
第一行为一个数字1、0或-1,如果最后你是胜利者则为1;若失败则为0;若结果无法确定则为-1。
输入输出样例
说明
[数据范围]
50%的数据,a, b <= 1000
100%的数据,a, b <= 1 000 000 000
题解
裸的威佐夫博弈。
威佐夫博弈(Wythoff's game):有两堆各若干个物品,两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。 ——百度百科
在威佐夫博弈中,有这样一种性质:
若当前为一个奇异局势,则先手必败;否则先手必胜。
其中奇异局势,是这样的一系列数对——
$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20)......$
观察可得,若设第$k$组奇异局势为$(a[k],b[k])$的话,那么有:
$1. b[k]==a[k]+k$
$2. a[k]$为这之前未出现过的数中最小的一个。
奇异局势有如下性质:
$1.$任何自然数都包含在一个且仅有一个奇异局势中。
由于$a[k]$是未在前面出现过的最小自然数,所以有$a[k] > a[k-1] $,而 $b[k]= a[k] + k > a[k-1] + k > a[k-1] + k - 1 = b[k-1] > a[k-1]$ 。所以性质$1$成立。
$2.$任意操作都可将奇异局势变为非奇异局势。
事实上,若只改变奇异局势$(a[k],b[k])$的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。如果使$(a[k],b[k])$的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
$3.$采用适当的方法,可以将非奇异局势变为奇异局势。 ——百度百科
要么保持$x$不变,把$y$减到$x$对应的$a[k]$;
要么保持$x$不变,把$y$减到$x$对应的$b[k]$;
要么把$x$和$y$一起减到$a[y-x],b[y-x]$,
总有一种适合你。
根据奇异局势的定义(面对时先手必败),可证若给定局势为奇异局势,先手必败;
而根据性质$3$,可知若给定局势不是奇异局势,先手可以用一步操作把其变为奇异局势。所以若给定局势不是奇异局势,则先手必胜。
——————
但是递推去求每一个奇异局势的话还是复杂度太高了QAQ
根据一系列推演,可以得到$a[k]$和$b[k]$是一个叫Beatty序列的东西。
证明我也看不懂呐,就当结论记吧QAQ
$a[k]=k*\frac{\sqrt{5}+1}{2},b[k]=a[k]+k$
而且这是一个计算机也能用的公式!(不像Fibonacci通项公式一样因为精度问题不能用QAQ
所以此题解决√
/*
qwerta
P2252 取石子游戏
Accepted
100
代码 C++,0.27KB
提交时间 2018-10-01 20:15:45
耗时/内存
28ms, 812KB
*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
int main()
{
LL a,b;
cin>>a>>b;
if(a>b)swap(a,b);
LL x=((double)(b-a)*(sqrt(5.0)+1.0)*0.5);
if(x==a)cout<<;
else cout<<;
return ;
}
最新文章
- VC中预处理指令与宏定义详解
- ISO-8859-1
- dropdownlist分页
- 关于Http协议的解析
- JS 自定义回调函数callback
- 6--OC--封装 继承 多态
- Unity 坐标 转换 详解 World世界坐标 Screen屏幕坐标 View视口坐标 GUI坐标 NGUI坐标 localPosition相对父级坐标
- 02_3中方式的反射,通过Class.forName获得Class对象,通过类.class获得字节码对象,通过类实例.getClass()的方式获得Class对象
- Socket编程实践(5) --TCP粘包问题与解决
- Jmeter——HTTP协议的接口压力测试环境搭建
- ubuntu 精简配置
- 吐槽下mac的打印机设置
- BZOJ5093 图的价值(NTT+斯特林数)
- IIS Web 服务器/ASP.NET 运行原理基本知识概念整理 转
- 匿名内部类的参数引用只能是final,可能遇到的问题及其解决
- P2258 子矩阵
- AndroidArchitecture
- ios framework 使用图片资源
- [Luogu 3966] TJOI 2013 单词
- 树莓派编译安装 EMQ 服务器
热门文章
- chm 转 pdf 工具推荐与对比
- win7 更改同步时间的网址
- linux 中两个文档怎么对比内容是否一致
- Win7安装软件,界面上中文显示乱码的解决方案
- CentOS 7.2 , YUM 方式安装VSC
- Python Journey
- TFS 解除独占锁定
- jni集成第3方third party动态库libwebrtc_audio_preprocessing.so时android.mk的编写
- iOS8中提示框的使用UIAlertController(UIAlertView和UIActionSheet二合一)
- 登录和注册(Js)的写法