「NOIP模拟赛」擒贼先擒王

2014年11月2日3,4220

公元3941年10月,宇宙中最具侵略野心的X星人发现了地球。他们以月球为据点,向人类开战。同年12月7日,X星人一次成功的偷袭,使人类军队遭到重创,以至在军事力量上,人类无法与X星人抗衡。
X
星人正沉醉在偷袭成功的喜悦中时,老Z——人类社会的头号间谍,秘密地潜入月球,盗取了X星军队的一份绝密军事材料。
WREAMC(World Resist Extraterrestrial Aggression Military Committee
,世界反外来侵略军事委员会)于12月8日凌晨4时接到了这份绝密材料,通过3小时的研究,WREAMC有足够的证据说明该材料中包含 了X星军队所有成员的个人档案。据《宇宙法》513条:档案是宇宙生物的唯一标识。然而,WREAMC发现,X星军队档案集中有些档案所描述的内容本质上 是一样的。换句话说,某些成员的个人档案在该档案集中曾多次出现。
WREAMC
猜想,某个成员的档案在该档案集出现的频率越高,该成员在X星军队中的地位就越高。而档案出现频率最高的,自然就是X星军队的首领(你不必怀疑该猜想的正确性,我们应该相信WREAMC成员的直觉)。
正所谓“擒贼先擒王”,在人类军事力量处于劣势的情况下,WREAMC决定集中力量,消灭X星军队的首领。你的任务就是根据这份档案集,帮助WREAMC找到X星军队首领的档案。
为了便于你的研究,WREAMC已经将档案集简化成了巴科斯-瑙尔范式(BNF):

<档案>     ∷= ( <属性> | <子女档案> { , <属性> | <子女档案> } )
<
子女档案> ∷= <档案>
<
属性>     ∷= <数字> { <数字> }
<
数字>     ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

注:其中“∷=”表示定义为,“|”表示或,“{…}”内的项可以重复任意多次或不出现。

X星人的个人档案和人类的一样,包括了本人的各种属性。为了便于研究,我们用不同的整数来表示不同的属性,数值相同则属性相同。(注意是数值,不是字符串)
与人类档案略有不同,X星人的个人档案中还包含他亲生子女的个人档案。
X
星人的个人档案中的属性和子女档案都可能有重复,这些重复将被忽略。
X
星人的个人档案中的属性和子女档案可以按任意顺序在档案中出现。

「输入」

输入文件的第1行为档案集中档案的条数n(1≤n≤100)。
输入文件的第2行至第n+1行每行表示一条档案。
每条档案的长度不超过100字符。
输入文件中没有多余的空格。
输入文件中保证X星军队中有且仅有一个首领。

「输出」

输出文件有两行
输出文件第一行为一个整数,表示AAA军队首领档案在档案集中出现的次数。
输出文件第二行为X星军队首领在输入文件首次出现的档案的序号。

「输入输出样例」

king.in
6
(3,3,(
01,3),2,(2,3),(3,2))
(2,(3,1),3,(3,2),(1,3,1))
(2,3,(3,1),(1,3,1))
(((1231231231)))
((1231231231))
(1231231231)

king.out
2
1

题解

除了题目比较绕没什么难度嘛

按照相同的规则处理字符串,使得相同的字符串相等,不同的字符串不等,然后判断。

处理方法:

1、如果字符串不含括号,也就是只有一个数,去前导零后返回。

2、去掉最外围括号。

3、将所有逗号隔开的字符串递归处理。

4、将处理的结果字符串按字典序排序,加上逗号。

5、加上最外围括号,返回

 

avatar
  Subscribe  
提醒