括号序列匹配利器：贪心匹配 + 折线图：ARC141C

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135225808

https://www.luogu.com.cn/problem/AT_arc141_c

首先可以列出一些条件，那是 ss 的必要条件：

  1. 若 pi>pi+1p_i>p_{i+1} ，则 si=( ,si+1=)s_i=(\,,s_{i+1}=)

  2. 若 qi>qi+1q_i>q_{i+1} ，则 si=( ,si+1=)s_i=(\,,s_{i+1}=)

然后现在要说明这是充分的。如果这些全都满足，那么 p,qp,q 都是合法的括号序列。如果一个位置，没有被覆盖，那么无解。（看作折线，则一个是水平线上，一个是水平线下，必然包括所有情况）

接下来，我们还原 p,qp,q 判断是否相等即可。

1
2
3
4
5
pre coding at 16:15
st coding at 16:27
st bugging at 16:34
passing at 16:37
fn blogging at 16:43
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
void NO() { printf("-1"); exit(0); }
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 400010
//#define M
//#define mo
int n, m, i, j, k, T;
int a[N], b[N], c[N]; 
queue<int>q; 
char str[N]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read()<<1; 
	for(i=1; i<=n; ++i) a[i]=read(); 
	for(i=1; i<=n; ++i) b[i]=read(); 
	for(i=1; i<n; ++i) if(a[i] > a[i+1]) {
		if(str[a[i]] == ')' || str[a[i+1]] == '(') NO(); 
		str[a[i]]='('; str[a[i+1]]=')'; 
	}
	for(i=1; i<n; ++i) if(b[i] < b[i+1]) {
		if(str[b[i]] == ')' || str[b[i+1]] == '(') NO(); 
		str[b[i]]='('; str[b[i+1]]=')'; 
	}
	for(i=1; i<=n; ++i) if(!str[i]) NO(); 
	for(i=1, j=k=0; i<=n; ++i) {
		if(str[i]=='(') c[++j]=i, ++k; 
		else q.push(i); 
		while(k && !q.empty()) c[++j]=q.front(), q.pop(), --k; 
	}
	if(!q.empty() || k) NO(); 
	for(i=1; i<=n; ++i) if(a[i] != c[i]) NO(); 
	for(i=n, j=k=0; i>=1; --i) {
		if(str[i]=='(') c[++j]=i, ++k; 
		else q.push(i); 
		while(k && !q.empty()) c[++j]=q.front(), q.pop(), --k; 
	}
	if(!q.empty() || k) NO(); 
	for(i=1; i<=n; ++i) if(b[i] != c[i]) NO(); 
	printf("%s", str+1); 
	return 0;
}