POJ 1068-Parencodings Parencodings Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20210 Accepted: 12196 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 Source Tehran 2001
简单题。给一个括号字符串的P序列，要求算出其W序列。 直接计算即可，首先根据P序列还原出该括号字符串，因为P序列的每一个数字是对应右括号的，所以这个数字就表示这个右括号左边有多少个左括号，通过一个while循环就可以还原出原始括号字符串。 得到原始括号字符串之后，就可以计算W序列了。W序列的每一个数字也是对应右括号的，它表示从“和该右括号匹配的左括号”的位置到“该右括号”的位置一共有多少个右括号。这就要求我们知道每一个右括号匹配的左括号的位置，用一个堆栈可以简单求出。 求除了右括号及其匹配的左括号的位置后，就可以遍历括号字符串计算出期间共有多少个右括号了。 求解思路清晰之后，可以快速写出完整代码： [cpp] #include<iostream> #include<string> #include<vector> #include<stack> using namespace std; typedef struct PAR//括号结构 { char c;//左括号或右括号 int pos;//该字符的下标 }; //根据P-sequence还原出括号字符串 string get_parentheses(vector<int>& p) { string rs=""; vector<int>::iterator it=p.begin(); int i=0; while(it!=p.end()) { while(i!=(*it)) { rs+='(‘; i++; } rs+=’)’; it++; } return rs; } //根据括号字符串paren得到W-sequence void get_w(vector<int>& w,string paren) { int len=paren.size(); stack<PAR> s_p; PAR par; vector<int> right_pos,left_pos;//分别记录某个右括号对应左括号的位置 for(int i=0;i<len;i++) { if(paren[i]=='(‘)//如果是左括号，入栈 { par.c=paren[i]; par.pos=i; s_p.push(par); } else//右括号，出栈，配对 { par=s_p.top(); s_p.pop(); right_pos.push_back(i); left_pos.push_back(par.pos); } } vector<int>::iterator it_r=right_pos.begin(); vector<int>::iterator it_l=left_pos.begin(); while(it_r!=right_pos.end())//计算W-sequence { int num=0; for(int i=*it_l;i<=*it_r;i++) { if(paren[i]==’)’) num++; } w.push_back(num); it_r++; it_l++; } } int main() { int t,n; cin>>t; while(t–) { cin>>n; vector<int> p;//P-sequence int tmp; string parentheses; while(n–) { cin>>tmp; p.push_back(tmp); } parentheses=get_parentheses(p); vector<int> w;//W-sequence get_w(w,parentheses); vector<int>::iterator it=w.begin(); while(it!=w.end()) { cout<<*it<<" "; it++; } cout<<endl; } return 0; } [/cpp] 本代码提交AC，用时0MS，内存764K。]]>