• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

CF1162E Thanos Nim

问题- 1162E -代码力

是关于一个迟到了13个月的解决方案?

这道题我已经是第二次做了。上次做的时候,我才刚刚开始。我什么都不懂,也看不懂学长给我的问题解答。今天又有幸遇到这个问题,终于可以靠自己的思考一点点的谈谈自己的想法了。

大致题意

有成堆的石头。每次Alice和Bob需要选择\(\frac{n}{2}\)堆石头时,分别移除任意数量的石头。谁先不会操作,就被认为输了这场比赛。

解题思路

经过思考,我们可以得到一个明显的结论:谁先减少石头的数量,谁就一定会输掉比赛。原因很简单,假设还原后的石堆数量为\(t\),\(t n\),对方去掉任意一个\(\frac{n}{2}\),那么就剩下\ (t-\ frac {n} {2}。

得到这个之后,我们继续思考,什么时候要把一堆石头完全搬走?

让我们首先考虑简单的情况。一堆石头里只有1,有些数字大于1(如果都大于1,显然可以继续操作,直到出现这种情况)

当除1以外的石头剩余数量少于一半时,无论我们如何选择,都需要选择一堆数量为1的石头,将其移除,然后输掉游戏。否则,我们可以选择那些编号不是1的石头,将它们的编号改为1。这样操作之后,数量不是1的石头数量必须少于一半,对方就输了(原因同上)。

从只包含1等数的情况到更大数目的情况,如果只包含2等数。当不是2的石头剩余数量少于一半时,我们必须选择一堆2来将其变为1。同时我们注意到,经过这次操作,我们剩下的不是1的石头数量就超过一半了,这就是我们上一段讨论的情况,是对方赢的状态,也就是我们会输太多。另一方面,当不是2的石头数量大于一半时,我们把它们都变成2,另一方就输了。

以此类推,可以找到一个共同的规律。对于所有数字中最小的数字,如果其出现次数大于\(\frac{n}{2}\),则第一手获胜,否则第二手获胜。这样问题就解决了。

这个博弈思想还有另外一种理解,就是可以理解为“不要让最小值先减小”。但是,我在写的时候,想了很久,如何证明这个想法和制胜策略之间的关联性。最后觉得有点迷茫,就放弃了。就我个人而言,还是从简单的情况来理解比较好。

其实我不是很擅长游戏,所以可能不是很严谨。请指出任何错误。

Link to comment
Share on other sites