POJ 1068：Parencodings

Parencodings

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 22849		Accepted: 13394

Description

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:

q 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).

q 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.

Input

The first line of the input 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.

Output

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.

Sample Input

2

6

4 5 6 6 6 6

9

4 6 6 6 6 8 9 9 9

Sample Output

1 1 1 4 5 6

1 1 2 4 5 1 1 3 9

题意是给出一个成对的括号顺序。

P序列的每一个数代表每一个右括号左边有多少左括号。

W序列的每一个数代表每一个右括号与其成对的左括号范围之内有多少右括号。

给出P序列，求W序列。

自己的做法是规规矩矩模拟还原，只是想如果数据量比较大，还得自己找规律了。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

int Test,num,i;

int ps[105];

int flag[105];

vector<char> seq;

void change()

{

	int qian=0,temp,j;

	for(i=1;i<=num;i++)

	{

		temp = ps[i]-qian;

		for(j=1;j<=temp;j++)

			seq.push_back('<');

		seq.push_back('>');

		qian=ps[i];

	}

}

void cal()

{

	memset(flag,0,sizeof(flag));

	int len= seq.size();

	int j;

	for(i=1;i<len;i++)

	{

		if(seq[i]=='>')

		{

			int result=1;

			for(j=i-1;j>=0;j--)

			{

				if(seq[j]=='>')

					result++;

				if(seq[j]=='<'&&flag[j]==0)

				{

					cout<<result<<' ';

					flag[j]=1;

					break;

				}

			}

		}

	}

	cout<<endl;

}

int main()

{

	cin>>Test;

	while(Test--)

	{

		cin>>num;

		for(i=1;i<=num;i++)

			cin>>ps[i];

		change();

		cal();

		seq.clear();

	}

	return 0;

}

巴特西

POJ 1068：Parencodings

最新文章

热门文章