P1290 欧几里德的游戏

原题链接  https://www.luogu.com.cn/problem/P1290

 

题解

模拟赛的一道题，我大眼一看是博弈论的题，想都没想直接跳过（我完全不会博弈论），看了题解之后发现其实并不难；

直接看结论：

记当前状态为 $d(x,y)$ ，且 $x>y$ ，若此时 $x >= 2y$  ，则目前的操作者胜利；

下面是证明：

假定 $x=ky+r$，其中 $r = x \% y$，$k = x / y$ ，根据假设，$k>=2$，此时讨论 $d(y,r)$ 的可能情况：

$1$. 若 $d(y,r)$ 为必胜状态（即当时的操作者有必胜策略），则当前操作者（ 即 $d(y,r)$ 状态下的操作者 ）可以转移到 $d(y+r,r)$（取 $k-1$ 堆小的，由于 $k>=2$，肯定可以取到 ）。

此时，轮到对手操作。因为必须要取正整数堆较小的，所以只能转移到 $d(y,r)$ 这个必胜状态上。那么，当前的操作者胜利。

若 $d(y,r)$ 为必败状态，其实是类似的，可以直接转移从 $d(x,y)$ 至 $d(y,r)$，把必败状态留给后手。

这样，就能把必败状态留给对手，将必胜状态留给自己，那么自己必胜！

这样的话，我们在搜索的时候如果出现 $x >= 2y$ 的情况，则当前的操作者必胜，否则转移到 $d ( x , x - y )$ ；

$Code$：

#include<cstdio>
#include<algorithm>
using namespace std;
int dfs(int x,int y,int p) //p表示当前的操作者，0是先手的人，1是后手的人 
{
    if(x==y) return p;     //当x==y，那么当前操作者必胜 
    if(x>=2*y) return p;   //结论 
    else return dfs(y,x-y,p^1);
}
int n,m,T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);      //保证让第一个是较大的数 
        if(dfs(n,m,1)==0) printf("Ollie wins
");  
        else printf("Stan wins
");
    }
}