首页 > 硬币游戏Ⅲ
开通博客写题解
头像 lalalaterraria
发表于 2020-05-11 19:35:50
研究了一天终于会写了，故在自己研究并ac后简略提供下解题思路。 官方题解中，"这样我们就转化为k堆独立的硬币问题"是最让我迷惑的地方，这里错了，应改为"转化成n堆独立的硬币问题"。IOI2009中国集训队论文 有一篇关于SG函数的论文中提出的翻硬币问题就是本题的背景。 翻硬币问题可以转化为若干0加一 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 свобода
发表于 2020-05-10 18:45:20
我们翻硬币的时候，可以理解成把最后一个硬币替换成最多前面k-1，最少0个硬币。因为如果在一个位置有两个同样的硬币，他们的sg函数相同，互相抵消。这样我们就转化为k堆独立的硬币问题。令2^p≤k<2^(p+1)，第i个硬币的sg函数是min(lowbit(i),2^p )。可以归纳法证明。如果i 展开全文
去ta的博客 赞 (1) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”