HDU-5510 Bazinga （字符串水题）

发表于 | 更新于 | 阅读次数：

题目链接

题意很简单：输入n 然后输入n个字符串，求最大的i， 要求1 ~ i-1 中至少有一个串不是i的子串
思路：直接遍历就行，两个for循环嵌套（注意，都是自上而下开始），用strstr判断是不是子串，若是，就打上标记（此串相当于废弃了，即不需要再判断），这样就减少了对strstr的调用。针对这道水题的数据来说，这样做大大减少了时间，让我们逃出了TLE的泥沼

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <string.h>
char ch[501][2002];
int main()
{
    int T;
    scanf("%d", &T);
    int n;
    for (int i = 0; i < T; i++)
    {
        scanf("%d", &n);
        for (int j = 0; j < n; j++)
        {
            scanf("%s", ch[j]);
        }
        int idx[501] = {};
        int ans = -1;
        int f = 1;
        for (int l = 1; l < n; l++)
        {

            for (int k = 0; k < l; k++)
            {
                if (idx[k])
                    continue;
                if (!strstr(ch[l], ch[k]))
                {
                    ans = l + 1;
                }
                else
                {
                    idx[k] = 1;
                }
            }
        }
        printf("Case #%d: %d\n", i + 1, ans);
    }
    return 0;
}
0%