首页 > 代码库 > HDU-5510 Bazinga
HDU-5510 Bazinga
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2390 Accepted Submission(s): 746
Problem DescriptionLadies and gentlemen, please sit up straight.
Don‘t tilt your head. I‘m serious.
For n given strings S1,S2,?,Sn, labelled from 1 to n, you should find the largest i (1≤i≤n) such that there exists an integer j (1≤j<i) and Sj is not a substring of Si.
A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".
InputThe first line contains an integer t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500) and in the following n lines list are the strings S1,S2,?,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.
OutputFor each test case, output the largest label you get. If it does not exist, output −1.
Sample Input45ababczabcabcdzabcd4youlovinyouaboutlovinyouallaboutlovinyou5dedefabcdabcdeabcdef3abacccSample OutputCase #1: 4Case #2: -1Case #3: 4Case #4: 3
题意:
求i最大的且其前无子串的字符串,若无则输出-1。
我们运用了求子串函数strstr(); 关于strstr();的介绍请见:http://www.cnblogs.com/Kiven5197/p/5869909.html
先找两个相邻 若找出不匹配的串再反向对比。
附AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 //strstr(); 5 6 char s[510][2010]; 7 8 int main(){ 9 int t,n;10 scanf("%d",&t);//cin>>t;11 int ans=1;12 while(t--){13 scanf("%d",&n);//cin>>n;14 for(int i=1;i<=n;i++){15 scanf("%s",s[i]);//cin>>s[i];16 }17 int res=-1;18 for(int i=n;i>0;i--){19 if(!strstr(s[i],s[i-1])){20 res=max(i,res);21 for(int j=i+1;j<=n;j++){22 if(!strstr(s[j],s[i-1])){23 res=max(j,res);24 }25 }26 }27 }28 printf("Case #%d: %d\n",ans++,res);//cout<<"Case #"<<ans++<<": "<<res<<endl;29 }30 return 0;31 }
这题第一发用的cin和coutT掉了..改成scanf printf就A了
HDU-5510 Bazinga
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。