night

larsr · 2026-03-12 15:04:41 · 题解

赛时花了 1h 左右想出了做法，然后因为时间不够了只写了判断是否有解，由于一个细节写错了挂成 22 分，遗憾呀。

下文很多东西正确性个人感觉比较显然，故没写证明。

可以发现对于 b 中的一个元素，它要么是从 a 中的一个区间元素 [l,r] 合并而成的，要么是 a 中的一个前缀和后缀合并而成的。

具体结构长这样：

• 将 X_{beg} 和 X_{end} 合并成一个元素，要求 (|X_{end}|-|X_{beg}|)\bmod 3=1。
• 同一个段将合并成 b 一个元素，每个部分的元素按顺序放置。

这个实际上是对称的，就是要翻转再做一遍。

考虑枚举 X_{beg} 和 X_{end} 的位置，还有它们合并之后在 b 中的位置 z，这个复杂度是 O(n^3) 的。

考虑其它位置怎么处理，对于 Y 可以每次贪心取最小的段，可以 O(n^3) 预处理。得到 Y 部分匹配到的位置 l，然后从 l 处理 U,V,W 部分。

设 fu_{i,j} 代表 U 部分从 i 端点开始匹配 b 中的 [1,j] 右端点最小的位置，但是 V 部分是一个一个匹配的，所以设 h_{i,j,k} 代表 U 还没使用 W 部分从 i 端点开始匹配 b 中的 [1,j] 右端点 k 是否可以为 j。此处 h 的转移如下：

• 如果 a_k=b_j 并且 h_{i,j-1,k-1} 则 h_{i,j,k} 为 1。
• 如果 k\ge fu_{i,j} 并且 s_k=s_{fu_{i,j}} 且 (k-fu_{i,j})\bmod 3 = 0，则 h_{i,j,k} 为 1。