专栏文章

题解：CF2048I2 Kevin and Puzzle (Hard Version)

LLittle09笋
CF2048I2题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqo1rqt
此快照首次捕获于
2025/12/04 07:56
3 个月前
此快照最后确认于
2025/12/04 07:56
3 个月前
查看原文
根据简单版本，可以发现大部分情况解的个数并不多，因为对于 LR，LL 和 RR，对于里面的部分填完后，外层只有唯一的填法。因此如果没有一层是 RL，那么答案必然是 11。
接下来考虑有 RL 的情况，不妨假设 RL 是最外部的两个字符。
可以证明的是：这个 RL 中 R 位置和 L 位置填的数是相同的。具体证明在此省略，读者自证不难。
不妨设这个相同的值为 mm。接下来，枚举最右侧填 mm 的 R 位置 xx，和最左侧填 mm 的 L 位置 yy。讨论一下 x,yx,y 的关系：
  • 若 x>yx>y，可以发现 xx 右边的 L 都需要填 mm，而 xx 右边的 R 只有唯一的填法。对 yy 同理。对这种情况计算，我们可以直接枚举 mm，然后就可以确定唯一的 x,yx,y 位置，并检查是否满足 x>yx>y。
  • 若 x<yx<y，此时 xx 左边的 R 都只能填 mm，左边的 L 是唯一的填法。对 yy 的右侧同理。再考虑 (x,y)(x,y) 中间的部分，显然 mm 必然没有在中间出现，因此我们可以删除 xx 及其左边的 R，yy 及其右边的 L（也就是删除所有值为 mm 的位置），称得到的新序列为剩余序列。删除这些字符后，我们解决剩余序列，再对得到的数全部 +1+1，然后加入所有数为 mm 的位置即可。
    以下为一个初始序列的例子，其中红色的字符为 xx 和 yy，省略的部分是 (x,y)(x,y) 中间的部分。
    R L L R R L L R ... L L R R L m 1 2 m m 3 4 m ... m m 2 1 m\textbf{R L L R R L L }\color{red}\textbf{R}\color{black}\textbf{ ... }\color{red}\textbf{L}\color{black}\textbf{ L R R L}\\\textbf{ m 1 2 m m 3 4 m ... m m 2 1 m}
    以下为上述对应的剩余序列，∗* 对应原序列中 x,yx,y 的位置。
    L L L L * ... * R R 1 2 3 4 * ... * 2  1\textbf{L L L L }\color{red}\textbf{*}\color{black}\textbf{ ... }\color{red}\textbf{*}\color{black}\textbf{ R R}\\\textbf{ 1\ 2\ 3\ 4 * ... * 2 \ 1}
    在填完剩余序列后，需要分析加入所有数为 mm 的位置的条件：我们将剩余序列分为“左”、“中”、“右”三个部分，以 x,yx,y 的位置为分界线，其中左部分只有 L，右部分只有 R。则要求是，记“左中”部分的颜色总数为 c1c_1，“中右”部分的颜色总数为 c2c_2，那么需要满足 m=c1+1=c2+1m=c_1+1=c_2+1。同时还要求 mm 不在剩余序列中出现，该限制等价于对于“左中”部分和“中右”部分，都满足 d=1d=1。可以推出等价于剩余序列满足 d=1d=1。对于条件 c1=c2c_1=c_2，容易发现其等价于：记 zz 为左部分和右部分的个数较大值，则剩余序列最左边 zz 个字符必须全为 L，最右边 zz 个字符必须全为 R。
    这部分的最终得出的充要条件是：记 xx 左边有 aa 个 L，yy 右边有 bb 个 R，不妨假设 a≥ba\ge b，取出 (x,y)(x,y) 中间的字符串（不包含 x,yx,y），需要满足末尾有连续 a−ba-b 个 R，且去这 a−ba-b 个 R 后，得到的字符串满足 d=1d=1，即每次取出首尾字符时不存在 RL 的情况。由于 d=1d=1，因此若剩余序列满足该条件，则存在恰好一种填法。
最后仅需要对上述情况分别计数即可。x>yx>y 的情况容易 O(n)O(n) 统计，对于 x<yx<y 的情况，不妨 a≥ba\ge b，可以枚举 yy，计算出 yy 前面连续的极长 R 的个数 cntcnt，那么对 aa 的限制变成了 b≤a≤b+cntb\le a\le b+cnt。
  • 当 cnt=0cnt=0 时，aa 的值固定，但对应的 xx 可以在某一个 R 连续段中任意选择一个位置。我们发现由于 cnt=0cnt=0，也就是 yy 前面一个位置填的是 L，那么 xx 后面一个位置就不能填 R，所以 xx 只能取这个 R 连续段中的最后一个 R。
  • 当 cnt>0cnt>0 时，只需要枚举 xx 的值。容易发现每个 xx 只会被计算至多 22 次。
通过上述观察，我们总共只需要枚举 O(n)O(n) 组 x,yx,y 并判断其是否会对答案增加 11。也就是说，答案是 O(n)O(n) 级别的。
最后的问题是：每次给定一组区间 [l,r][l,r]，问这个字符串每次取出首尾字符时，是否存在 RL 的情况。
一种简单的解决方法是，使用 bitset 维护，例如从小到大扫描 rr，以 bitset 维护对于每个 l+rl+r，是否存在 RL 的情况。该做法的时间复杂度为 O(n2ω)O(\dfrac {n^2}{\omega})，可以通过本题。
如果使用分块卷积，可以做到更优的复杂度。事实上，如果继续深挖性质，可以做到 O(nlog⁡2n)O(n\log ^2n) 的时间复杂度（需要使用卷积），如果你对此感兴趣可以自行研究。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...