ZigZagK的博客
[复杂度分析]LOJ6043(雅礼集训 2017 Day7)【蛐蛐国的修墙方案】题解
2019年3月1日 11:03
LOJ
查看标签

题目概述

给出一个 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!