题目概述

给出一个 $n$ 的排列 $\{p_n\}$（满足 $i\not=p_i$ ），求一个括号序列满足：1.是合法的括号序列。2.对于所有左括号 $i$ ，向 $p_i$ 连双向边，最后得到的图所有节点度数均为 $1$ 。

解题报告

我根本不会构造题.jpg，先考虑把这个排列（也就是置换）拆成若干个循环（环），不难发现，一旦一条边被确定了，其他边也就确定了（当然所有环都必须是偶数个点，否则无解）。

所以我们就可以爆搜？由于环是偶数个点，所以最少点数为 $2$ ，这样最多只有 $50$ 个环，复杂度为 $O(2^{50}n)$ ……

继续考虑发现点数为 $2$ 的时候只有一种方法，是确定的，所以环最少是 $4$ 个点，这样复杂度就是 $O(2^{25}n)$ ，就可以过了QAQ。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100;

int n,a[maxn+5],D[maxn+5];char p[maxn+5];

#define val(ch) ((ch)=='('?1:-1)
#define Mark(i,j) (p[i]='(',p[j]=')')
inline void Solve(int i,bool f){
    if (f) Mark(i,a[i]);f^=1;
    for (int x=a[i];x!=i;x=a[x],f^=1) if (f) Mark(x,a[x]);
}
inline void Clear(int i) {p[i]=0;for (int x=a[i];x!=i;x=a[x]) p[x]=0;}
bool Dfs(int st,int sum=0){
    if (sum<0) return false;if (st>n) return !sum;if (p[st]) return Dfs(st+1,sum+val(p[st]));
    for (int t=0;t<2;t++) if (Solve(st,t),Dfs(st+1,sum+val(p[st]))) return true;Clear(st);return false;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) if (!p[i]&&a[a[i]]==i) p[i]='(',p[a[i]]=')';
    Dfs(1);puts(p+1);return 0;
}