HDOJ 5510-Bazinga【模拟】

骑猪看日落 2022-08-20 14:10 7阅读 0赞

# Bazinga #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1468 Accepted Submission(s): 457

Problem Description

Ladies and gentlemen, please sit up straight.  
**Don't tilt your head**. I'm serious.  
![C645-1002-1.jpg][]  
For  n![Image 1][] given strings  S![Image 1][]1![Image 1][],S![Image 1][]2![Image 1][],⋯,S![Image 1][]n![Image 1][]![Image 1][], labelled from  1![Image 1][] to  n![Image 1][], you should find the largest  i(1≤i≤n)![Image 1][] such that there exists an integer  j(1≤j<i)![Image 1][] and  S![Image 1][]j![Image 1][]![Image 1][] is not a substring of  S![Image 1][]i![Image 1][]![Image 1][].  
  
A substring of a string  S![Image 1][]i![Image 1][]![Image 1][] is another string that occurs **in**  S![Image 1][]i![Image 1][]![Image 1][]. For example, \`\`ruiz" is a substring of \`\`ruizhang", and \`\`rzhang" is not a substring of \`\`ruizhang".

Input

The first line contains an integer  t(1≤t≤50)![Image 1][] which is the number of test cases.  
For each test case, the first line is the positive integer  n(1≤n≤500)![Image 1][] and in the following  n![Image 1][] lines list are the strings  S![Image 1][]1![Image 1][],S![Image 1][]2![Image 1][],⋯,S![Image 1][]n![Image 1][]![Image 1][].  
All strings are given in lower-case letters and strings are no longer than  2000![Image 1][] letters.

Output

For each test case, output the largest label you get. If it does not exist, output  −1![Image 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亚洲区沈阳站-重现赛（感谢东北大学） ][2015ACM_ICPC_-_]

解题思路：

就是找到一个最大的下标字符串，上面的字符串不是这一串的字串。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char map[2000][2000];
    int main()
    {
    	int T;
    	int yy=0;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int n,i,j,k;
    		scanf("%d",&n);
    		for(i=1;i<=n;i++)
    		{
    			scanf("%s",map[i]);
    		}
    		int ans=-1;
    		for(i=n;i>1;i--)
    		{
    			if(!strstr(map[i],map[i-1]))
    			{
    				ans=max(ans,i);
    				for(j=i-1,k=i+1;k<=n;k++)
    				{
    					if(!strstr(map[k],map[j]))
    					ans=max(ans,k);
    				}
    			}
    		}
    		printf("Case #%d: %d\n",++yy,ans);
    		
    	}
    	return 0;
    }

[C645-1002-1.jpg]: /images/20220731/7333718308104a8ba278b7732daa3e5f.png
[Image 1]: 
[2015ACM_ICPC_-_]: http://acm.hdu.edu.cn/search.php?field=problem&key=2015ACM%2FICPC%D1%C7%D6%DE%C7%F8%C9%F2%D1%F4%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B6%AB%B1%B1%B4%F3%D1%A7%A3%A9&source=1&searchmode=source