板子题。。。
然而我还是不会。
大概做法就是先把所有的串差分后拼成一个大的串,小的串之间用一个极大数(比差分数组中最大的数大就可以)隔开。
并且确保每个用于隔开小串的数大小不同,每隔开一个\(+1\)就可以了。
然后进行二分答案就\(OK\)了
SA+莫队
大概就是像上一个题一样,将所有的名字建成一个大串,记录一下所在名字,
然后对于每个询问预处理一下在SA数组左右的端点
之后的做法和莫队就是标准的莫队了。。。
正解:主席树+SA+二分+RMQ
但是暴力做法远快于正解,而且码量思路也比较好想
还是那个推论2,对于以a到b开始的每个后缀都求一下,
然后在把推算结果与d-c+1取最小值。
对于a到b中rk小于rk[c]的:
从rk[c]开始,到height[i]小于ans就停止,如果i大于sa[a]小于sa[b]更新就好了
对于a到b中rk等于rk[c]的:
特判一下
对于a到b中rk大于rk[c]的:
把小于rk[c]的操作从rk[c]+1到n进行一边就好了
单调栈+SA求LCP
比较易懂,大概就是先把题面上的式子简化一下,
变成某个带n的代数式加上LCP
\(∀1\leq i<j\leq n,\) \(LCP(sa_i,sa_j)=\min\limits_{i< k\leq j} (height_k)\)
然后运用LCP的推论2,将问题转化成了求每个子区间的最小值的加和
可以打权值线段树,但是太麻烦了,于是可以用单调栈来优化
注意:
在求SA时M所赋的初值应大于原序列中的最大值
SA+RMQ(ST表)+二分
每个字串都是一个后缀的前缀,先求一下SA以及LCP,
然后就可以预处理出每个后缀的左右边界值
在处理询问的时候进行二分,查看要查询的字串的左右端点在哪两个后缀中,
最后算一下就好了
注意:
对于每一个操作都要搞正反两遍
常规做法是并查集+SA(+set)
但是zxb用三棵线段树硬是给干过去了,做法么,和差异这个题差不多,tql%%%
用RMQ暴力有两种打法:
最简单的也是得分最低的:
每种情况都枚举一遍
优化的暴力:对于不同的LCP都更新,然后累加
正解就是对于第二种暴力放弃RMQ,改用并查集维护,处理一个siz值,对于不同的点进行合并,这里用set维护了一下并查集
半个板子题,有一个很妙的思路,在处理manacher的时候整一下,对于i=1的情况,循环一下i+p[i],如果j-i长度为4的倍数,更新答案。
毕竟,双倍的回文串还要计算上在每一位之间插进去的字符。
荣登最优解\(Top3\)
我真傻,真的,我单知道输入字符串从0开始,却不知道求manachar时也要从0开始处理
和上一题差不多,都是在manachar函数里搞事情
开一个l和r数组用来表示以i为分割点的所谓双回文串的左右端点,理论上来讲,l在最后取max时应该从n到2,r应该从2到n,防止更改过的对以后的有影响。但是数据他水呀
最后取一下\(l[i]+r[i]\)的最值就ok了
还是在manachar的板子上进行修改。
观察题面,无非就是要求我们求异或意义下的回文串
因为题面的意思是要求我们1与0相对,而不是1与1相对,在函数里循环的时候两个两个的枚举防止#与#判等的情况,相对关系用一个to数组存就好了。
在一个长度为\(L\)的异或回文串里共有\(\frac L2\)个异或回文串,直接加起来就好了。
正解和暴力都想了挺长时间,尤其是暴力\(code\)
用了离散化,regster int,inline来优化。
对于正解,就是对于整个方块横着竖着各扫一边,统计出横纵最长回文串的长度,在运算的时候可以用单调队列优化。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章