【题解】牛客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

相关推荐

评论
7
4
分享

创作者周榜

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