这道题的题意BZ和POJ上的都不大清楚...  

  大概就是给出n堆石子,以及初始每堆石子的个数

  两个玩家交替操作,每个操作可以任意在一堆中取任意多的石子

  然后再从这堆里拿若干个石子放到某个当前还存在的堆里,当然这个操作也可以不做

  问先手还是后手有必胜策略

  博弈的题目果然是脑洞大啊...

  最后的结论:

    对于奇数堆,先手必胜

    偶数堆时,先手败当且仅当所有的堆都可以分成两两相等的堆

  

  证明大概就是:

    首先考虑1堆的情况,先手显然胜

    考虑两堆且相等的情况,如果先手拿完,后手把剩下一堆拿完;如果先手没拿完

    后手就在另一堆里重复和先手一模一样的操作直至结束

    这样后手有必胜的策略

    并且对于每两堆相等的堆,后手都会这样做

    于是我们可以完全忽略这些堆

    然后对于两堆不相等的情况,先手可以在一次操作内将两堆变成相等的两堆,转化成上面的必败态

    这样先手必胜

    对于三堆的情况,先手可以在一次操作内将三堆变成相等的两堆,同上

  

[BZOJ1982][POJ1740][Spoj 2021]Moving Pebbles|解题报告-LMLPHP

    (无视上面这张图)

    现在的理解大概就是移动的操作一次可以做无限次

    然后先手就可以一步把目前形势转化到两两相等的情况

    然后就没了

    30/.April

    

   

05-11 22:53