题目数据疑似较弱
查看原帖
题目数据疑似较弱
505544
shaoyifan楼主2024/7/21 00:17

如题,我使用一份错误的代码通过了这道题,但是这是一个假做法。

例如,这么一个数据:

1
aabbcc
3
aab
aab
aab

我的输出是:

WRONG
REPEAT
REPEAT

这显然是不合题意的。

问题出现在 trie 树的查询中。我的代码对于这种数据是错误的:存在字符串 TT,如果 TT 名字错误,但是是某一个正确名字的前缀,而且这个数据被查询到至少两次。

在我的代码中:第一次查询返回 0,之后返回 -1。也就是第二次查询 TT 返回的答案均为错误答案,但是这样仍然通过了这一道题。

所以我希望可以加强这道题的数据。

// 这是我的提交记录
// https://www.luogu.com.cn/record/167481169
const int M = 5e5 + 10;
int son[M][30], cnt[M], idx;
char str[55];

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];  
    }
    cnt[p] ++;
}
// 查询的逻辑是错误的
int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    int res = cnt[p];
    cnt[p] = -1;
    return res;
}
int main()
{
    int n, m;
    scanf("%d", &n);
    while (n --) {
        scanf("%s", str);
        insert(str);
    }
    scanf("%d", &m);
    while (m --) {
        scanf("%s", str);
        int res = query(str);
        if (res > 0) printf("OK\n");
        if (res == 0) printf("WRONG\n");
        if (res == -1) printf("REPEAT\n");
    }
} // 忽略了其余部分
2024/7/21 00:17
加载中...