POJ2505 (简单博弈,二分,打表)

题意:Stan和Ollie在玩一个乘法游戏,每一局他们都指定一个n,Stan每次都从p=1开始,乘上一个2-9的数字后轮到Ollie对Stan得到的结果做相同的操作,直到p>=n的时候该轮的玩家取得胜利。

这题虽然比较水,但是如果对博弈论中N-p、P-p状态的性质不了解的话可能不能很快地归纳出必胜的结论。
首先我们可以很简单地得到当2≤n≤9的时候,Stan是必胜的,因为他可以操作一次得到这里的任意数。而当10≤n≤18的时候,Ollie是必胜的,因为他可以从Stan的任意一种操作中再操作一次得到这个区间中的任何数字。
接下来我们分析n=19,如果双方足够聪明,那么Stan第一局必出一个2,然后Ollie无论做出什么操作,都不可能得到19,而下一轮Stan可以轻松地乘上一个数字超过19,这里便可以确定19是Stan的下一个必胜区间的下限。这里要强调的是,对于一个必胜决策,一旦某一方处于必败态,那么无论他做出什么操作,之后都不可能取得胜利,基于这一点对于我们推出之后的获胜区间很关键。为了使Ollie做出什么操作都不可能胜利,我们可以推倒出下一个Stan的必胜区间上限应该为9*2*9,因为为了得到162,知道Ollie会尽可能阻止他,Stan唯一的方案就是第一回合出9,否则第二回合Ollie只要出2,那么Stan便无论做什么也得不到162了,这个决策就不属于一个必胜的决策。必胜区间的上线必须基于最坏的情况考虑,然后基于最坏的情况作出下一回合的最有决策。
基于上述的思路,我们就可以继续推倒出Stan的必胜区间为[9^n+2^(n-1)+1,9^n+2^n],而Ollie的必胜区间则为[9^n+2^n+1,9^(n+1)+2^n]。
根据区间打表之后再进行二分搜索所在区间究竟是谁必胜,我们就可以得到问题的解了。


给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;
int i;
struct node
{
long long lower;
long long upper;
int swin;
}table[16];
void inittable()
{
table[1].lower=2;
table[1].upper=9;
table[1].swin=1;
table[2].lower=10;
table[2].upper=18;
table[2].swin=0;
for(i=3;;++i){
table[i].lower=table[i-1].upper+1;
if(i%2) {
table[i].swin = 1;
table[i].upper = table[i-1].upper * 9;
}
else {
table[i].swin = 0;
table[i].upper = table[i-1].upper * 2;
}
if(table[i].upper>=4294967295)
break;
}
};
int binsearch(long long n)
{
int l=1;
int r=i;
while(l<=r){
int mid=(l+r)/2;
if(table[mid].lower<=n && n<=table[mid].upper)
return table[mid].swin;
else if(n<table[mid].lower) r=mid-1;
else l=mid+1;
}
return -1;
}
int main() {
long long n;
inittable();
while(cin>>n) {
if(binsearch(n))
cout<<"Stan wins."<<endl;
else
cout<<"Ollie wins."<<endl;
}
return 0;
}

运行结果为: