CF1043G Speckled Band
Codeforces Luogu 分析 如果 $[l, r]$ 内不存在两个相同字符，则无解，否则答案至多为 $4$。 于是我们可以对答案进行讨论： 如果答案为 $1$，说明子串形如 $AAAA\cdots$，因此我们可以枚举 $r - l + 1$ 的约数 $d$，并判断其是否存在长度为 $d$ 的周期。 如果答案为 $2$，有三种情况：$AAB$、$ABA$、$BAA$。对于第一种和第...
Codeforces Luogu 分析 如果 $[l, r]$ 内不存在两个相同字符，则无解，否则答案至多为 $4$。 于是我们可以对答案进行讨论： 如果答案为 $1$，说明子串形如 $AAAA\cdots$，因此我们可以枚举 $r - l + 1$ 的约数 $d$，并判断其是否存在长度为 $d$ 的周期。 如果答案为 $2$，有三种情况：$AAB$、$ABA$、$BAA$。对于第一种和第...
Luogu [LOJ](https://loj.ac/problem/2133） 分析 如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。 考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $h...
Luogu LOJ 分析 考虑二分答案 $mid$，则我们需要判定是否存在一个 $p\in[a,b-mid+1]$，满足 $\operatorname{lcp}(suf(p),suf(c))\geq mid$。 既然有 LCP，可以考虑后缀数组，则 $\operatorname{lcp}(suf(p),suf(c))\geq mid$ 相当于 $\min_{i=rk_p+1}^{rk_c}h...
Luogu LOJ 分析 设 $L_i$ 表示以 $i$ 为左端点的 AA 串的数量，$R_i$ 表示以 $i$ 为右端点的 AA 串的数量，则答案为 考虑计算 $L_i$ 和 $R_i$。 暴力就是 $\mathcal{O}(n^2)$ 枚举并用哈希 $\mathcal{O}(1)$ 判断，这样子可以拿 95 分。 考虑枚举 A 的长度 $l$，然后把所有是 $l$ 的倍数的位置标成关键...
Luogu 分析 先考虑 $k|n$ 时的做法。显然所有串的长度应相等。枚举第一个串的起始位置，则需要比较 $k$ 个串中最大的，事先倍长然后后缀排序即可利用 $rk$ 比大小。 考虑 $k\nmid n$ 时怎么做。显然最长的串至多比最短的串长 $1$。 考虑二分答案的排名 $mid$，check() 时仍然枚举第一个串的起始位置 $i$，然后记录一个指针 $p$ 一开始等于 $i$，每次...