题目大意

我们有一个排列 P（保证 P_i ≠ i），需要构造一个长度为 n 的合法括号序列。 规则是：对于序列中的每个位置 i，如果它是 '('，则必须在图中从节点 i 向节点 P_i 连一条边。最终要求这个图里每个节点的度数都为 1。

关键条件分析

1. 括号序列合法：这是基本要求。

2. 每个点度数为 1：这意味着整个图是由若干个环组成的（因为每个点入度和出度之和为1，且排列保证了图的特殊性）。更具体地说：

   • 我们只在 i 位置是 '(' 时，才从 i 连向 P_i。
   • 一个节点 j 的入度可能来自所有满足 P_i = j 且 s[i] = '(' 的 i。
   • 一个节点 j 的出度来自于它自己：如果 s[j] = '('，那么它会连向 P_j。
   • "每个点度数为一" 在这个问题背景下，实际上等价于：每个节点在图中恰好是一条边的起点或终点。 更精确地说，由于我们只在左括号位置连边，这个条件意味着：
     • 整个图必须是一个完美匹配：n 个节点，n/2 条边（因为括号序列中左括号数量为 n/2），每个节点恰好与一条边关联。
     • 如果把连边关系 (i, P_i) 看作一个匹配，那么这个匹配必须覆盖所有点。

3. 排列 P 的启示：排列 P 将 1..n 这个集合映射到自身。我们可以将 (i, P_i) 视为一个潜在的边。我们的任务是选择其中恰好 n/2 条边（通过将对应的 i 设为 '(' 来实现），使得：

   • 被选中的边构成一个完美匹配（即所有节点恰好出现一次）。
   • 这个匹配与括号序列的合法性相容。

核心思路

1. 将问题转化为图论问题： 我们把 1 到 n 这 n 个点画出来。排列 P 定义了一个置换，这个置换可以分解成若干个环（Cycle）。

2. 观察环的性质： 考虑排列 P 分解出的一个长度为 L 的环：a1 -> a2 -> a3 -> ... -> aL -> a1。

   • 如果我们选择环上的一个点 ai 作为左括号（即选择边 (ai, P[ai]=a{i+1})），那么节点 ai 和 a{i+1} 都已经被这条边使用了。
   • 为了不重复使用节点，环上下一个点 a{i+1} 就不能再作为左括号了（否则 a{i+1} 会连出两条边，且 a{i+2} 会被两条边指向）。所以，我们必须间隔地选择环上的点作为左括号。

3. 环长度的奇偶性至关重要：

   • 对于一个偶数长度的环，我们可以间隔地选择点，恰好选出 L/2 个点作为左括号，剩下的 L/2 个点作为右括号的“接收者”。这是可行的。
   • 对于一个奇数长度的环，我们无法进行这样的间隔选择。因为无论从哪里开始，尝试间隔选取都会导致冲突，无法满足每个点度数恰好为1的条件。因此，如果排列 P 中存在奇数长度的环，则问题无解。

4. 构造括号序列：

   • 如果所有环的长度都是偶数，那么对于每个环，我们固定一种选取模式（例如，从环上编号最小的点开始，将它标记为左括号，然后间隔标记）。
   • 具体步骤：
     1. 分解排列 P 得到所有环。
     2. 检查每个环的长度，如果存在奇数环，直接判定无解（但题目保证有解，所以可以跳过检查直接构造，或者题目数据保证有解）。
     3. 遍历每个环，将环上的点按顺序排列。将奇数位（1, 3, 5, ...）的点标记为 '('，偶数位（2, 4, 6, ...）的点标记为 ')'。或者反过来也可以，只要保证间隔选取且整个序列左右括号数量相等。
     4. 输出每个位置 i 对应的括号。

算法正确性证明

• 每个点度数为1： 在我们的构造中，每个环上，一个点如果是左括号，它是一条边的起点；如果它是右括号，由于它在环中的前一个点必然是左括号，而那个左括号的边正好指向它，所以它是那条边的终点。每个点都恰好属于一条边。
• 括号序列合法： 我们将每个环自身构造成了 ()()... 这种交替形式。整个括号序列是由多个这样的合法交替序列拼接而成。任意多个合法括号序列的拼接仍然是合法的。

样例验证

输入：

n = 6
P = [2, 3, 6, 1, 4, 5] (索引从1开始)

1. 找环：
   • 从1开始：1 -> P[1]=2 -> P[2]=3 -> P[3]=6 -> P[6]=5 -> P[5]=4 -> P[4]=1。得到一个环：1 -> 2 -> 3 -> 6 -> 5 -> 4。长度为6，是偶数。
2. 构造括号序列：
   • 环的顺序：[1, 2, 3, 6, 5, 4]
   • 将奇数位置（第1、3、5个）标记为 '('，偶数位置（第2、4、6个）标记为 ')'。
   • 即：
     • 位置1：'('
     • 位置2：')'
     • 位置3：'('
     • 位置6：')' （注意这里是环序列的第4个元素，对应原序列位置6）
     • 位置5：'(' （环序列第5个元素，对应原序列位置5）
     • 位置4：')' （环序列第6个元素，对应原序列位置4）
3. 输出：按原序列位置 1 到 6 输出括号：
   • s[1] = '('
   • s[2] = ')'
   • s[3] = '('
   • s[4] = ')'
   • s[5] = '('
   • s[6] = ')'
   • 得到 ()()()，与样例输出一致。

复杂度分析

• 时间复杂度：O(n)。只需要遍历节点找环，并为每个节点分配括号。
• 空间复杂度：O(n)。需要存储访问标记、排列 P 和结果字符串。

代码实现 (C++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> P(n + 1); // 1-indexed
    for (int i = 1; i <= n; i++) {
        cin >> P[i];
    }

    vector<char> s(n + 1, ' ');
    vector<bool> visited(n + 1, false);

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            // Find the cycle starting from i
            vector<int> cycle;
            int cur = i;
            while (!visited[cur]) {
                visited[cur] = true;
                cycle.push_back(cur);
                cur = P[cur];
            }
            // Assign parentheses for the cycle
            int len = cycle.size();
            // If cycle length is odd, it's impossible (but problem guarantees solution)
            for (int j = 0; j < len; j++) {
                // Even index in cycle (0-based) -> '(', Odd index -> ')'
                if (j % 2 == 0) {
                    s[cycle[j]] = '(';
                } else {
                    s[cycle[j]] = ')';
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << s[i];
    }
    cout << endl;

    return 0;
}

总结

这道题的关键在于将抽象的括号序列和连边条件，转化为在排列的环结构上进行间隔选取的图论问题。通过分析环的奇偶性，并给出一种确定的构造方法，就能简洁地解决问题。