http://poj.org/problem?id=1740

规则题目没说明白:可以不移动石子到其他堆中,直接拿走就行,谁先取完谁胜利。

那么怎么讨论呢?
首先看两堆两堆相等的情况,比如n=6时,有x x y y z z这6堆,这时我们用x怎么做,对方就用另一个x同样的做,所以此类情况下先手必败。
知道这个结论后,就可以把n堆中两两相等的堆去掉,讨论去掉后互不相等的堆:

  1. 只有一堆x,先手直接全部取走,必胜;
  2. x y的形式(这里不妨假设递增,下同),先手从第二堆中取走(y-x)个石头,这样两堆相等,后手必败,先手必胜;
  3. x y z的形式,先手从z中直接拿走(z-(y-x))个石头,将剩下(y-x)个石头移到第一堆上,还是先手必胜;
  4. 去掉相等的堆后还剩下奇数个(2k+1)的情况。由于全体相邻两项之差的和必小于最后一个,所以可以用最后一堆凑出k组两两相同的堆,依旧先手必胜,后手苦逼。
  5. 去掉相等的堆后还剩下偶数个(2k)的情况。在开头加一个0个石子的堆就和4一样了。

所以统计堆数个数,若存在某一堆数的数目为奇数,则输出0。

/*0ms,164KB*/

int cnt[105];

int main()
{
    int n, i, x;
    while (scanf("%d", &n), n)
    {
        memset(cnt, 0, sizeof(cnt));
        for (i = 0; i < n; ++i) scanf("%d", &x), ++cnt[x];
        for (i = 1; i <= 100; ++i) if (cnt[i] & 1) break;
        printf("%d\n", i != 101);
    }
    return 0;
}

Comments

comments powered by Disqus