hdu_5831_Rikka with Parenthesis II(模拟)

题意：

给你一些括号的排列，必须交换一次，能不能将全部的括号匹配

题解：

模拟一下括号的匹配就行了，注意要特判只有一对括号是NO，因为必须要交换一次

 1 #include <cstdio>
 2 #include <cstring>
 3 const int N = 1e5 +5;
 4 char s[N];
 5 int st[N],top;
 6 int main()
 7 {
 8     int t;
 9     scanf("%d", &t);
10     while (t--)
11     {
12         int n;
13         scanf("%d", &n);
14         scanf("%s", s);
15         if (n == 2 && s[0] == '(' && s[1] == ')') {printf("No
"); continue;}
16         top = 0; st[0] = -1;
17         for (int i = 0; i < n; i++)
18         {
19             if (s[i] == '(') st[++top] = 0;
20             else if (st[top] == 0) top--;
21             else st[++top] = 1;
22         }
23         if (top == 0) printf("Yes
");
24         else if (top == 2 && st[1] == 1 && st[2] == 0) printf("Yes
");
25         else if (top == 4 && st[1] == 1 && st[2] == 1 && st[3] == 0 && st[4] == 0) printf("Yes
");
26         else printf("No
");
27     }
28     return 0;
29 }

View Code