poj1068（Parencodings）

题目大意：

给你一串关于左右括号的字符串，长度为2*n。这个字符串构成通过两种方式：其中一种是P[i]。p[i]代表第i个右括号有多少个左括号，一共N位。让你求W[i],W[i]代表第i个右括号与其配对的左括号之间有多少个左括号，算上与其配对的左括号。也可以解释为,W[i]代表第i个右括号与其配对的左括号之间有多少个成功配对的括号。

解题思路：

模拟。先通过给出的p[i]模拟出s串左右括号的情况。具体模拟可以是存储每个右括号间隔的左括号个数，然后向数组s里输入“（”“）”。最后计算W[i]，找到每一个“）”，然后依次向前寻找，当找到左右括号（sum1，sum2）相等时说明右括号已经成功配对，然后输出括号个数（sum1，sum2）。

代码：

 1 #include<cstdio>
 2 #include<math.h>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int cas;
11     scanf("%d",&cas);
12     int a1[200],a[200];
13     char s[200];
14     while(cas--)
15     {
16         int n;
17         scanf("%d",&n);
18         int i,j;
19         int len=n;
20         for(i=0;i<n;i++)
21         {
22             scanf("%d",&a1[i]);
23             a[i]=a1[i];
24             if (i)
25                 a[i]=a1[i]-a1[i-1];
26         }
27         int d=0;
28         for(i=0;i<n;i++)
29         {
30             for(j=0;j<a[i];j++)
31                 s[d++]='(';
32             s[d++]=')';
33         }
34         int sum1=0,sum2=0;
35         int cnt=0;
36         for(i=0;i<2*n;i++)
37         {
38             if (s[i]==')')
39             {
40                 cnt++;
41                 for(j=i;j>=0;j--)
42                 {
43                     if (s[j]==')')
44                         sum1++;
45                     else
46                         sum2++;
47                     if (sum1==sum2&&cnt==1)
48                     {
49                         printf("%d",sum1);
50                         break;
51                     }
52                     if (sum1==sum2&&cnt!=1)
53                     {
54                         printf(" %d",sum1);
55                         break;
56                     }
57                 }
58             }
59             sum1=0;
60             sum2=0;
61         }
62         printf("
");
63     }
64     return 0;
65 }

View Code

屌丝终有逆袭日，*******。