首页 > ACM题库 > HDU-杭电 > HDU 1361 Parencodings-模拟-[解题报告] C++
2013
12-09

HDU 1361 Parencodings-模拟-[解题报告] C++

Parencodings

问题描述 :

Let S = s1 s2 … s2n be a well-formed string of parentheses. S can be encoded in two different ways:
  • By an integer sequence P = p1 p2 … pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
  • By an integer sequence W = w1 w2 … wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:


  S    (((()()())))
  P-sequence   4 5 6666
  W-sequence   1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.

输入:

The first line of the input file contains a single integer t (1 t 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 n 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

输出:

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.

样例输入:

2
6
4 5 6 6 6 6
9 
4 6 6 6 6 8 9 9 9

样例输出:

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1361

题意:对于一个合法的括号序列S,可以计算出P和W的值。P的第i个值表示第i个右括号前面有多少个左括号,W的第i个值表示第i个右括号会和前面第几个左括号匹配。现在给出P的值,求W的值。

mark:因为数据很小,n的长度只有20,因此可以直接模拟,由P反求出S,然后由S直接求出P。

代码:

# include <stdio.h>
# include <string.h>


char str[50] ;
int p[50],w[50] ;
int n ;


void setstr()
{
    int num, i, j, cnt ;
    for(i=0;i<n;i++)
    {
        scanf ("%d", &num) ;
        cnt = 0 ;
        for(j=0;cnt<num;j++)
        {
            if (str[j]==')') continue ;
            cnt++ ;
        }
        while (str[j]==')')j++ ;
        str[j] = ')' ;
    }
    for(i = 0 ; i < 2*n ; i++) if (str[i]!=')') str[i] = '(' ;
    str[2*n] = '\0' ;
}


void setw()
{
    
    int i, j=0, flag = 0 ;
    for (i = 0 ; i < 2*n ; i++)
    {
        if (str[i]=='('){ j=i; continue ;}
        if (flag == 0) flag = 1 ;
        else putchar(' ') ;
        printf ("%d", (i-j)/2+1) ;
        str[j] = '*' ;
        while (j>=0 && str[j] != '(') j-- ;
    }
    printf ("\n") ;
}

int main ()
{
    int t ;
    scanf ("%d", &t) ;
    while (t--)
    {
        scanf ("%d", &n) ;
        memset (str, 0, sizeof(str)) ;
        setstr() ;
        setw() ;
    }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/02/16/2353516.html


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。