20260304 测试 笔记

T1 P7306 [COCI 2018/2019 #1] Strah

• 见到矩形统计问题，应该要往扫描线思想上靠。

考虑按行进行扫描线，对于 $(i,j)$，求出其上方（$<i$）的空地长度 $U_j$，那么原问题等价于

$$\sum _{1\le L\le R\le M}((R-L+1)\times \underset{L\le i\le R}{min}{U}_i)$$

• 考虑转换贡献方式，对于 $i$，处理出 $U_i=\underset{L\le j\le R}{min}{U}_j$ 的最大区间 $[L_i,R_i]$，在这个位置处理跨越 $i$ 的答案。

每行做两次单调栈就可以解决。

• 为了不重复，采用左开右闭区间的形式，即 $U_{L_i}<U_i$ 且 $U_{R_i}\le U_i$。

时间复杂度 $O(n^2)$。

T2 P3715 [BJOI2017] 魔法咒语

• 需要记录 DP 当前串长啥样，并检查当前串中是否有指定的若干个字符串，使用 AC 自动机，并把 Trie 中的点记录进 DP 状态。

设 $f_{u,i}$ 表示当前答案串是 Trie 中的 $u$ 点，当前串长度为 $i$ 的方案数。

则枚举每个字符串 DP，时间复杂度 $O(L^3)$。

对于 $L>100,\mathrm{len}\le 2$，说明 $f_{u,i}$ 只与 $f_{v,i-1/i-2}$ 两层有关，使用矩阵快速幂优化 DP，时间复杂度 $O((4m{)}^3\log L)$。

T3 P4652 [CEOI 2017] One-Way Streets

• 注意不到是能否唯一确定，而不是能否指定。

有一个环的一定可以随便走，不能确定，找环就是找 EDCC，然后判断某割边是往哪个方向走，使用 LCA 打标记。