POJ 1068 Parencodings （模拟），暑假第一题~

最终考完高线大，头也不那么疼了，也最终有空来刷题了~。先来一发水题试试水

题目链接：http://poj.org/problem?id=1068

简单的模拟，麻烦在理解题意。，英语好的请无视这句；

【分析】

        S		(((()()())))

	P-sequence	    4 5 6666

	W-sequence	    1 1 1456

意思是，第n个右括号‘）’左边有Pn 个左括号 。。比如 456666 第1个右括号“）”左边有4个左括号 。第2个“）”左面有5个“（”..

让你得出相应的 W-sequence，1 1 1 4 5 6  相应Q1 Q2 ,,Qn

意思是。第n个右括号‘）’和左边第Qn个‘（’是一对；

第一个‘）’能够和它左边第一个'('结合，第二个‘）’也是能够和它左边第一个‘（’结合，，最后一个右括号能够和它左边第六个‘（’结合，  于是就有了 111456；

我们能够依据给出的 P-sequence 模拟出 S。将S 存到字符串中，再依据W-sequence的规则在S中遍历。就可以模拟求出结果；

【要求】

输入 P-sequence 输出相应的 W-sequence；

【代码】

#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	while(n--){
		int t;
		cin>>t;
		string str="";int num;
			int pre=0;
		for(int i=0;i<t;i++){
			
			cin>>num;
			int now=num-pre;
			for(int j=0;j<now;j++)
				str+='(';
			str+=')';
			pre=num;
		}
	//	cout<<str<<endl;//測试时 输出的模拟出来的字符串；
		int count=0;
		int len=str.length();
		for(int i=0;i<len;i++){
			if(str[i]==')'){
				int cnt1=0;
				int cnt2=0;
				for(int j=i;j>=0;j--){
					if(str[j]==')')
						cnt1++;
					if(str[j]=='(')
						cnt2++;
					if(cnt1==cnt2) //假设遍历到的左右括号个数同样，就说明是一对
					{
						if(count>0)
							cout<<' ';
						cout<<cnt1;
						count++;break;
					}
			}
		}
	}	cout<<endl;
	}
		
	return 0;
}