UVA12293题解

· · 题解

题意

有两个盒子，第一个盒子有 n 个球， 第二个盒子有 1 个球。每次将少的那一个清空，从另一个盒子哪任意数量的球到被清空的盒子里，使两个盒子都至少有 1 个球，不能操作者输。判断先手能必胜，还是后手能必胜。

思路

这是一道博弈论的题,由于 2≤n≤10^9，在程序中直接推导 SG 函数是不可行的，但我们可以先算几个来找规律。

先定义一下状态。盒子有两个，但明显少的那个盒子没有任何作用，因为下一步它就会被清空。所以我们定义状态为数量多的的盒子中的球数。 如此一来，每个状态 x 的后继状态集合是 \{a\vert a \in \mathbf{N} ,x/2≤a<x\}。

用一下代码可以递推出 1 到 30 的 SG 值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int SG[35],vis[35];
    SG[1]=0;
    cout<<SG[1];
    for(int i=2;i<=30;i++){
        memset(vis,0,sizeof(vis));
        for(int q=i-1;q*2>=i;q--) vis[SG[q]]=1;
        for(int q=0;;q++) if(!vis[q]){
            SG[i]=q;
            break;
        }
        cout<<" "<<SG[i];
    }
    return 0;
}

得到结果：

0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

可以发现，当 x 是偶数，SG(x)=x/2，当 x 是奇数，SG(x)=SG(int(x/2))。这样问题就解决了。

AC代码

#include<bits/stdc++.h>
using namespace std;
bool sg(int n){
    return n%2 ? sg(n/2) : n/2;
}
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        if(sg(n)) cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
}