BZOJ 1982 [Spoj 2021]Moving Pebbles

发布于 2017-04-08  128 次阅读


题意:给定 n 堆石子,两个人玩游戏,每次任选一堆,拿走一个石头后将任意多个石头移动到其它堆,求必胜方。

对于先手必败的条件是:n 为偶数,且每堆都可以和另一石子数相同的堆配对。

证明如下:

首先对于一个满足上述条件的状态,无论先手如何操作,后手都可以做对称的操作使得维持状态满足上述条件,故先手必败。

当某状态不满足上述条件时,先手都可以用一步操作使得新状态满足上述条件。

  1. 当 n 为奇数,将最小堆与次小堆配对,依此类推,拿空最大一堆去填补配对堆差值,一定能满足上述条件。
  2. 当 n 为偶数,同样配对,用最大堆和其配对堆的差值去填补其它堆的差值,显然也能填补使得其满足上述条件。

故而其他状态先手必胜。

代码:

 


一个非常弱的准退役OIER