【题解】牛客NOIP暑期七天营-提高组2

A.ACGT

部分分30分:

实现较优秀的暴力

100分1:trie树

trie树上的节点多记一个rest值表示还有多少个串没被用。枚举所有串, 每次先在trie上跑匹配串,看一看那个点的rest。如果没法匹配的话就往trie里插入原串,把结束节点的rest+1

100分2:hash

思路和正解1类似。其实就是把trie换成hash。(把在树上跑换成求hash值

B.幸运数字考试

部分分30分

每次选择乘10加4进队和乘10加7进队,有数字≥时判断4和7个数是否 相同,相同则输出后退出
效率

100分

可以发现,所以可以先把所有数据范围内的数字都预处理出来,每次询问二分查找即可
注意在答案为10个4和10个7的时候,需要特判以避免long long/int64的范围问题

C.滑块

部分分30分

直接模拟即可

部分分50分

对于一段连续且标记状态相同的区间,可以考虑将其用一个结点表示,需要对其内部滑块操作时再进行分裂,使用支持插入的数据结构维护即可
维护时,可考虑维护lsum/rsum分别表示该区间左端/右端延续的最大长度,mx表示该区间的答案,并记录相应位置即可

100分

对于复制操作,在部分分2的基础上使用支持可持久化的数据结构即可
注意如果选手使用非旋转Treap时,在合并时需考虑结点key值相同的问题,
一个OI数据范围内可以接受的解决方案详见:FHQ Treap及其可持久化与***树式重构
在构造本部分数据时,鉴于本场比赛为NOIP模拟赛,未加入诸如多个轨道互相复制式插入形成接近数据上限个标记状态互不相同的滑块的数据,数据强度尽量保证复杂度优于暴力的解法通过。
对于加强数据如有需要,可私信获取该部分数据生成器


全部评论
我想问T3 50分中支持插入的数据结构是指什么
点赞 回复 分享
发布于 2019-08-20 13:55
吐槽最后一题数据强度,以及为什么模拟赛考名次树
点赞 回复 分享
发布于 2019-08-20 13:55
rating咋还没计算啊
点赞 回复 分享
发布于 2019-08-20 15:34
前排刘明,,,
点赞 回复 分享
发布于 2019-08-20 13:20
话说有std嘛qwq
点赞 回复 分享
发布于 2019-08-21 08:30
t2打了个大模拟的蒟蒻路过。。。
点赞 回复 分享
发布于 2019-08-20 22:30
treap算NOIP范围嘛
点赞 回复 分享
发布于 2019-08-20 14:56
T1直接用set就好了(逃
点赞 回复 分享
发布于 2019-08-20 13:42
为什么前两题这么水,最后一题代码这么长,调都懒得调
点赞 回复 分享
发布于 2019-08-20 13:40
比赛时候忘了可持久化,忘了旋转,甚至一个大于小于写反了,然后得了70,开心,出题人真好
点赞 回复 分享
发布于 2019-08-20 13:26
前排资磁
点赞 回复 分享
发布于 2019-08-20 13:20
前排留名,,
点赞 回复 分享
发布于 2019-08-20 13:13

相关推荐

不愿透露姓名的神秘牛友
2025-12-17 16:48
今天九点半到公司,我跟往常一样先扫了眼电脑,屁活儿没有。寻思着没事干,就去蹲了个厕所,回来摸出手机刷了会儿。结果老板刚好路过,拍了我一下说上班别玩手机,我吓得赶紧揣兜里。也就过了四十分钟吧,我的直属领导把我叫到小隔间,上来就给我一句:“你玩手机这事儿把老板惹毛了,说白了,你可以重新找工作了,等下 HR 会来跟你谈。” 我当时脑子直接宕机,一句话都没憋出来。后面 HR 找我谈话,直属领导也在旁边。HR 说我这毛病不是一次两次了,属于屡教不改,不光上班玩手机,还用公司电脑看论文、弄学校的事儿。我当时人都傻了,上班摸鱼是不对,可我都是闲得发慌的时候才摸啊!而且玩手机这事儿,从来没人跟我说过后果这么严重,更没人告诉我在公司学个习也算犯错!连一次口头提醒都没有,哪儿来的屡教不改啊?更让我膈应的是,昨天部门刚开了会,说四个实习生里留一个转正,让大家好好表现。结果今天我就因为玩手机被开了。但搞笑的是,开会前直属领导就把我叫去小会议室,明明白白告诉我:“转正这事儿你就别想了,你的学历达不到我们部门要求,当初招你进来也没打算给你这个机会。”合着我没入贵厂的眼是吧?可我都已经被排除在转正名单外了,摸个鱼至于直接把我开了吗?真的太离谱了!
rush$0522:转正名单没进,大概率本来就没打算留你
摸鱼被leader发现了...
点赞 评论 收藏
分享
评论
7
4
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务