「POJ2505」A multiplication game [博弈论]
程序员文章站
2022-05-10 20:41:02
题目链接:http://poj.org/problem?id=2505 题目大意: 两个人轮流玩游戏,Stan先手,数字 p从1开始,Stan乘以一个2-9的数,然后Ollie再乘以一个2-9的数,直到谁先将p乘到p>=n时那个人就赢了,而且轮到某人时,某人必须乘以2-9的一个数。 解题思路: 这是 ......
题目链接:http://poj.org/problem?id=2505
题目大意:
两个人轮流玩游戏,Stan先手,数字 p从1开始,Stan乘以一个2-9的数,然后Ollie再乘以一个2-9的数,直到谁先将p乘到p>=n时那个人就赢了,而且轮到某人时,某人必须乘以2-9的一个数。
解题思路:
这是一道博弈论的题目。
不过这道题并没有用SG函数相关的知识。
首先我们可以很快判断区间[2,9]必定是先手胜
然后紧接着是区间[10,18]区间是后手胜
然后是什么呢?
[18,??]
我们可以这样来理解:
我们可以考虑一下,先手是要取胜,就是要越大越好,越大越快,
所以每次轮到先手进行操作时,肯定是要乘上最大的哪一个数,也就是9
那么我们反过来,后手就是要尽量拖住先手,所以每一次都会乘上哪一个最小的数,也就是2
于是,这样的话我们就可以将区间补出来:
[2,9]
[9+1,9*2]
[9*2+1,9*2*9]
[9*2*9+1,9*2*9*2]
.......
所以着一道题我们就可以做了吧。
至于怎么操作,我用的方法并不是最快的,但是应该是比较清楚的。
定义l,r为2,9然后按照上面模拟即可,然后每次判断就行
额。。。网上有题解说他们是找规律找出来的,我连找规律都不会找。。。。。推了好久才推出来。。。
无语。。。
贴代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 typedef long long ll; 6 ll n; 7 int main() 8 { 9 while(scanf("%lld",&n)==1) 10 { 11 ll l=2; 12 ll r=9; 13 int flag=1; 14 while(true) 15 { 16 if(n>=l&&n<=r) 17 { 18 if(flag==1) printf("Stan wins.\n"); 19 else printf("Ollie wins.\n"); 20 break; 21 } 22 else{ 23 l=r+1; 24 if(flag==1) 25 { 26 r=r*2; 27 flag=0; 28 } 29 else 30 { 31 flag=1; 32 r=r*9; 33 } 34 } 35 } 36 } 37 return 0; 38 }
谢谢大家支持。
如何可以指出我有哪些写得不好的地方,本人感激不尽!!
上一篇: 3、看源码MVC中的Controllr的Json方法
下一篇: 同事们都投过来一阵敬佩的目光
推荐阅读
-
博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++代码实现
-
POJ2505 A multiplication game(博弈)
-
「POJ2505」A multiplication game [博弈论]
-
I. Game on Plane(SG函数 博弈论)
-
HDU 2147 kiki's game 博弈论
-
基础博弈论之——简单的博弈问题【hdu1525】【Euclid‘s Game】
-
HDU 2147 kiki‘s game 博弈论 巴什博弈 PN图
-
HDU 1730 Northcott Game 博弈论 尼姆博弈
-
POJ2505 A multiplication game(博弈)
-
博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++代码实现