UVA10368 题解

2023-08-06 15:18:08 solution

双倍经验

这种有限轮游戏的博弈通常都是有两种状态，必胜态和必败态。

对于必胜态，指的是从它可以转移到必败态。

对于必败态，指的是从它不论如何只能转移到必胜态。

对于每个玩家都采取最优策略的有限游戏，我们通常只需要关注必胜态与必败态之间的转移即可得到先手必败或者先手必胜的结论。

回到这题，因为两个数有大小关系，我们不妨令 \(x\ge y\)。

当 \(x<2y\)，只能转移到下一个状态 \((x-y,y)\)。

当 \(x\ge 2y\) 时，出现了多个可能的状态。令 \(\lfloor\frac{x}{y}\rfloor=k\)。

对于状态 \((x-ky,y)\)，它只有两种可能：必胜态或者必败态。

若为必败态，显然当前状态为必胜态。

若为必胜态，由于 \((x-(k-1)y,y)\) 只能转移到 \((x-ky,y)\)，那么 \((x-(k-1)y,y)\) 为必败态，而当前状态可以转移到 \((x-(k-1)y,y)\)，所以当前状态为必胜态。

综上，对于所有 \(x\ge 2y\) 的情况，都是必胜态，剩下的状态因为只有一种转移，我们只需要递归求解即可，考虑到每次 \(x\) 至少减小一半，所以最劣复杂度为 \(O(\log x)\)。

\(Code\)

bool check(long long x,long long y){
    if(x==y)return 1;
    if(x<y)x^=y^=x^=y;
    if(x<(y<<1))return check(x-y,y)^1;
    return 1;
}
int main(){
    for(long long x=read(),y=read();x+y>0;x=read(),y=read()){
        if(check(x,y))puts("Stan wins");
        else puts("Ollie wins");
    }
}