题解 P4018 【Roy&October之取石子】

· · 题解

博弈论题首先找规律

首先0个石子的状态一定是必败态，因为对面在上一轮已经拿完了。

观察1~5个石子，发现1=p^0,2=2^1,3=3^1,4=2^2,5=5^1，都是必胜态，可以一次拿完赢得游戏。

然后6个石子没办法一下拿完（因为6\neq p^k）。可以知道只能拿1~5个石子，这样都会转移到前面的必胜态，只不过这个必胜态已经是对面的了，所以说6个石子是你的必败态，在你面前出现6个石子又轮到你拿的时候，你必定失败。

这样一直往后找到12的时候，发现7~11都是必胜态（一次把石子总数拿到6个石子然后对面就输了），而12是必败态（可以枚举1~12中的所有p^k，都转移到对面的必胜态）。

于是猜想所有6n的状态是必败态，其余所有状态(6n+1,6n+2 \ldots 6n+5)都是必胜态。

我们采用数学归纳法证明：

当n=0时，结论成立，因为0~5上面已经说明过了。

现在假设0~6n-1都满足结论。

先证明6n为必败态：因为任何p^k，都不是6的倍数，所以6n个石子拿完一次不会还是6的倍数，故必定转移到对面的必胜态，所以6n是必败态。

显然6n+r(r=1,2 \ldots 5)只需要拿掉r便可以转移到6n，是对面的必败态，所以6n+r(r=1,2 \ldots 5)是必胜态。

证毕。

代码，只需要判一下输入是否是6n即可：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T,x;
    for(scanf("%d",&T);T;T--){
        scanf("%d",&x);
        puts(x%6==0?"Roy wins!":"October wins!");
    }
    return 0;
}