简介

$ Manacher $ ，俗称马拉车，是一种可以在 $ O(n) $ 的时间复杂度下，求出一个字符串的所有回文子串的神奇算法。

$Link$

给你一个 $n$ 个点的树，根为 $1$ 号点。

共有 $m$ 次询问，每次询问给你 $k$ 个数，问能否找到其中一个数，使得其他点在从根到这个数的路径上或与其距离为 $1$。

$ 2\le n\le 2\times 10^5,1\le m\le 2\times 10^5,\sum k\le 2\times 10^5$。

$Link$

$n$ 个点围成一圈，每个点都有类型。

给每个点染色，要求相邻的不同类型的点不能染同种颜色。

求最少颜色数和染色方案。

共有 $t$ 组数据。

$1\le t\le 10^4,3\le n\le 2\times 10^5,\sum n\le 2\times 10^5$。

$Link$

给你一个 $n$ 的排列 $p$，以及排列中每个数的颜色 $c$。

定义若 $c=a\times b$，则 $c_i=b_{a_i}$。

找到最小的正整数 $k$ 使得将 $p$ 变为 $p^k$ 后，存在一个 $i$ 使得 $c_i=c_{p_i}=c_{p_{p_i}}=\cdots$。

共有 $t$ 组数据。

$1\le t\le 10^4,\sum n\le 2\times 10^5$。

$Link$

定义一个数中，连续 $k$ 个数相等，为一个长度为 $k$ 的块。

要求块外两端的数字不同于块内数字。

写下从 $0\dots 10^n-1$ 的所有数，不足 $n$ 位的用前导 $0$ 补足。

对于每一个 $i=1\dots n$ 求这些数中有多少长度为 $i$ 的块。

$n\le 2\times 10^5$，答案对 $998244353$ 取模。

定义

将一个字符串的每个后缀按字典序排序，后缀数组 $ sa_i $ 表示排名为 $ i $ 的后缀的起始下标。

来源

$KMP$ 算法是对于一个主串匹配一个子串，$AC$ 自动机则解决了一个主串匹配多个子串的问题。

来源

在暴力匹配子串时，若不匹配，则跳回子串开头匹配主串的下一位。

会发现其实主串的部分位置已经遍历过了，这样重复的遍历导致了暴力算法并不优秀。

我们可以让子串跳过一部分主串，以达到更高的效率。

定义

一棵树，用边代表字母，这样一条路径就代表了一个字符串。

写在前面

第一轮考的还不错，希望第二轮可以考个好成绩吧。