POJ 1068 Parencodings

Posted on | In | 阅读

给定括号串的两种编码，第一种是显示每个右括号左边有多少个左括号，第二种显示每个右括号与其匹配的左括号间有多少个右括号（包括自己），给出第一种编码，求第二种编码

可以直接模拟，算出原括号串然后去数出第二种编码，也可以定位与右括号匹配的左括号在哪个右括号分割出的区间内，即给出的第一种编码两个数之间是两个相邻右括号之间的左括号数，找的时候就从左边相邻的右括号开始枚举，每次加一个右括号数num_right同时加上中间相应的左括号数num_left直到num_left > num_right为止

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int main(){
    int ca;
    int num;
    int diff[25];
    int arr[25];
    arr[0] = 0;
    scanf("%d", &ca);
    while(ca--){
        memset(diff, 0, sizeof(diff));
        scanf("%d", &num);
        for(int i = 1; i <= num; i++){
            scanf("%d", &arr[i]);
            diff[i] = arr[i] - arr[i-1];
        }
        for(int i = 1; i <= num; i++){
            int j = i;
            /*number of right parentheses between (j-1)th and (i)th right parentheses, including (i)th*/
            int num_right = 1;
            /*number of left parentheses between (j-1)th and (i)th right parentheses*/
            int num_left = diff[j];
            while(num_right > num_left){
                num_right += 1;
                j--;
                num_left += diff[j];
            }
            printf("%d ", num_right);
        }
        printf("\n");
    }
    return 0;
}