首页 > > 程序设计 > C/C++ >

HDU_5510_Bazinga

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

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

Input

The first line contains an integer

Output

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

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 }