做题记录 25.9.25

szt100309 · 2025-09-25 09:53:57 · 个人记录

\textcolor{black}\odot P3785 [SDOI2017] 文本校正

假设将 t 划分为 $1，$2，$3 三部分，则组合 s 有 6 种情况：$1,$2,$3，$1,$3,$2，$2,$1,$3，$2,$3,$1，$3,$1,$2，$3,$2,$1

$1,$2,$3 的处理是显然的

$1,$3,$2 和 $2,$1,$3，$2,$3,$1 和 $3,$1,$2 分别对称，以下只考虑 $2,$1,$3 和 $2,$3,$1 的情况

231：

等价于两者循环同构且位移长度超过 1（实际上位移为 1 时可以转化为 $3,$1,$2 的情况），可以用 sa 做到 O(n\log n) 或 O(n)

另一种 O(n) 的实现：实际上就是对每个 i 判断是否有 t[1:i]=s[n-i+1:n] 和 t[i+1:n]=s[1:n-i]，对 ts 和 st（表示拼接）分别求出 z 函数即可 O(1) 判定，该方法比 O(n) sa 及 O(n)-O(1) rmq 常数小

213

等价于一个前缀循环同构，同样求出 ts 和 st 的 z 函数 z_{ts}[1\sim 2n] 和 z_{st}[1\sim 2n]，则需要找到一组 (a,b) 使得 t[1:a]=t[b+1:b+a],t[a+1:a+b]=t[1:b],s[a+b+1:n]=s[a+b+1:n]，令 p=\text{lcs}(t,s)，等价于 a\ge 1,b\ge 1,a+b<n,a+b\ge n-p,z_{ts}[n+b+1]\ge a,z_{st}[n+a+1]\ge b

显然为二维数点的形式，容易树状数组做到 O(n\log n)

321

翻转 s，和 t 交错排列，则转化为给定一个长度 2n 的串，判定能否划分为恰好三个长度为偶数的非空回文子串，以下用 s 表示这一字符串，以下回文都表示长度为偶数且回文

先跑一遍 \text{manacher} 对每个回文中心求出最大回文半径

定理：对于一个 s[1:n] 和 1\le a<b<c<n，令 la=s[1:a],ra=s[a+1:n]，lb=s[1:b],rb=s[b+1:n]，lc=s[1:c],rc=s[c+1:n]，若 ra,lb,rb,lc 回文，则 la 和 rc 也回文

证明：

• +----+----------+
  | la |   *ra*   |
  +----+-+--------+
  | *lb* |  *rb*  |
  +----------+----+
  | *lc*     | rc |
  +----------+----+
     ->| v |<-

• 令 v=lc\cap rb
• 因此 la \cdot v 为 la\cdot ra 的前缀，为 lc 的前缀
• 由于 lb 为 lc 的 \text{border}，因此 v 为 lc 的周期
• 因此 la 为 v^{+\infty} 的后缀
• 而 v^R 是 lc 的前缀，因此 la 为 (v^R)^{+\infty} 的前缀，即 la^R 为 v^{+\infty} 的后缀
• 因此 la=la^R，la 回文
• 同理得到 rc 回文

由此容易得到：对于一个 i，若 [1,i] 回文，则只需要考虑 [1,i],[i+1,j],[j+1,n]（其中 j 为第一个满足 j>i 且 [j+1,n] 回文的位置）和 [1,i],[i+1,k],[k+1,n]（其中 k 为最后一个满足 [i+1,j] 回文的位置），该判定过程容易做到 O(n)

代码 （代码中 s，t 互换）

参考 1

参考 2

\purple\odot CF547E Mike and Friends

每个区间询问拆为两个前缀之差，考虑如何计算 s_p 在 s_{1\sim i} 中的出现次数

离线，将询问挂在 i 上

先用 s_{1\sim n} 建立 \text{ACAM}

从 1 到 n 扫描，枚举到 s_i 时，用 s_i 在 \text{ACAM} 上跑，对于每个访问到的点 k，令 \text{fail} 树上 k 到根的链答案加一，s_i 处的询问直接单点查询

链加单点查询转化为单点加区间查询，树状数组即可

时间复杂度 O(m|\sum|+(q+m)\log m)，其中 m=\sum|s_i|

代码

参考

\textcolor{black}\odot P13665 「TPOI-5D」「僕は…」

一次查询 (l,r,L,R) 中，将 [l,r] 分块，整块部分每块建立 \text{ACAM}，令 c_u 表示结点 u 到根的链上终止位置数量，扫描 i=1\sim n，用 s_i 在 \text{ACAM} 上跑，并累加上跑到的点的 c 之和，散块部分使用 \purple\odot CF547E Mike and Friends 的方式，将树状数组改为 O(\sqrt m) 加，O(1) 查询的分块，即可做到总时间复杂度 O(m|\sum|+m\sqrt m+\frac{(m+q)n}S+qS)，假定 n,m,q 同阶则时间复杂度 O(n\sqrt n+n|\sum|)，离线后依次处理每一块可做到空间线性

卡常提示：

1. 整块部分统计答案时不必将询问挂到 L-1 和 R 处，直接枚举询问判断，可以显著提升速度
3. 块长取 500 左右足够通过，也许可以继续优化
4. 不要让数组退化为指针，这样会丢失对齐信息从而影响 \text{simd} 优化

代码

参考

\textcolor{black}\odot CF587F Duff is Mad

代码

参考