学步园

模拟题：

算法

1.由输入的P-sequence构找S

2.根据S求每个右括号的左匹配括号，pipei[right] = left

3.根据W-sequence定义求结果

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
using namespace std;

int p[10000], N;
char stk[100000];
int pipei[10000];

int pre( )
{
  int x = p[1], id;
  for( int i = 0; i < x; i++)
     stk[i] = '(';
  stk[x] = ')';
  id = x;
  for( int i = 2; i <= N; i++)
  {  
     
     int y = p[i];
     if( y > x )
     {
        for( int j = 0; j < y - x; j++)
           stk[++id] = '(';
        x = y;        
     }
     stk[++id] = ')'; 
       
  }
  return id;  
}

void find(int t)
{
  stack<int>px;
  for( int i = 0; i <= t; i++)
  {
      if( stk[i] == '('  )
      {
         px.push( i );
      }
      else
      {
        int x = px.top();
        pipei[i] = x;      
        px.pop( );    
      }          
  }     
} 


void solve(int t)
{
  int x = 0;
  //找到其匹配括号得ID 
  for( int i = 0; i  <=  t; i++)
  {
     if( stk[i] == ')' )
     {
         int t = pipei[i], num = 0;
         //printf("%d\n", t);
         for( int j = t + 1; j <= i; j++)
         {
            if( stk[j] == ')' )
                num++;
                    
              
         }
         p[x++] = num;    
         
     }       
       
  }      
  printf("%d",p[0]);
  for( int i = 1; i < x; i++)
  {
     printf(" %d",p[i]);     
  }
  puts("");   
}

int main( )
{
  int T;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d",&N);
    for( int i = 1; i <= N; i++)
      scanf("%d", &p[i]);
    int t = pre( );
    find( t );
    solve( t );        
            
  }    
  return 0;  
}