POJ1740 A New Stone Game

我其实十分惧怕博弈问题,因为碰到这种问题会完全没有思路。这道威武的题目出自楼教主之手,被列入男人八题之列。在网上稍稍查找了一下题解,有了点灵感。

问题可以从小情况开始考虑:

  • 只有一堆石子。那么先手想要赢,直接把所有的石子都拿走,这样后手就没有石子拿了。
  • 两堆石子。先手想要赢,就不能只留一堆石子给对方,而要让对方只留一堆石子给自己。先手会输的情况会发生在1 1,因为无论取哪堆石子,都一定会取完,而且只留了一堆给对方。再考虑多一点石子的情况,只要两堆石子一样多,无论先手取多少,分配多少,一定会导致两堆石子不一样多,而后手就可以把两堆石子恢复到一样多;而先手一定不会希望取完其中一堆,但是每次又必须取,最后一定会逼到1 1的情况,先手卒。反过来,如果一开始两堆石子不一样多,那么先手必胜。
  • 多于两堆的情况
    • 先考虑比较特殊的。假如说给先手的石子是偶数堆,而且石子堆里石子的数目两两相同,那么就可以看作是上面一种情况多次出现在这个游戏里面,对于每一个这样的子游戏,先手都一定会输,而且输了一个子游戏之后在其他的游戏里面还是先手。这种情况下,先手必输。
    • 假如说有偶数堆,但是没有出现上面的那种情况,为了让对方必输,需要将现在这种情况转换成上面那种情况。将石子按数量排序,从最多的那堆里面取,将排名2和3,4和5,……这样下去的几对石子堆补齐成两两相同,最后取走石子直到剩下的数量最小的那堆数量一样,也组成了一对数量相同的石子堆。这种情况,我们把最多的石子堆分配给其他的石子堆,很容易证明一定是够分配出上面提到的那种必输的情况的。那么这种情况就是先手必赢了。
    • 奇数堆可以考虑成上面这种情况中最小的那堆为0,一样能够转化成先手必输的情况。所以这种情况先手一样必赢。

总结上面的各种情况,只要满足堆数为偶数堆,且两两相同,那么先手必输,其他情况先手必胜。

参考AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[10],n;
inline bool judge(){
    if(n%2){
        return true;
    }
    sort(a,a+n);
    for(int i=0;i<n;i+=2){
        if(a[i]!=a[i+1]){
            return true;
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    while(n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        cout<<judge()<<endl;
        cin>>n;
    }
}

15763200 sshockwave 1740 Accepted 732K 16MS G++ 413B 2016-07-20 10:02:13

avatar
Kerry Su