CF508E (贪心+搜索+构造)

题目大意：让你构造一个括号序列，括号匹配的方式类似于栈，给出从左数每个括号到和它匹配的右括号的最小和最大距离，让你输出一个合法括号序列

看错题了以为是二分图，然后写了搜索

贪心发现如果距离往小了填，不会影响结果

括号必须套完整的括号，所以距离必须是2的整数倍+1

如果一个括号匹配上了，那么两个括号之间不能有其它的半个括号

如果第一个能匹配的右括号的位置被占上了，那么就把前面的左括号相匹配的右括号往右挪，如果超过了能移动的最大范围，说明不合法

细节比较多

 1 #include <map>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define N 2000
 7 #define ll long long
 8 #define dd double
 9 using namespace std;
10 //re
11 int gint()
12 {
13     int ret=0,fh=1;char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
16     return ret*fh;
17 }
18 int n,cte,tp;
19 int l[N],r[N],pos[N],w[N],mch[N];
20 int move(int x)
21 {
22     int y=mch[x];
23     if(!y) return 1;
24     if(x+2>2*n) return 0;
25     if(x+2<=pos[y]+r[y])
26     {
27         if(!mch[x+2]||move(x+2)) mch[x+2]=mch[x],mch[x]=0;
28         else return 0;
29     }else return 0;
30     return 1;
31 }
32 
33 int main()
34 {
35     freopen("a2.in","r",stdin);
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++)
38         scanf("%d%d",&l[i],&r[i]);
39     int k=1;cte=1;int ma=2*n;
40     for(int i=1;i<=n;i++)
41     {
42         while(mch[k]) w[k]=2,k++;
43         int st=k+l[i]+(l[i]&1?0:1);
44         if(st>k+r[i]) {printf("IMPOSSIBLE
");return 0;}
45         for(int j=k+1;j<=st;j++)
46             if(mch[j]){
47                 int flag=move(j);
48                 if(!flag) {printf("IMPOSSIBLE
");return 0;}
49             }
50         int flag=0;
51         for(int j=st;j<=k+r[i]&&j<=2*n;j+=2)
52             if(!mch[j]) {mch[j]=i,pos[i]=k,k++;flag=1;break;}
53         if(flag) continue;
54         flag=move(st);
55         if(!flag) {printf("IMPOSSIBLE
");return 0;}
56         mch[st]=i,pos[i]=k,k++;
57     }
58     while(mch[k]) w[k]=2,k++;
59     for(int i=1;i<=2*n;i++)
60         if(w[i]==2) printf(")");
61         else printf("(");
62     puts("");
63     return 0;
64 }