题解 | E的秒杀解法

小d的博弈

https://ac.nowcoder.com/acm/contest/53366/E

E题利用SG定理可以直接秒掉。

OI-wiki的介绍

由题意可知，合法的状态转移为 x→x′(x′<x2)x \to x' (x'< \frac{x}{2}) （ yy 类似 ），所以 SG(x)=x′<x2SG(x′)SG(x)=\mathop{mex} \limits_{x'< \frac{x}{2}} SG(x') ，SG(1)=SG(2)=0SG(1)=SG(2)=0 。利用数学归纳法可得 SG(x)=⌊2(x+1)⌋−1SG(x)=\lfloor \log_{2}(x+1) \rfloor - 1 。如果 SG(n)=SG(m)SG(n)=SG(m)，则后手胜利，否则先手胜利。

全部评论
SG函数打个表
点赞 回复 分享
发布于 2023-05-28 22:00 山东
怎么用数学归纳法得到sg函数的表达式？
点赞 回复 分享
发布于 2023-04-24 07:57 浙江
budong
点赞 回复 分享
发布于 2023-04-08 20:44 广东

相关推荐

12-23 20:09
南京工业大学浦江学院 Java
点赞 评论 收藏
分享
昨天 16:42
小红书_后端开发_REDstar算法工程师(准入职员工)
小红书内推，小红书内推码
小红书推荐算法面经一面（60min）1、自我介绍（5分钟）2、项目和一些八股（40分钟）-&nbsp;模型label是什么-&nbsp;这一结构为什么会有效果提升，分析-&nbsp;embedding怎么得到的-&nbsp;简单介绍一下sim3、手撕代码（10分钟）-&nbsp;最大子数组和4、反问二面（40min）1、自我介绍（5分钟）2、项目（20分钟）-&nbsp;为什么模型有效果-&nbsp;召回粗排和精排要解决什么问题，选一个最熟悉的讲一下未来的迭代方向-&nbsp;怎么保证链路一致性3、手撕代码（10分钟）-&nbsp;给链表的头结点，将其按照升序排列并返回排序后的链表4、反问虽然两次面试前几个小时，面试官都因为临时开会更改了面试时间，让人有点不舒服，但是面试官人真的都...
点赞 评论 收藏
分享
12-20 13:19
已编辑
曲阜师范大学 Java
点赞 评论 收藏
分享
12-24 20:52
武汉大学 Java
点赞 评论 收藏
分享
评论
26
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客2025仙途报告 #
9244次浏览 200人参与
# 我们是不是被“优绩主义”绑架了？ #
741次浏览 40人参与
# 2025年终总结 #
186727次浏览 3138人参与
# 你面试体验感最差/最好的公司 #
26200次浏览 433人参与
# 找工作，行业重要还是岗位重要？ #
86450次浏览 1725人参与
# 今年你最想重开的一场面试是？ #
9125次浏览 107人参与
# 礼物开箱Plog #
2632次浏览 97人参与
# 一人说一个提前实习的好处 #
18247次浏览 263人参与
# 秋招落幕，你是He or Be #
19455次浏览 335人参与
# 重来一次，你会对开始求职的自己说 #
8662次浏览 224人参与
# 工作中听到最受打击的一句话 #
10876次浏览 162人参与
# 为了秋招你都做了哪些准备？ #
29377次浏览 523人参与
# 实习没事做是福还是祸？ #
21359次浏览 316人参与
# 工作两年，想和老板谈涨薪怎么说 #
39012次浏览 176人参与
# 实习的内耗时刻 #
212399次浏览 1576人参与
# 离家近房租贵VS离家远但房租低，怎么选 #
13873次浏览 130人参与
# 这些公司卡简历很严格 #
82551次浏览 375人参与
# 拿到offer之后，可以做些什么 #
81195次浏览 428人参与
# 职场上哪些行为很加分？ #
308301次浏览 3490人参与
# 团建是“福利”还是是 “渡劫” #
9419次浏览 178人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务