📄 toj1743 - king's treasure.mht
字号:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: Problem 1743 | TJU ACM-ICPC Online Judge
Date: Thu, 11 May 2006 23:14:19 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
type="text/html";
boundary="----=_NextPart_000_0018_01C67550.A1A97A70"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2869
This is a multi-part message in MIME format.
------=_NextPart_000_0018_01C67550.A1A97A70
Content-Type: text/html;
charset="gb2312"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://cs.tju.edu.cn/acm/show_problem.php?pid=1743
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Problem 1743 | TJU ACM-ICPC Online Judge</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; charset=3Dgb2312">
<META content=3D"MSHTML 6.00.2900.2873" name=3DGENERATOR></HEAD>
<BODY>
<CENTER><A href=3D"http://cs.tju.edu.cn/acm/"><IMG height=3D80=20
alt=3D"Welcome to Tianjin University Online Judge"=20
src=3D"http://cs.tju.edu.cn/acm/pics/head.jpg" width=3D770 =
border=3D0></A></CENTER>
<HR>
<FONT face=3D"Times New Roman">
<CENTER><FONT color=3Dblue size=3D+2>King's Treasure</FONT></CENTER>
<HR>
<CENTER><FONT color=3Dgreen>Time Limit:</FONT> 2.0 Seconds =
<FONT=20
color=3Dgreen>Memory Limit: </FONT>65536K<BR><FONT color=3Dgreen>Total =
Runs:=20
</FONT>61 <FONT color=3Dgreen>Accepted Runs: =
</FONT>24</CENTER>
<HR>
<BR><BR>
<P>Long long ago, there is a mystical fable - king Arthur buried his =
mystical=20
treasure in the Death valley. Countless adventurers intrude in, yet no =
one has=20
the fortune.</P>
<P>Of course they can't, they don't have a map. However, Lucky Fanskyer =
find it.=20
It is a very tough job to translate such ciphered map, with the help of =
ACT the=20
organization, they finally understand:</P>
<LI>Every single point has an ordinal number, let's take a 6-node map as =
an=20
example.=20
<LI>The ciphered serials are 1, 2, 3, 2, 5 each represents the number =
that the=20
point is connected to only.=20
<LI>The first number is always 1, because the second point can only be =
connected=20
to the first one.=20
<LI>The second number may connect to 1 or 2, and in this situation it =
connected=20
the first point.=20
<P>As we can see, The fourth digit 2 tells us that the point 5 is =
connected to=20
point 2.</P>
<P>So, 1, 2, 3, 2, 5 corresponds to the following map:</P>
<P><TT><PRE>1 - 2 - 5 - 6
|
4 - 3
</PRE></TT>
<P></P>
<P>The distance between the points is the quantity of mutual connections =
(between each other) in chain. Thus, in example mentioned above the =
distance=20
between point #4 and #2 is 2, and between point #3 and #6 is 3. </P>
<P>We also deciphered that the Arthur King's treasure is in the Centers =
of the=20
map. </P>
<P>The definition of center is a definite point that has minimal =
distance to the=20
most remote point. In the shown example, point #2 is the unique center =
of the=20
map.</P>
<P>Your task is to help him to find all the possible centers of the =
map.</P>
<P><B>Input</B></P>
<P>This problem has multiple test cases.</P>
<P>The first line is a integer T represents the quantity of the test =
cases.</P>
<P>In the following lines, the first string contains integer N =
(2=A1=DCN=A1=DC240 000) --=20
quantity of the nodes. The other successive strings contain the ciphered =
map, --=20
N-1 numbers.</P>
<P>There maybe some whitespaces between all the numbers.</P>
<P><B>Output</B></P>
<P>Output is a single line for each case contains ordinal numbers of all =
the=20
centers of the determined map in ascending order seperating by exactly =
one=20
space. If the map has unique center, no trailing space is needed. </P>
<P><B>Sample Input</B></P>
<P><TT><PRE>2
6
1 2 3
2 5
3 1 1
</PRE></TT>
<P></P>
<P><B>Sample Output</B></P>
<P><TT><PRE>2
1</PRE></TT>
<P></P>
<P><B>Hint</B></P>
<P>Huge input, scanf() is recommended.</P>
<P><B>Author</B>: <A href=3D"http://blog.micy.cn/">BunnyQ</A>=20
@TJU</P><BR><BR><FONT face=3D"Lucida Handwriting,Arial"=20
color=3Dred><B>From:</B> <I><A style=3D"COLOR: red; =
TEXT-DECORATION: none"=20
href=3D"http://cs.tju.edu.cn/acm/search_process.php?s=3DTJU+Contest+Septe=
mber+2005">TJU=20
Contest September 2005</A></I></FONT>
<HR>
=20
<CENTER><A =
href=3D"http://cs.tju.edu.cn/acm/submit.php?pid=3D1743">Submit</A> =
<A =
href=3D"http://cs.tju.edu.cn/acm/list_problem.php?vol=3D8"><FONT=20
color=3D#00a000>List</FONT></A> <A=20
href=3D"http://cs.tju.edu.cn/acm/forum.php?pid=3D1743"><FONT=20
color=3D#006060>Forum</FONT></A> <A=20
href=3D"http://cs.tju.edu.cn/acm/problem_stat.php?pid=3D1743">Statistics<=
/A></CENTER>
<HR>
<CENTER>
<TABLE border=3D0>
<TBODY>
<TR>
<TD align=3Dright width=3D500><A =
href=3D"http://cs.tju.edu.cn/acm/"><FONT=20
color=3Dblue>Tianjin University Online Judge</FONT></A> <FONT=20
color=3Dred>v1.1.5</FONT></TD>
<TD align=3Dright width=3D270><FONT color=3Dgray>PageView:=20
=
2216987</FONT></TD></TR></TBODY></TABLE></CENTER></FONT></LI></BODY></HTM=
L>
------=_NextPart_000_0018_01C67550.A1A97A70
Content-Type: image/jpeg
Content-Transfer-Encoding: base64
Content-Location: http://cs.tju.edu.cn/acm/pics/head.jpg
/9j/4AAQSkZJRgABAgAAAQABAAD/4QDmRXhpZgAASUkqAAgAAAAFABIBAwABAAAAAQAAADEBAgAc
AAAASgAAADIBAgAUAAAAZgAAABMCAwABAAAAAQAAAGmHBAABAAAAegAAAAAAAABBQ0QgU3lzdGVt
cyBEaWdpdGFsIEltYWdpbmcAMjAwNTowNDoyNCAxNzo1ODoxMwAFAACQBwAEAAAAMDIyMJCSAgAE
AAAANzEwAAKgBAABAAAAAgMAAAOgBAABAAAAUAAAAAWgBAABAAAAvAAAAAAAAAACAAEAAgAEAAAA
Ujk4AAIABwAEAAAAMDEwMAAAAAAAAAAA/8AAEQgAUAMCAwEiAAIRAQMRAf/bAIQAAgEBAQEBAgEB
AQICAgIDBQMDAgIDBgQEAwUHBgcHBwYHBggJCwkICAoIBgcKDQoKCwwMDQwHCQ4PDgwPCwwMDAED
AwMEAwQIBAQIEgwKDBISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhISEhIS
EhISEhIS/8QAvwAAAQUBAQEBAQAAAAAAAAAABAMFBgcICQIAAQoQAAEDAwMDAgQDBQQECQgLAAEC
AwQFBhEABxIIITETQQkUIlEyYcEVFiNxgUJSkaEKFyRiJTM3Q3J1sbK0GDQ4Y3ST0tMpNlN2gpSi
tcLR8AEAAQUBAQEAAAAAAAAAAAAABAECAwUGAAcIEQABAwMDAgMGBAYCAgMAAAABAgMRAAQhBRIx
QVEGYXETIoGRobEUMsHwBxUjQtHhFlIz8SRicv/aAAwDAQACEQMRAD8A7+a+19r7XV1faErldots
0iRX7iq0eDBiILj0uW4G22kj3Uo9gNNu5m5VlbP2HVNy9xa8zTKLR2FSJUx84CEj2H3JOAAO5JA1
yE6uOsjfD4hG5ldsG236RQdu7Kmsz6jVHa+WIVBgNhSlzJy2grktSkoSlopUpSlcWxnkrQN7fIs0
5yT0qx0/TnL9RjCRya1J1b/HM2i2qNTs3p/p8C4Ljhy0U5ty4pBgRXZKgohDfIDmQAD9am85GOWs
51nqx+Lf1HKlXNaVDuGh23Ulinw0Vl6PaLByriqVHlOqQp5KsfwxhRyvCgoDKoTT7lt3p7uh2w9i
LGn1O+6HMjVqJuPf8V6qTLhjvJ9RcaFE+UkIpvzGCGkpSt8iHJbV6biRq/dlPh1371D0CtbgdRG3
SqZMv+0qlb06beM5ybW2EuOsSqPMSSSpt+OlSmHRltSlRG14JOsu9qNxcHKo9K0iLWzsUbtg9VZJ
x2x/meRVDXvYnXrYNvUq9dxutCxqXGcjtVChVavbgvNprjbp4pdlFCVtlpSzlHprxhPDkQSsSK0r
/wDi47by65Tdr9xzeb0BxLkw2zdMW5hRZA+pUIU8LU8pCkhwJUpHMkI7JCVKOxN3fhm2Xvm5YMHc
K/pTFHtGh06izqNQ0LiipoiIfThD6VhxlCzIUCBk8U4z3OqWqnwjt87Wsy47bs3ca26iqaurSaTI
jCTDkRJc91ppt9fqrcQExIy5ZSlsp5KUPpBUTocOvJMhRpRd2zqYXtn/APOP3++9GdP3x3J1Orrl
pdV+266O3GhGS7OkpTT6o0psEPpcpyiVZQULUSOKeOMEnXQDZ7evazf2yYu4m0V5w63SZaQpEmIr
unIzhSTgpP5EDXJnf3fmzKBdta2n61tk6/UKbQV02g2xIulofvZxfedEyvO1RIcVwU24kIjoBb5v
MscCQrELpV7b2/Dtv5vfLYLdaZuDZzcNFOfqEyvR/wDg6V6nqppdYijKGZQbeUnPq8SWjwKVJKNW
1pq7jatrx3D60Jc6Q1cJ3sjao8f9T1x9Ptmu4evxX4dVx0sdTFl9VG1MPca1OEaTxQio0gvoecp7
6kJXwKkEhSSlQUlQ7KSQfOQLHV+HWmbWlxIWkyDWXcbU0ooWIIpJfjSbntpRfjSbntqUUyklfi15
UkqIA16V+LTXd8Wsz7dlQbdmqjTnUYZkJ/sKzkZ7jt2wf56VaihBUkSR0705IClAExRsj5aI0qRN
kIabT5W4rAGq73P6mtt9taY9OlVRjiwkqU++rg0gDzk+f+zWYd1Oo++KJTp06qTvU+TSrK0rKgv/
AKJx2Hb31zW3JqvX98TXc+VtbsVt/XBQIzpQ7IbSplnjnHJbquyU9/JOvP2fFd5r7v4bSW9scqV0
+FaheiW2lth++XPYDrXQdj46O2l57/RdjNtaRFrhkL9Az4Ta+CXMjsFcu+ATk49hrcVHmPVCkRp0
hHFbzYWU/bOsE/DH+CVB6QpTG5W80yBULlxyEeKorRGP25YwT+ffW/8AghtCW2xhKRgDW+0y2dtW
Ah9wrV1J/fFZq6dQ84VNpCR2FeF+NIO/rpdfjSDv66s00PSaIxklSQoDHudfn7KcTICV9068SGUy
4b8FwKKH0KbVwODggg4PtrOFC6kLksne+Js+uqpkzH5xhqgJIUHQHCkqSn27Jznt4OqDWvEKNDda
S8glK8SMwfSrOw0xWoocU2oApEwe3rVv7i762lYEhyDUYBUlhZQ6UKHPHY5AOPz7Z79u/fUgpkVF
fp6KvT3QuO8gONrGRzSRkH/DWYuoSps1fcSoPR5Tb7apDgCwv+Gr8sj2GcdtUL1xdU/UzT1Q+mrp
Nps+8KnNabYRVI7S+EVPEAhKP938OTrF6Z42vzqT9mUe0zCACBmT8SIjpj41oLvw9bJs2rgK24lR
Mnt9a6CPOR/VUw0+lakeQk9xpBfnVF9Auz3UDtRtE2epK4RKuCd/EcZLvqFnPfBP31ei/OvYmiVJ
BUINYox0pF/wdCPeNFv+DoVaeSgn76JTTKGeH5aHX76fqrV7LtqnI/b0pTSnE8itKeQbHgE++M/b
J/I9tRNF52ZV5iYtDuGLIW6nmlDLgUSP0/l5GhrfU7W4uFWqFjenkTn5VMu2dQ2HVJO09elKu/ro
V3xop39dCu+NWyagNDO986doVAob9PS7NrDLLzhwhDy+GfucnsAO3kjyNN8aC9UH/l2BlR0pc1i1
122pqVHHpMqkAkq+gtgryAD5KUqT3yPqOq7W7t6zsXX7WCtIJAPWMkfL60RZtIefQ26YBMfOkI9v
SZVTEaMgqAV3OhN/dwpm0lBStM4NqDAJRyKSnJOAR75wkj28ajm3O+yLDhPUudTmpRaVhCllfNP0
+O3YjJz/AE1kP4nkjqJ6n36Vt3sw9IRKqTx5KbUW8gDOMjsAAn/LXket+OmfE9qxp9idjrhAM/2n
rn7Vr7PQHNKecubkbkIB+Pw+9bNsO/LGr9uMVO77hirqhYS5KixXG18VqJI7JICRwKcj+9nAx4hl
zdRWwr10M2hbl4xXqo6+tg09CsutqSEklQ8AHmMd/Y6y5cHTbTfhgdBVaujcfcF6o3fXGf4J5gBp
0kH+GSeR7p45OexV9u+f/g/9PV57kbhzeom+Z8pxn1FFlT6lH1CTknv/AP7trb+H73WP5p/L3HAp
tpIB5JmOCo8nqfMxVDfN2n4YPpBC1Enyj07dB6V08cORkfbQzv66JcGBgew0M7+uvUE1RUk57aHc
9tEOe2h3PbU6aaaFd99Du++iHffQ7vvqZNJSR8HSLv6aWPg6Rd/TUorqGc99Iue2lnPfSLntqUUh
pBzwdeNKFC3Fem2kqUo4CR5J0u5Qa0zLRT3KTID7v4GOBK1f086jcumGVpadWApUwCQCYyYHWOva
lCFKBIGKb3f10ivzp0kW5V2Kgikzo6Ikp3KkRpzqY7igPJCVkHTSl+NIAciSmnkEZS6wsLQofcKH
Yj8xqOz1bT751TFq+hak8hKgSOmQDIzinLZcbG5aSB6V5V+LSR8nRL66VTIIrFenKYjKc9NIaAUt
wgAqwCQMJCk5Of7QwDpmqN/WPJ3QlbY0BE5p+nxWZMmRUCnCfUZS+cJQCcJbcb+5KlYAyBkK48Ua
ZaXgsnVncd2YO0bU7lSqNuBE5MEgHJqRNo6tHtAMY9c4GKc0/h0oPA013hf22doS6TRjc0qRMqyH
nW8xfSZQhtSEk+oVZJKl4ACc/So9sadY1Tq0enSZFtrbEp+G820t1sLSkqbUAog/bOf6aYvxLau6
Xc6nZArDIXIIUgkoBKk++kHkRMQDI6GlFqsPJZcxujz59KVT+LSyfw6jVmX3A/dePcV7x3WVyMqb
jJV6fJAUU81KIOASlWAASeJ/CME/t5b8WpZ9/wAqyott0msophSiaKU9J9RC1ISvilxRCchK0E/w
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -