HDU_5510_Bazinga

2018-06-17 21:48:20来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5056    Accepted Submission(s): 1596


Problem Description
Ladies 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 (1in) such that there exists an integer j (1j<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".
 

 

Input
The first line contains an integer t (1t50) which is the number of test cases.
For each test case, the first line is the positive integer n (1n500) 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.
 

 

Output
For each test case, output the largest label you get. If it does not exist, output 1.
 

 

Sample Input
4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc
 

 

Sample Output
Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3
 

 

Source
2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)
 
  • 找到最大ID字符串i使得存在j<i的字符串不是i的子串
  • 首先考虑如果从l到r串都满足都是r的子串,那么k>r串只需要检测r串即可
  • 如果自l串开始到l+k串都是存在小于l的串不是当前串子串,那么对于l+k+1串就要检测l-1串和l到l+k串
  • 算法出来了,就是记录当前最大id使得此id之前全是id串的子串,然后检测串的范围就是这个id到当前ID的前一位
  • 如果用这样的算法,用c的strstr即可,用kmp可以减少一半时间

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int T, n, use[maxn], mx, ans;
25 char s[505][2005];
26 std::vector<int> v;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         for(int kase=1;kase<=T;kase++){
32             ans=-1;
33             scanf("%d",&n);
34             mx=1;
35             use[1]=0;
36             v.clear();
37             scanf("%s",s[1]);
38             for(int i=2;i<=n;i++){
39                 scanf("%s",s[i]);
40                 int flag=1;
41                 if(strstr(s[i],s[mx])==NULL)
42                     flag=0;
43                 if(flag&&use[i-1]){
44                     for(int j=v.size()-1;j>=0 && flag;j--){
45                         if(strstr(s[i],s[v[j]])==NULL)
46                             flag=0;
47                     }
48                 }
49                 if(flag){
50                     mx=i;    use[i]=0;    v.clear();
51                 }else{
52                     ans=i;    use[i]=1;    v.push_back(i);
53                 }
54             }
55 
56             printf("Case #%d: %d\n",kase,ans);
57         }
58     }
59     return 0;
60 }

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU_5512_Pagodas

下一篇:HDU_1457_后缀自动机四&#183;重复旋律7