P1290 题解

CreeperK · 2018-04-03 22:02:01 · 题解

看到下面有些dalao的证明十分严谨（然而也有点萌新不友好），却也有一些dalao过程不是那么严谨（请原谅我的措辞）。

所以我决定写一篇稍稍平均一点的题解，即尽力做到清楚地解释。

这道题有一个很快的方法。记当前状态为d(i,j)，且i>j，若此时i>=2j，则目前的操作者胜利。下面是证明：

假定i=kj+l，其中l = i % j，k = i div j，根据假设，k>=2，此时讨论d(j,l)的可能情况：

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

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

若d(j,l)为必败状态，其实是类似的，可以直接转移从d(i,j)至d(j,l)，把必败状态留给后手。得证！

因此，在搜索时向后的决策就只有一个了：若i>=2j，则当前操作者胜；反之转移至d(j,i-j)，继续一样的操作。

这种方法的时间复杂度是多少呢？不难发现，当i和j为斐波那契数列的相邻两项时，所需次数最多。得出，复杂度上界略大于O(logn)。肯定是不会炸的！

下面是代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int dfs(int a,int b,int p){//0表先手(1),1表后手(2);
    if(b==a)return 1;//等于也直接胜利
    if(b/a>=2)return 1;//不小于2直接胜利
    else return 1^dfs(b-a,a,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\n");
        else printf("Stan wins\n");
    }
}