一、问题分析与数学建模

1.1 问题本质

这是一道括号序列构造 + 字典序优化问题，核心在于理解匹配条件并设计高效的判断与构造算法。

问题形式化

合法括号序列定义（递归定义）：

1. 空串 $\varepsilon$ 是合法的
2. 若 $B$ 合法，则 $(B)$ 合法
3. 若 $L, R$ 合法，则 $LR$ 合法

匹配定义： 括号序列 $B$ 与字符串 $S$ 匹配，当且仅当：

1. $|B| = |S|$（长度相等）
2. $\forall i < j$，若 $B_i$ 和 $B_j$ 配对，则 $S_i = S_j$

目标：找到字典序最小的满足条件的括号序列 $B$，或判断无解。

---

1.2 核心数学观察

观察 1：配对的必要条件

命题 1：若 $B_i$ 和 $B_j$ 配对，则必须满足 $S_i = S_j$。

推论：字符不同的位置不能配对。

---

观察 2：栈模拟配对过程

定理 1：可以用栈来判断括号序列的合法性。

证明：

• 遇到 (：压栈
• 遇到 )：弹栈
• 最终栈为空 $\Leftrightarrow$ 序列合法

推广：对于字符串 $S$，我们可以用栈来模拟配对过程：

• 当前字符 = 栈顶字符 → 配对，弹出
• 否则 → 压入栈

关键性质：如果最终栈非空，则无解。

---

观察 3：栈状态与哈希

定理 2：两个位置的栈状态相同，当且仅当它们到达该位置时栈中的元素序列相同。

哈希表示： 定义哈希函数：

$$H_i = \sum_{k=1}^{\text{depth}} \text{base}^k \times S[\text{stack}[k]] $$

其中：

• $\text{depth}$ 是当前栈深度
• $\text{stack}[k]$ 是栈中第 $k$ 个元素的位置
• $\text{base}$ 是哈希基数（如 $10^9 + 7$）

关键性质：

$$H_i = H_j \land S_i = S_j \Rightarrow \text{位置 } i \text{ 和 } j \text{ 可以配对} $$

证明：

• $H_i = H_j$ 意味着栈状态相同
• 如果在位置 $i$ 后压入 $S_i$，在位置 $j$ 后可以与之配对（弹出）
• 配对要求 $S_i = S_j$

---

观察 4：贪心策略

定理 3：为了使字典序最小，应该尽早放置左括号 (。

证明： 由于 ( 的字典序小于 )，在相同位置：

• 放置 ( 的序列字典序更小

因此贪心策略：

• 当前位置优先放置 (
• 找到最近的可以配对的位置放置 )
• 递归处理剩余部分

---

1.3 算法设计思路

第一步：合法性判断

• 用栈模拟配对过程
• 记录每个位置的哈希值
• 最终栈非空 → 无解

第二步：建立映射

• 将相同哈希值的位置存储在一起
• 用于快速查找配对位置

第三步：递归构造

• 贪心：左端点放置 (
• 二分查找：找到最近的配对位置
• 递归：处理内部和外部

---

二、算法流程详解

2.1 栈模拟与哈希计算

核心思想： 模拟字符串的配对过程，用哈希值记录每个位置的"栈状态"。

算法：

for i = 1 to n:
    if 栈非空 and S[栈顶] == S[i]:
        配对成功，弹出栈顶
        哈希值 -= 贡献
    else:
        压入位置 i
        哈希值 += 贡献
    记录 hash[i] = 当前哈希值

数学推导：

设当前栈为 $[p_1, p_2, \ldots, p_d]$（深度为 $d$），则：

$$H = \sum_{k=1}^{d} \text{base}^k \times S[p_k]$$

压入位置 $i$：

$$H' = H + \text{base}^{d+1} \times S[i]$$

弹出：

$$H' = H - \text{base}^d \times S[p_d]$$

---

2.2 递归构造算法

函数签名：dfs(l, r) 处理区间 $[l, r]$

算法流程：

1. 在位置 $l$ 放置 (
2. 查找匹配位置 $p$：
   • $p$ 是区间 $[l+1, r]$ 内，满足 $\text{hash}[p-1] = \text{hash}[l]$ 且 $S[l] = S[p]$ 的最小位置
3. 在位置 $p$ 放置 )
4. 递归处理 $[l+1, p-1]$（括号内部）
5. 递归处理 $[p+1, r]$（括号外部）

正确性证明：

引理 1：若 $\text{hash}[p-1] = \text{hash}[l]$，则 $[l+1, p-1]$ 是一个完整的配对区间。

证明：

• $\text{hash}[l]$：位置 $l$ 之前的栈状态
• $\text{hash}[p-1]$：位置 $p-1$ 之后的栈状态
• 两者相同 → 位置 $l$ 压入的字符在 $[l+1, p-1]$ 区间内完全配对
• 因此 $l$ 和 $p$ 可以配对

---

2.3 二分查找优化

问题：如何快速找到匹配位置？

方法：

• 预处理：将相同哈希值的位置存储在 vector 中
• 查询：在 mp[hash[l]] 中二分查找第一个 $\le r-1$ 的位置

代码：

int ps = upper_bound(mp[hh[l]].begin(), mp[hh[l]].end(), r - 1) 
         - mp[hh[l]].begin() - 1;
ps = mp[hh[l]][ps] + 1;

解释：

• upper_bound(r-1)：找到第一个 $> r-1$ 的位置
• -1：回退到最后一个 $\le r-1$ 的位置
• 这就是哈希值等于 hash[l] 且在区间内的最右位置
• +1：因为配对位置是该位置的下一个

---

三、代码模块详解

模块 1：初始化与预处理

const int N = 1e5 + 5;
int n;
char s[N], ans[N];

ull bs = 1e9 + 7, pw[N];

inline void init() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    pw[0] = 1;
    
    for (int i = 1; i <= n; ++i)
        pw[i] = pw[i - 1] * bs;
}

数据结构：

• s[]：输入字符串
• ans[]：答案括号序列
• pw[]：哈希权重，$\text{pw}[i] = \text{base}^i$

初始化：

• 预计算哈希权重，避免重复计算

---

模块 2：栈模拟与哈希计算

int st[N], tp;
ull hh[N];

inline void work() {
    ull H = 0;
    tp = 0;
    
    for (int i = 1; i <= n; ++i) {
        if (tp && s[st[tp]] == s[i]) {
            H -= pw[tp] * s[i];
            --tp;
        } else {
            st[++tp] = i;
            H += pw[tp] * s[i];
        }
        
        hh[i] = H;
    }
    
    if (tp) {
        puts("-1");
        return;
    }

栈操作：

• st[]：栈，存储位置
• tp：栈顶指针

配对判断：

if (tp && s[st[tp]] == s[i]) {
    // 栈顶字符 = 当前字符 → 配对
    H -= pw[tp] * s[i];  // 减去贡献
    --tp;                // 弹出
}

压栈：

else {
    st[++tp] = i;        // 压入位置 i
    H += pw[tp] * s[i];  // 加上贡献
}

哈希公式：

$$H = \sum_{k=1}^{\text{tp}} \text{pw}[k] \times s[\text{st}[k]] $$

合法性判断：

if (tp) {  // 栈非空
    puts("-1");
    return;
}

如果处理完所有字符后栈非空，说明有字符无法配对，无解。

---

模块 3：建立哈希映射

map<ull, vector<int>> mp;

for (int i = 1; i <= n; ++i)
    mp[hh[i]].push_back(i);

目的：

• 将具有相同哈希值的位置分组
• 用于快速查找配对位置

数据结构：

• mp[hash]：所有哈希值为 hash 的位置的有序列表

---

模块 4：递归构造答案

inline void dfs(int l, int r) {
    if (l > r)
        return;
    
    ans[l] = '(';  // 贪心：左端点放置 '('
    
    // 二分查找匹配位置
    int ps = upper_bound(mp[hh[l]].begin(), mp[hh[l]].end(), r - 1) 
             - mp[hh[l]].begin() - 1;
    ps = mp[hh[l]][ps] + 1;
    
    ans[ps] = ')';  // 匹配位置放置 ')'
    
    dfs(l + 1, ps - 1);  // 递归：括号内部
    dfs(ps + 1, r);      // 递归：括号外部
}

贪心策略：

ans[l] = '(';

在左端点放置 (，保证字典序最小。

查找匹配位置：

int ps = upper_bound(mp[hh[l]].begin(), mp[hh[l]].end(), r - 1) 
         - mp[hh[l]].begin() - 1;
ps = mp[hh[l]][ps] + 1;

详细解释：

1. mp[hh[l]]：所有哈希值等于 hh[l] 的位置
2. upper_bound(..., r-1)：找到第一个 $> r-1$ 的位置
3. -1：回退到最后一个 $\le r-1$ 的位置
4. 这个位置的哈希值是 hh[某个位置]
5. 配对位置是该位置的 下一个位置，所以 +1

为什么是下一个位置？

因为 hh[i] 表示处理完位置 $i$ 之后的哈希值。

若 hh[p-1] = hh[l]，则：

• 处理完 $p-1$ 后，栈状态 = 处理完 $l$ 后的栈状态
• 说明位置 $l$ 压入的字符在区间 $[l+1, p-1]$ 内完全配对
• 因此 $l$ 和 $p$ 可以配对

递归处理：

dfs(l + 1, ps - 1);  // 内部
dfs(ps + 1, r);      // 外部

---

模块 5：输出答案

dfs(1, n);

for (int i = 1; i <= n; ++i)
    putchar(ans[i]);

puts("");

---

四、算法正确性证明

4.1 合法性判断的正确性

定理 4：栈最终为空 $\Leftrightarrow$ 存在合法的括号序列。

证明（$\Rightarrow$）： 若栈最终为空，则所有字符都成功配对。 按照配对关系构造括号序列即可。

证明（$\Leftarrow$）： 若存在合法括号序列，则所有字符必须两两配对。 栈模拟过程会将它们全部弹出，最终栈为空。

---

4.2 贪心策略的正确性

定理 5：在保证合法性的前提下，尽早放置 ( 得到的序列字典序最小。

证明： 字典序比较从左到右进行，( < )。 在任何位置放置 ( 都不会使字典序变大。

---

4.3 递归构造的正确性

定理 6：dfs(l, r) 正确构造区间 $[l, r]$ 的字典序最小括号序列。

证明（归纳法）：

• 基础：$l > r$ 时，空区间，正确。
• 归纳：假设对所有长度 $< r-l+1$ 的区间正确。
  • 在 $l$ 放置 (，保证字典序最小
  • 找到最近的配对位置 $ps$，保证合法性
  • 递归处理子问题，由归纳假设正确
  • 因此整体正确。

---

五、复杂度分析

时间复杂度

• 栈模拟：$O(n)$
• 建立映射：$O(n)$
• 递归构造：
  • 每个位置被访问常数次：$O(n)$
  • 每次二分查找：$O(\log n)$
  • 总计：$O(n \log n)$

总时间复杂度：$O(n \log n)$

空间复杂度

• 栈、哈希数组、映射：$O(n)$
• 递归深度：$O(n)$（最坏情况）

总空间复杂度：$O(n)$

---

六、易错点与优化

6.1 易错点 1：哈希冲突

问题：不同的栈状态可能产生相同的哈希值。

解决：

• 使用 unsigned long long 自然溢出
• 选择合适的哈希基数（$10^9+7$）
• 概率上冲突极小

---

6.2 易错点 2：配对条件

错误：只检查哈希值相同，忘记检查字符相同。

正确：配对需要同时满足：

1. hh[ps-1] = hh[l]
2. s[l] = s[ps]

代码中通过栈模拟保证了条件2。

---

6.3 易错点 3：二分查找边界

问题：upper_bound 的使用。

正确理解：

• upper_bound(x)：返回第一个 $> x$ 的位置
• -1：回退到最后一个 $\le x$ 的位置

---

七、知识点总结

核心算法技巧

1. ✅ 栈的应用

   • 括号匹配
   • 配对消除

2. ✅ 哈希技巧

   • 状态哈希
   • 快速判断相等

3. ✅ 递归/分治

   • 区间递归构造
   • 分解子问题

4. ✅ 贪心策略

   • 字典序优化
   • 尽早决策

5. ✅ 二分查找

   • 在有序序列中查找
   • STL upper_bound

---

适用场景

• ✅ 括号序列问题
• ✅ 字符串匹配与构造
• ✅ 字典序优化
• ✅ 递归构造

---

八、总结

算法精髓

本题采用的栈 + 哈希 + 递归算法的核心思想：

1. 栈模拟：判断合法性，模拟配对过程
2. 哈希优化：快速判断栈状态相等
3. 贪心策略：尽早放置左括号
4. 递归构造：分解子问题，逐步构造答案

学习价值

通过这道题，我们学习了：

1. 如何用栈解决配对问题
2. 如何设计状态哈希
3. 如何用贪心策略优化字典序
4. 递归构造的技巧