ATURICS

Viva la Vida


  • Home

  • About

  • Tags

  • Categories

  • Archives

  • Search

「构造博弈」[POJ1740]A New Stone Game

Posted on 2019-10-06 In 题解

$Solution-MashiroSky$

以下证明思路来自$MashiroSky$

  • 首先可以发现,只有一堆石子时先手必胜。

  • 然后,若有两堆数目相同的石子,无论先手做什么,后手在另一堆完成同样的操作,就可以保证胜利。因此后手必胜。

  • 这个结论可以推广到所有偶数堆且两两相等的情况。

  • 而其他情况,都可以通过一步操作变成上面所述的状态。

    • 对于奇数堆,我们需要证明可以用某一堆石子补齐剩余的堆,使它们成对。在这里我们选择最大堆。

    • 将所有石子堆从小到大排序,再与相邻堆两两组队,画出条形统计图,可以发现它们的差值的投影在y轴上组成了不连续的线段,且不会超出$[minheight,maxheight]$。因此一定可以补齐,剩下的扔掉即可。

    • 对于偶数堆,可将最多的一堆拿成和最少的一堆一样多,再与其他堆补齐。

  • 综上所述,当且仅当局面为偶数堆两两相等的石子时,先手必败。

就这样啦QWQ

# 博弈论
「容斥+dp」[CQOI2011]放棋子
NOIP2010初赛部分解析
八聲甘州

八聲甘州

射虎山横一骑,裂石响惊弦。
9 posts
2 categories
4 tags
GitHub Luogu LibreOJ Zhihu
Friend Links
  • tgs9311
  • zymredbird
  • STEE_HZY
  • code004
© 2019 八聲甘州
Powered by Hexo v3.9.0
|
Theme – NexT.Gemini v7.3.0