📄 1068 -- parencodings.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0049)http://acm.pku.edu.cn/JudgeOnline/problem?id=1068 -->
<HTML><HEAD><TITLE>1068 -- Parencodings</TITLE>
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK
href="1068 -- Parencodings.files/poj.css" type=text/css rel=stylesheet>
<SCRIPT language=javascript src="1068 -- Parencodings.files/poj.js"></SCRIPT>
<META content="MSHTML 6.00.2900.2802" name=GENERATOR></HEAD>
<BODY vLink=blue aLink=blue link=blue leftMargin=5><A name=top></A>
<TABLE style="BORDER-COLLAPSE: collapse" borderColor=#ffffff width="100%"
border=1>
<TBODY>
<TR>
<TD align=middle colSpan=5>
<TABLE class=h1 cellPadding=0>
<TBODY>
<TR>
<TD width="25%" alight="left"><IMG height=100
src="1068 -- Parencodings.files/logo1.jpg" border=0></TD>
<TD bgColor=#eaeffd colSpan=3>
<TABLE class=h2>
<TBODY>
<TR>
<TD><IMG height=90 src="1068 -- Parencodings.files/logo0.gif"
width=450 border=0></TD>
<TD width=95><IMG height=95
src="1068 -- Parencodings.files/logo3.gif" width=95
border=0></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR>
<TR vAlign=top align=middle bgColor=#6589d1>
<TH class=h>Online Judge</TH>
<TH class=h>Problem Set</TH>
<TH class=h>Authors</TH>
<TH class=h>Online Contests</TH>
<TH class=h>User</TH></TR>
<TR vAlign=top align=middle bgColor=#f1f1fd>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"><A
href="http://acm.pku.edu.cn/JudgeOnline/bbs">Web Board</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/">Home Page</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/faq.htm"
target=_blank>F.A.Qs</A><BR>Announcement</TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)">
<FORM action=gotoproblem method=get><A
href="http://acm.pku.edu.cn/JudgeOnline/problemlist">Problems</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/submit">Submit Problem</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/status">Online Status</A><BR><FONT
color=blue>Prob.ID:</FONT><INPUT size=6 name=pid><INPUT type=submit value=Go name=pb1></FORM></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)">
<FORM action=searchuser method=get><A
href="http://acm.pku.edu.cn/JudgeOnline/register">Register</A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/modifyuser">Update your
info</A><BR><A href="http://acm.pku.edu.cn/JudgeOnline/userlist">Authors
ranklist</A><BR><INPUT size=10 name=key><INPUT type=submit value=Search name=B1></FORM></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"><FONT
color=#1a5cc8>Current Contest</FONT><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/pastcontests">Past
Contests</A><BR><A href="http://acm.pku.edu.cn/JudgeOnline/contests"><FONT
color=red>Scheduled Contests</FONT></A><BR><A
href="http://acm.pku.edu.cn/JudgeOnline/awardcontest_announce.htm"
target=_blank><FONT color=red>Award Contest</FONT></A></TD>
<TD class=h onmouseover="scbg(this, 1)" onmouseout="scbg(this, 0)"
align=left>
<FORM action=login method=post>
<TABLE>
<TBODY>
<TR>
<TD>User ID:</TD>
<TD><INPUT size=10 name=user_id1></TD></TR>
<TR>
<TD>Password:</TD>
<TD><INPUT type=password size=10 name=password1></TD></TR></TBODY></TABLE><INPUT type=submit value=login name=B1> <A
href="http://acm.pku.edu.cn/JudgeOnline/register"
target=_parent>Register</A><INPUT type=hidden
value=/JudgeOnline/problem?id=1068 name=url></FORM></TD></TR></TBODY></TABLE>
<TABLE width="100%" background="1068 -- Parencodings.files/table_back.jpg"
border=0>
<TBODY>
<TR>
<TD>
<P align=center><FONT color=blue size=5>Parencodings</FONT> <BR>Time
Limit:1000MS Memory Limit:10000K<BR>Total Submit:3230 Accepted:1843
</P>
<P><FONT color=blue size=5>Description</FONT><BR><FONT
face="Times New Roman" size=3>Let S = s1 s2...s2n be a well-formed string
of parentheses. S can be encoded in two different ways: <BR>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). <BR>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).
<BR><BR>Following is an example of the above encodings: <BR><PRE><BR> S (((()()())))
<BR> P-sequence 4 5 6666
<BR> W-sequence 1 1 1456
<BR></PRE><BR>Write a program to convert P-sequence of a well-formed
string to the W-sequence of the same string. <BR></FONT>
<P></P>
<P><FONT color=blue size=5>Input</FONT><BR><FONT face="Times New Roman"
size=3>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.</FONT></P>
<P><FONT color=blue size=5>Output</FONT><BR><FONT face="Times New Roman"
size=3>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.</FONT></P>
<P><FONT color=blue size=5>Sample Input</FONT><BR><FONT
face="Times New Roman" size=3><PRE>2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
</PRE></FONT>
<P></P>
<P><FONT color=blue size=5>Sample Output</FONT><BR><FONT
face="Times New Roman" size=3><PRE>1 1 1 4 5 6
1 1 2 4 5 1 1 3 9</PRE></FONT>
<P></P>
<P><FONT color=blue size=5>Source</FONT><BR><FONT face="Times New Roman"
size=3><A
href="http://acm.pku.edu.cn/JudgeOnline/searchproblem?field=source&key=Tehran 2001">Tehran
2001</A></FONT></P></TD></TR></TBODY></TABLE><FONT color=#333399 size=3>
<P align=center>[<A
href="http://acm.pku.edu.cn/JudgeOnline/submit?problem_id=1068">Submit</A>]
[<A href="javascript:history.go(-1)">Go Back</A>] [<A
href="http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1068">Status</A>]
[<A href="http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=1068">Discuss</A>]
</FONT></P>
<P><IMG height=30 src="1068 -- Parencodings.files/home.gif" width=40
border=0><FONT size=3><A href="http://acm.pku.edu.cn/JudgeOnline/">Home Page</A>
</FONT> <IMG height=30 src="1068 -- Parencodings.files/goback.gif"
width=40 border=0><FONT size=3><A href="javascript:history.go(-1)">Go
Back</A> <IMG height=30 src="1068 -- Parencodings.files/top.gif"
width=40 border=0><A
href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1068#top">To
top</A></FONT><BR>
<HR>
<P style="FONT-FAMILY: Arial," align=center sans-serif Helvetica,>All Rights
Reserved 2003-2006 Ying Fuchen,Xu Pengcheng,Xie Di<BR>Any problem, Please <A
href="mailto:stycbackup@gmail.com">Contact Administrator</A></P>
<SCRIPT src="1068 -- Parencodings.files/urchin.js"
type=text/javascript></SCRIPT>
<SCRIPT type=text/javascript>_uacct="UA-790353-1";urchinTracker();</SCRIPT>
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -