「NOIP模拟赛」擒贼先擒王
公元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、加上最外围括号,返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<set> #include<map> #define ll long long #define inf 100000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,mx,ans; string str[105]; int cnt[105]; map<string,int> mp; string solve(string s) { string ans=""; if(s[0]!='(') { for(int i=0;i<s.length();i++) if(s[i]!='0') for(;i<s.length();i++) ans+=s[i]; if(ans=="")ans="0"; } else { int top=1; int left=0; string q[105];q[1]=""; for(int i=1;i<s.length()-1;i++) { if(s[i]=='(')left++; if(s[i]==')')left--; if(s[i]==','&&!left)q[++top]=""; else q[top]+=s[i]; } for(int i=1;i<=top;i++)q[i]=solve(q[i]); sort(q+1,q+top+1); ans+='('; for(int i=1;i<=top;i++) { if(q[i]!=q[i-1]||i==1) { ans+=q[i]; if(i!=top) ans+=','; } } if(ans[ans.length()-1]==',')ans.erase(ans.length()-1); ans+=')'; } return ans; } int main() { //freopen("king.in","r",stdin); //freopen("king.out","w",stdout); n=read(); for(int i=1;i<=n;i++) { cin>>str[i]; str[i]=solve(str[i]); } for(int i=1;i<=n;i++) { int t=mp[str[i]]; if(!t)mp[str[i]]=i,cnt[i]=1; else cnt[t]++; if(cnt[t]>mx)ans=t,mx=cnt[t]; } printf("%d\n%d\n",mx,ans); return 0; } |