manacher算法一图复习

2021-11-14

manacher 算法总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551651.html 测试一下这个博客园的功能（图片好像只能在洛谷上看，有时间就改） manacher 算法总结题目大意给定一字符串，求其最长回文串长度方法对比暴力效率：O(n3)O(n^3)O(n3)，优化后为O(n2)O(n^2)O(n2) manacher效率：O(n)O(n)O(n) 算法思想回文串有两种：奇回文与偶回文分类讨论太麻烦，主要是我不会，于是我们就统一为奇回文如何统一例： abbab 偶回文：abba 奇...

2021-12-05

【P4302 [SCOI2003]字符串折叠】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15646276.html 题目链接题目折叠的定义如下：一个字符串可以看成它自身的折叠。记作S = S X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB 给一个字符串，求它的最短折叠。例...

2021-12-02

【CF554A Kyoya and Photobooks】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15634024.html 题目链接暴力是肯定可以的。所以这里讲 O(1)O(1)O(1)。首先不考虑重复，则有 (∣s∣+1)×26(|s|+1)\times 26(∣s∣+1)×26 种可行方案。然后重复的就是在一个字母的左右放和这个字母相同的字母，有 ∣s∣|s|∣s∣ 种可能。所以总共有 (∣s∣+1)×26−∣s∣(|s|+1)\times 26-|s|(∣s∣+1)×26−∣s∣ 种可能。 Code 12345678910111...

2022-01-12

【P4551 最长异或路径】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15792154.html 题目链接题目给定一棵 nnn 个点的带权树，结点下标从 111 开始到 nnn。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或思路预处理每个点到根节点路劲的异或和，建一棵01trie树。对于每个节点，在trie树上找离它最远的节点，最后取个 max⁡\maxmax 值即可。总结这道题应该也算两个经典问题的集合吧？首先求树上两个节点之间路径的异或和，这是一个非...

2023-10-25

后缀数组SA

后缀数组SA 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134042245 https://uoj.ac/problem/35 通过倍增实现排序类似基数排序，先排后面，再排前面排的过程可以拿桶排优化设 h(i)=lcp(sa[rk[i]−1],i)h(i)=lcp(sa[rk[i]-1],i)h(i)=lcp(sa[rk[i]−1],i) 有 h(i)≥h(i−1)−1h(i)\ge h(i-1)-1h(i)≥h(i−1)−1 123...

2023-12-21

循环同构串的判断+broder剃头截尾法实现均摊：P3546

循环同构串的判断+broder剃头截尾法实现均摊：P3546 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135126979 https://www.luogu.com.cn/problem/P3546 两个串的循环同构可以表示成： AB ， BA ，所以我们等价于在原串求：显然A可以枚举，我们现在就是要求原串所有中心串的最长不交broder。这个方法之前提到过，我们可以用broder剃头截尾法。设 fif_ifi 表示 AAA 的长度为 iii...