【复杂度分析】loj#6043. 「雅礼集训 2017 Day7」蛐蛐国的修墙方案

感觉有点假

题目大意

数据范围：$n<=100$

题目分析

由于题目给出的是置换，所以相当于只需枚举每个环的两个状态。

主要是复杂度分析这里：

一元环：不存在

二元环：特判保平安

三元环：不存在

四元环：复杂度$O(2^{25})$，但是特判一下顺序就可以秒下来了

六元环：复杂度$O(2^{17})$至此及以后的复杂度都是可以接受的了

不知道为什么倒着搜就会更快？

 1 #include<bits/stdc++.h>
 2 const int maxn = 103;
 3 
 4 int n,las,p[maxn],w[maxn],deg[maxn];
 5 
 6 void dfs(int x)
 7 {
 8     if (x==0){
 9         if (las) return;
10         for (int i=1; i<=n; i++)
11             putchar(w[i]?'(':')');
12         exit(0);
13     }
14     if (w[x]!=-1){
15         int che = w[p[x]];
16         if (w[p[x]]!=-1&&((1-w[x])!=w[p[x]])) return;
17         w[p[x]] = 1-w[x];
18         las -= w[x]?1:-1;
19         if (las >= 0) dfs(x-1);
20         las += w[x]?1:-1;
21         w[p[x]] = che;
22     }else{
23         w[x] = 1;
24         int che = w[p[x]], chk = 1;
25         for (int i=p[x],f=w[x]; i!=x; i=p[i])
26             f = 1-f, chk &= (w[i]==-1)||(f==w[i]);
27         if (chk){
28             int bck[maxn],bct = 0;
29             for (int i=p[x],f=w[x]; i!=x; i=p[i])
30                 f = 1-f, bck[++bct] = w[i], w[i] = f;
31             las -= w[x]?1:-1;
32             if (las >= 0) dfs(x-1);
33             las += w[x]?1:-1;
34             for (int i=p[x],f=1; i!=x; i=p[i])
35                 w[i] = bck[f], ++f;
36         }
37         
38         w[x] = 0;
39         che = w[p[x]];
40         if (w[p[x]]==-1||((1-w[x])==w[p[x]])){
41             w[p[x]] = 1-w[x];
42             las -= w[x]?1:-1;
43             if (las >= 0) dfs(x-1);
44             las += w[x]?1:-1;
45             w[p[x]] = che;
46         }
47         
48         w[x] = -1;
49     }
50 }
51 int main()
52 {
53     memset(w, -1, sizeof w);
54     scanf("%d",&n);
55     for (int i=1; i<=n; i++) scanf("%d",&p[i]), ++deg[p[i]];
56     dfs(n);
57     return 0;
58 }

END