「COCI 2022.4」Superpozicija 题解

问题分析

核心问题

我们有$t$个实例，每个实例包含：

• 一个长度为$2n$的括号序列$z$
• $n$对位置$(a_i, b_i)$，每对中必须选择一个位置

要求从每对中选择一个位置，使得选出的$n$个字符构成合法的括号序列。

关键观察

观察1：2-SAT问题特征

这个问题具有典型的2-SAT特征：

• 每对括号必须二选一
• 选择之间存在复杂的约束关系
• 需要满足全局的括号序列合法性

观察2：括号序列的合法性条件

一个长度为$n$的括号序列合法的充要条件：

1. 总左括号数 = 总右括号数 = $n/2$（$n$为偶数）
2. 任意前缀中左括号数 ≥ 右括号数

算法思路

方法一：2-SAT建模

变量定义： 对于第$i$对位置$(a_i, b_i)$，定义布尔变量$x_i$：

• $x_i = 0$ 表示选择位置$a_i$
• $x_i = 1$ 表示选择位置$b_i$

约束条件来源：

1. 括号类型约束：

   • 如果$z[a_i] = z[b_i] = '$($'$，则无论怎么选都是左括号
   • 如果$z[a_i] = z[b_i] = '$)$'$，则无论怎么选都是右括号
   • 如果$z[a_i] \neq z[b_i]$，则选择会影响括号类型

2. 序列合法性约束： 这是最复杂的部分，需要确保：

   • 总左括号数 = 总右括号数
   • 任意前缀中左括号数 ≥ 右括号数

方法二：基于位置的约束建模

核心思想：将括号序列的合法性条件转化为2-SAT约束

步骤：

1. 预处理：

   • 计算如果选择某个位置，该位置是左括号还是右括号
   • 统计总的左括号数量约束

2. 构建蕴含图：

   • 为每个位置对创建两个节点（选择$a_i$或$b_i$）
   • 添加约束边表示各种必须满足的条件

算法细节

2-SAT约束的具体设计

约束类型1：总括号数平衡

设$L$为必须选择的左括号总数，$R$为必须选择的右括号总数。 由于最终序列长度为$n$且必须合法，所以$L = R = n/2$。

这可以转化为：选择恰好$n/2$个左括号和$n/2$个右括号。

约束类型2：前缀和约束

对于每个前缀位置$k$，设$S_k$为前$k$个字符的平衡值（左括号+1，右括号-1）。

必须满足：$S_k \geq 0$ 对所有$k$，且$S_n = 0$。

构建蕴含图

对于每对位置$(a_i, b_i)$，有四种可能的括号组合：

1. $(($：两个都是左括号
2. $()$：一个左一个右
3. $)($：一个右一个左
4. $))$：两个都是右括号

每种情况需要添加不同的约束边。

特殊情况处理

子任务2：$z[a_i] = z[b_i]$

• 如果都是左括号：该对贡献一个左括号
• 如果都是右括号：该对贡献一个右括号
• 问题简化为计数和匹配问题

子任务3：$b_i = a_i + 1$

• 位置是连续的
• 可以简化约束条件
• 可能使用贪心或DP解决

复杂度分析

2-SAT标准解法

• 图构建：$O(n + m)$，其中$m$是约束边数
• 强连通分量：$O(n + m)$
• 解构造：$O(n)$
• 总体：$O(n + m)$

约束边数量分析

在最坏情况下，可能需要$O(n^2)$条约束边来编码所有前缀约束。 但通过巧妙的建模，可以优化到$O(n)$或$O(n \log n)$条边。

实现要点

1. 图表示：使用邻接表存储蕴含图
2. Tarjan算法：用于求强连通分量
3. 拓扑排序：用于构造可行解
4. 约束简化：识别并消除冗余约束

优化策略

优化1：增量约束

不是一次性添加所有前缀约束，而是：

• 动态维护当前平衡值
• 只在可能违反约束时添加相应的边

优化2：平衡约束处理

总括号数平衡约束可以通过预处理来简化：

• 先确定必须选择某些类型的括号
• 减少变量自由度

优化3：对称性利用

利用括号序列的对称性来减少约束数量。

样例分析

样例1分析

输入：()))((()
位置对：(1,2), (3,5), (4,6), (7,8)
字符：位置1:')', 位置2:')', 位置3:')', 位置5:'(', ...
解：0 1 0 1
结果序列：()()

样例2分析

输入：)()()()(
解：1 1 0 0
结果序列：(())

总结

本题的核心在于将括号序列的选择问题转化为2-SAT问题，并通过精心设计的约束条件来确保最终序列的合法性。

技术亮点：

• 2-SAT在复杂约束问题中的应用
• 括号序列合法性条件的图论编码
• 大规模约束系统的优化处理
• 强连通分量算法在实际问题中的应用

对于$n \leq 100,000$的数据规模，基于优化2-SAT的解法是可行的，关键在于如何高效地编码括号序列的合法性约束。