求讲解博弈题

地板上有k堆石子，选择一堆石子，从中拿走若干个（至少一个），并可以把剩下的这堆石子拿若干（或全部）自由分到其他堆石子（包括原来没有石子的"堆"，而且可以同时分配石子给若干堆）。
谁如果取走最后一个石子，谁就赢了。
问先手是否有必胜策略
题目出处：https://vijos.org/p/1298

难道没有哪位大神犇可以来指点一下吗？。。。

如果堆数为偶数,并且满足排序后a2i=a2i-1，那么后手必胜,否则先手必胜

证明：
如果堆数为偶数,并且满足排序后a2i=a2i-1。
那么后手必胜理由显然。
下面证明如果不满足以上条件，一次移动后一定能移动到后手必胜态。
不妨假设给定的石头均排好序：a[i]<=a[i+1]
显然a[n]=sigma (a[i]-a[i-1] )
所以a[n]>sigma (a[2i]-a[2i-1])
所以我们可以把第n块取走a[n]-sigma (a[2i]-a[2i-1])块后，分给每个a[2i-1] 以a[2i]-a[2i-1]的石头,从而得到后手必胜态

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

11回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六