BZOJ 1982 [Spoj 2021]Moving Pebbles


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

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

证明如下:

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

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

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

故而其他状态先手必胜。

代码:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1982 [Spoj 2021]Moving Pebbles


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: