POJ 1068 Parencodings(括号匹配)

川长思鸟来 2022-05-17 02:40 106阅读 0赞

[题目链接][Link 1]

题目大意：现在读入一种P序列(它是由S序列转换来的)，让你输出S序列对应的W序列，P序列代表的是第i个右括号之前有多少个左括号，W序列代表的是第i个右括号与它对应的左括号完成匹配的中间有多少个右括号（包括第i个右括号）

分析：根据给出的P序列，可以还原出S序列，用一个字符数组存下来，然后遍历这个字符数组，每次遇到右括号的时候，就往前寻找与之所对应的左括号，因为每个右括号都有与之所对应匹配的左括号，所以为了避免其余的左括号扰乱匹配，对于每一次右括号找到与之对应的那个左括号的时候，就给该左括号打上标记，同时为了避免匹配了多余的左括号，所以在打上标记之后就break掉。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e3;
    int a[25],b[25],vis[maxn];
    char s[maxn];
    
    int main()
    {
        int T,n,k,sum;
        scanf("%d",&T);
        while(T--)
        {
            Clear(a);
            Clear(b);
            Clear(vis);
            scanf("%d",&n);
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            k=sum=0;
            for(int i=0;i<n;i++)
            {
                int cnt=0;
                for(int j=0;j<a[i]-sum;j++)
                {
                   s[k++]='(';
                   cnt++;
                }
                s[k++]=')';
                sum+=cnt;
            }
            int t=0;
            for(int i=0;i<k;i++)
            {
                int cnt=1;
               if(s[i]==')')
               {
                   for(int j=i-1;j>=0;j--)
                   {
                       if(s[j]==')')
                        cnt++;
                       if(s[j]=='('&&!vis[j])
                       {
                           vis[j]=1;
                           break;
                       }
                   }
                   b[t++]=cnt;
               }
            }
            for(int i=0;i<n;i++)
            {
                if(i!=0) printf(" ");
                printf("%d",b[i]);
            }
            printf("\n");
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1068