主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：P9522 [JOISC2022] 错误拼写
最后更新于 2025-08-28 08:54:09
作者
2huk
分类
题解
题解
P9522
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
显然可以转化成： - $A < B$：$S_{A+1\sim B} < S_{A\sim B-1}$； - $A>B$：$S_{B \sim A - 1} < S_{B+1\sim A}$。 我们第一种情况为例。 $S_{A+1 \sim B} < S_{A \sim B - 1}$，相当于从 $A$ 开始，第一个不满足 $S_i \ne S_{i+1}$ 一定是 $S_i > S_{i-1}$。 于是朴素的想法是 $\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>
正在渲染内容...
点赞
1
收藏
0
