http://poj.org/problem?id=2348
顺便说,必应翻译真的好用,比谷歌翻译好用 100 倍.
很难判断这道题的具体博弈类型.
有两种写法,一种是找规律,一种是推理得到关系后循环(或递归)处理.两种写法都能在题目下面的 discuss 中找到.
1. 找规律,我在这里直接复制了 discuss 中大神算出的 sg 函数表(在考试中这种写法是很值得借鉴的,这里就体现出代码能力的重要了,找规律天下第一!).
一下前 30 × 30 的 Sprague-Grundy 函数表,如下:
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
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
--------------------------------------------------------------------------------------------
| 0 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
| 0 2 1 0 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15
| 0 3 0 1 0 1 2 1 2 3 2 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10
| 0 4 2 0 1 0 0 1 2 1 1 2 3 2 3 3 4 3 4 4 5 5 5 5 6 6 6 6 7 7 7
| 0 5 1 1 0 1 0 0 0 1 2 1 2 2 2 3 2 3 3 3 4 3 4 4 4 5 4 5 5 5 6
| 0 6 3 2 0 0 1 0 0 0 1 1 2 1 1 1 2 2 3 2 2 3 3 3 4 3 4 4 4 4 5
| 0 7 3 1 1 0 0 1 0 0 0 0 1 1 2 1 1 2 2 2 2 3 2 2 3 3 3 3 4 3 4
| 0 8 4 2 2 0 0 0 1 0 0 0 0 1 1 1 2 1 1 1 1 2 2 2 3 2 2 3 3 3 3
| 0 9 4 3 1 1 0 0 0 1 0 0 0 0 0 1 1 1 2 1 1 1 2 2 2 2 2 3 2 2 2
| 0 10 5 2 1 2 1 0 0 0 1 0 0 0 0 0 0 1 1 1 2 1 1 1 2 1 2 2 2 2 3
| 0 11 5 3 2 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 2 1 1 1 1 2 2 2 2
| 0 12 6 4 3 2 2 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 2 1 1 1 1 1 1
| 0 13 6 4 2 2 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 2 1 1 1 1
| 0 14 7 4 3 2 1 2 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 2 1 1
| 0 15 7 5 3 3 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2
| 0 16 8 5 4 2 2 1 2 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
| 0 17 8 5 3 3 2 2 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1
| 0 18 9 6 4 3 3 2 1 2 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
| 0 19 9 6 4 3 2 2 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
| 0 20 10 6 5 4 2 2 1 1 2 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
| 0 21 10 7 5 3 3 3 2 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
| 0 22 11 7 5 4 3 2 2 2 1 2 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
| 0 23 11 7 5 4 3 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
| 0 24 12 8 6 4 4 3 3 2 2 1 2 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
| 0 25 12 8 6 5 3 3 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
| 0 26 13 8 6 4 4 3 2 2 2 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
| 0 27 13 9 6 5 4 3 3 3 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0
| 0 28 14 9 7 5 4 4 3 2 2 2 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
| 0 29 14 9 7 5 4 3 3 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0
| 0 30 15 10 7 6 5 4 3 2 3 2 1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1
可以发现 0 的分界线在黄金分割比附近,直接算一个边界就可以了.边界不好看清的话可以上下拖动滚动条.(我大概有病 orz,不过真的能看见,希望大家试试)
代码
1. 根据规则进行推理,在日常写题还是很推荐这种写法的,毕竟博弈论能找到规律的毕竟只是一部分,大部分不用 dp 的博弈论都是相应对策或者必胜选择的推理(个人感受不一定对).
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<ctime>
using namespace std;
const int maxn=1<<13;
int n;
int main(){
long long x,y;
while(~scanf("%lld%lld",&x,&y)){
if(x==0&&y==0)break;
if(x>y)swap(x,y);
long long w=((double)x*2.0/(sqrt(5.0)-1.0));
if(y<=w&&y!=x)printf("Ollie wins\n");
else printf("Stan wins\n");
}
return 0;
}
View Code
记每次一个人开始操作前的两数大的为 y,小的 x.
全程两人都没有选择(每次的情况都满足 y 减去一次 x 就比 x 小)的时候结果是一定的,那么直接循环找出最终胜利者就可以了(显然满足这种条件的时候循环次数不会太多).
假如其中有一个人有选择(y 可以减 n 次小的才比 x 小,n>1)的时候,这个人如果在 y 中取 n 个 x 时必输,这个人就可以在 y 中取 n-1 个 x,那么对方就必输.
于是有了一个循环解决的写法.
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<ctime>
using namespace std;
const int maxn=1<<13;
int n;
int main(){
long long x,y;
while(~scanf("%lld%lld",&x,&y)){
if(x==0&&y==0)break;
if(x>y)swap(x,y);
int w=0;
while(x!=0){
if(y%x==0||y-x>x)break;
y-=x;
w^=1;
if(x>y)swap(x,y);
}
if(w)printf("Ollie wins\n");
else printf("Stan wins\n");
}
return 0;
}
View Code
来源: http://www.bubuko.com/infodetail-2455400.html