【cdc和卫尧的游戏】

2015.07.10 14:02 Fri | 40次阅读 | 旧日oi | 固定链接 | 源码

题目大意:

给出两堆石子,一堆是 x 颗,另一堆是 y 颗,两人轮流取,有
两种规则:
• 在其中一堆取dx 颗,dx > 0;
• 在两堆分别取dx 和dy 颗,dx > 0, dy > 0, |dx − dy| < d
取光石子的人胜,问先手是否必胜?
多组数据 x,y<=10^8,T<=10^4

题解

这是一道博弈论的题。首先我们来确定必败的状态。
当d=1的时候,这种博弈称为威佐夫博弈。
首先(0,0)必败,然后有(ai,bi)必败,a[i]={mex(a[i-1],a[i-2],...a[0],b[i-1],b[i-2]...b[0])},b[i]=a[i]+i;
如何证明呢?
首先我们知道,
1.若(a,b)必败,则(b,a)也必必败。
2.(ai+k,bi)a[i]={mex(a[i-1],a[i-2],...a[0],b[i-1],b[i-2]...b[0])},b[i]=a[i]+i;b)(k!=0)必胜(若k>0,先手可以取k个形成必败态,否则令a+k存在于必败态(ak,bk)中,那么把b取成d对应的一项就行)
由这两个性质我们就可以证明(ai,bi),a[i]={mex(a[i-1],a[i-2],...a[0],b[i-1],b[i-2]...b[0])},b[i]=a[i]+i;是必败局面。因为如果不管先手怎么取,后手都可以把状态变成a0~ai-1中的一个,这个很好证明。
这里的a∪b=Z+,a∩b=空集;
然后推广到d>1的情况,可以猜出必败态是a[i]={mex(a[i-1],a[i-2],...a[0],b[i-1],b[i-2]...b[0])},b[i]=a[i]+i*d;证明和上面类似。
然后怎么搞?又来一个定理:BETTY定理。
设a、b是正无理数且 1/a +1/b =1。记P={ [na] | n为任意的正整数},Q={ [nb] | n 为任意的正整数},([x]'指的是取x的整数部分)则P与Q是Z+的一个划分,即P∩Q为空集且P∪Q为正整数集合Z+。
证明看百度百科吧,很简单。
然后我们设ai=i*x,bi=i*y,y-x=d且1/y+1/x=1,解出x,y一定是两个只和d有关无理数,然后判断一下给定的(X,Y,d)能否表示成i*x=X,i*y=y就可以了。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long double a,b,c,d;
int T,x,y;
int main()
{
    for(cin>>T;T;T--)
    {
        scanf("%d%d",&x,&y);cin>>d;
        if(y<x) swap(x,y);
        a=(sqrt(d*d+4)+2-d)/2.0;b=a+d;
        c=ceil(x/a);
        if(fabs(floor(c*a)-x)<=1e-12&&fabs(floor(c*b)-y)<=1e-12) puts("lose again");
        else puts("finally win");
    }
}```