「POJ2505」A multiplication game [博弈论]

2018-06-17 21:13:49来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接: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 }

谢谢大家支持。

如何可以指出我有哪些写得不好的地方,本人感激不尽!!

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:DirectSound---简易Wav播放器

下一篇:CSP201512-1: 数位之和