翻车笔记 ZKY 学长的杂题2 [杂题, 清奇脑回路]
第一篇文章莫名就1w字了
辣鸡Typora打开已经有点卡了…于是新开一个…
计数器:
5
种树
[NOI2010]超级钢琴
这个题和上一个一脉相承啊… = =
这个限制不用合并区间 也就不用搞链表了 挺舒服的
然而写着写着发现还有区间重复的问题… = =
去参拜了一发题解才发现还要记录当前的右端点是从哪个区间里选出来的 然后就不会重复了… = =
1 | /************************************************************** |
[Noi2014]动物园
emmmm…一开始看错题了…以为要求最长的不超过中间的border…
后来发现是要求个数… = = 感觉用树状数组做肥肠显然啊
感觉我的kmp似乎要重新学习一个了… = =
1 | /************************************************************** |
我怎么感觉\(\mathrm O(n)\)的那个递推和这个差不多呢 = = 这复杂度真的是\(\mathrm O(n)\)的吗…
[Poi2000]病毒
复(学)习字符串…
trie图上找环…找到了就说明可以一直匹配…
环上的任意节点跳fail到root都不能是结尾(以病毒串为后缀)
发现我不会找环了都…
1 | /************************************************************** |
[Noi2011]阿狸的打字机
是我太菜了还是这题太神了…
首先明确一下
一个串的子串就是这个串在trie的那条路径上的每个节点上
跳fail到根, 途中遇到的每个结尾就是这个串的子串
考虑建一个fail树, 然后考虑从\(x\)出发 如何得出答案: 在这个节点的子树里
有多少个点是\(y\)的节点
我们就可以遍历trie树,
把当前的点在fail树的dfs序上的位置+1,
然后每到达一个终点, 就枚举所有以这个串为\(y\)的询问, 这时\(x\)的子树和就是这个询问的答案
最后…我又把编号搞乱了…
又及: 我在想这题的时候…yy了一个东西 然后似乎发现 这东西叫dsu on tree…
= =
为什么当时学长讲课的时候我连这玩意要干啥都没听懂…此题最大收获在于让我学会了dsu
on tree
1 | /************************************************************** |
By 准备退役旅游的 Cansult