【Bazinga HDU - 5510 】【考察strstr()的使用】【贪心】-白红宇

【Bazinga HDU - 5510 】【考察strstr()的使用】【贪心】

阅读量：4966 次

发布时间：2019-06-12

本文共 1391 字，大约阅读时间需要 4 分钟。

题意分析

1.题目大致说的是让你输出符合这种条件（在所给的字符串中至少有一个不是它的子串）的字符串对应的label，若没有输出-1；

2.判断子串可以用string.h下的strstr（s1, s2）函数，若s2 是s1的子串则返回在s1中s2首字母对应的地址，若不是则返回NULL，想进一步了解strstr可访问；

3.如果只是暴力比较两个字符串是否某个是某个的子串时会超时，还需进一步优化；

4.设那个符合条件的初始位置maxx=-1，可以从最后一个字符串开始遍历（因为它最长，越在后面的越有可能符合条件），比较相邻的两个字符串，若短的是长的子串，则继续遍历，否则即短的不是长的子串时，可以更新maxx了，不过还没完，再进行进一步的判断；

5.既然该串符合条件，那么位于它后面的串中倘若有的包含它，并且在位于它之前的字符串中含有不属于它的串，这样maxx就可以更大了，详细情况见AC代码。

AC代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                using namespace std;const int maxn = 2000 + 10;char s[500+10][maxn];int T, n;int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d", &T); for(int t = 1; t <= T; t++) { scanf("%d", &n); memset(s, 0, sizeof(s)); for(int i = 1; i <= n; i++) scanf("%s", s[i]); int maxx = -1; int ff = 0; for(int i = n; i >= 2; i--) { if(strstr(s[i], s[i-1]) == NULL) //短的不是长的子串，符合条件 { maxx = max(maxx, i); for(int j = i + 1; j <= n; j++) { if(strstr(s[j], s[i]) != NULL) //试图寻找更大位置的符合条件的串 { int flag = 0; for(int k = i; k >= 1; k--) { if(strstr(s[j], s[k]) == NULL) { flag = 1; break; } } if(flag) maxx = max(maxx, j); else { ff = 1; break; } } } } if(ff) break; } printf("Case #%d: %d\n", t, maxx); }}

转载于:https://www.cnblogs.com/KeepZ/p/11470477.html

你可能感兴趣的文章