这道题的题意BZ和POJ上的都不大清楚...
大概就是给出n堆石子,以及初始每堆石子的个数
两个玩家交替操作,每个操作可以任意在一堆中取任意多的石子
然后再从这堆里拿若干个石子放到某个当前还存在的堆里,当然这个操作也可以不做
问先手还是后手有必胜策略
博弈的题目果然是脑洞大啊...
最后的结论:
对于奇数堆,先手必胜
偶数堆时,先手败当且仅当所有的堆都可以分成两两相等的堆
证明大概就是:
首先考虑1堆的情况,先手显然胜
考虑两堆且相等的情况,如果先手拿完,后手把剩下一堆拿完;如果先手没拿完
后手就在另一堆里重复和先手一模一样的操作直至结束
这样后手有必胜的策略
并且对于每两堆相等的堆,后手都会这样做
于是我们可以完全忽略这些堆
然后对于两堆不相等的情况,先手可以在一次操作内将两堆变成相等的两堆,转化成上面的必败态
这样先手必胜
对于三堆的情况,先手可以在一次操作内将三堆变成相等的两堆,同上
(无视上面这张图)
现在的理解大概就是移动的操作一次可以做无限次
然后先手就可以一步把目前形势转化到两两相等的情况
然后就没了
30/.April