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模拟赛，未加入诸如多个轨道互相复制式插入形成接近数据上限个标记状态互不相同的滑块的数据，数据强度尽量保证复杂度优于暴力的解法通过。
对于加强数据如有需要，可私信获取该部分数据生成器
全部评论
(12) 回帖