题解：P9522 [JOISC2022] 错误拼写

· · 题解

显然可以转化成：

我们第一种情况为例。

于是朴素的想法是 $\mathcal O(3^n n |\Sigma|)$，爆搜每两个位置之间的 $<,>,=$ 关系，然后 DP 处理方案数。 考虑正解。设 $f(i, j)$ 表示考虑前 $i$ 个位置，且 $S_i=j$ 的方案数。 第一个转移是 $f(i-1,j)$。 然后枚举 $S_{i-1}=k \ne j$ 以及以 $i-1$ 结尾的极长连续段 $[p,i-1]$。我们思考 $S_{i-1}=k,S_i=j$ 能否满足所有与其有关的条件。如果满足就能从 $f(p, k)$ 转移过来。 对于一个限制 $A_i = u, B_i = v$（$u < v$，其余情况类似）。如果 $p \le u \le i - 1$ 且 $v \ge i-1$，那么这个限制就和 $(i-1,i)$ 是有关的。具体的，由于 $i-1$ 之前全是 $=$，所以我们只需要判断 $j,k$ 的大小关系是否是这个 $i$ 限制所要求的（因为 $(i-1,i)$ 是第一个满足不是 $=$ 的）。 注意直接 $f(p, k) \to f(i,j)$ 会转移重复，因为我们没有体现出 $[p,i-1]$ 是极长的这一点。所以状态再加一维 $0/1$ 表示是否 $S_{i-1}\ne S_i$。 暴力实现上述过程代码：<https://www.luogu.com.cn/paste/h7k2fk9q> 优化不是很困难，相信来做本题的读者有能力完成。 AC 代码：<https://www.luogu.com.cn/paste/85m5mr8j>