明明原理都一样,为什么我的代码过不了?

P8306 【模板】字典树

ZY_202301005129 @ 2024-11-16 00:42:00

首先是我的代码,

// P8306 【模板】字典树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int s[62] = {0};//前26个存储字母,后面的储存数字
    int end=0;
    int num=0;
}t[3000005];
int n, m;
void add(string a,node *t,int&p)
{
    int now=0;
    for (auto i = a.begin();i != a.end();i++)
    {
        int j;
        if (*i >= '0' && *i <= '9')
            j = 52 + *i - '0';
        else if (*i >= 'a' && *i <= 'z')
            j = *i - 'a';
        else j = *i - 'A' + 26;
        if (!t[now].s[j])
            t[now].s[j] = ++p;

        now = t[now].s[j];
        if (i + 1 != a.end())
        t[now].num++;
    }
    t[now].end++;
}
int find(string a,node*t)
{
    int now = 0;
    int sum;
    for (auto i = a.begin();i != a.end();i++)
    {
        int j;
        if (*i >= '0' && *i <= '9')
            j = 52 + *i - '0';
        else if (*i >= 'a' && *i <= 'z')
            j = *i - 'a';
        else j = *i - 'A' + 26;
        if (!t[now].s[j])
            return 0;
        else now = t[now].s[j];
        //sum = t[now].num;
        //if (i + 1 == a.end())
            //sum += t[now].end;
    }
    return t[now].end+ t[now].num;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //取消同步流
    int x;cin >> x;
    while (x--)
    {
        int p=0;
        cin >> n >> m;
        memset(t, 0, sizeof(t));
        for (int i = 1;i <= n;i++)
        {
            string a;cin >> a;
            add(a,t,p);
        }
        for (int i = 1;i <= m;i++)
        {
            string a;cin >> a;
            cout << find(a,t) << "\n";
        }
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件

其次是一个题解的代码,这个代码甚至用的是手动置0,我原本是用局部变量初始化来规避生成时间,本来能过第二点,结果模仿ta的代码后第二个都过不了了......

#include<bits/stdc++.h>
using namespace std;
int T, q, n, t[3000005][65], cnt[3000005], idx;
char s[3000005];
int getnum(char x) {
    if (x >= 'A' && x <= 'Z')
        return x - 'A';
    else if (x >= 'a' && x <= 'z')
        return x - 'a' + 26;
    else
        return x - '0' + 52;
}
void insert(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0;i < len;i++) {
        int c = getnum(str[i]);
        if (!t[p][c])
            t[p][c] = ++idx;
        p = t[p][c];
        cnt[p]++;
    }
}
int find(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0;i < len;i++) {
        int c = getnum(str[i]);
        if (!t[p][c])
            return 0;
        p = t[p][c];
    }
    return cnt[p];
}
int main() {
    scanf("%d", &T);
    while (T--) {
        for (int i = 0;i <= idx;i++)
            for (int j = 0;j <= 122;j++)
                t[i][j] = 0;
        for (int i = 0;i <= idx;i++)
            cnt[i] = 0;
        idx = 0;
        scanf("%d%d", &n, &q);
        for (int i = 1;i <= n;i++) {
            scanf("%s", s);
            insert(s);
        }
        for (int i = 1;i <= q;i++) {
            scanf("%s", s);
            printf("%d\n", find(s));
        }
    }
    return 0;
}

by lhz2022 @ 2024-11-17 23:34:39

@ZY_202301005129

你说有没有一种可能,就是要手动清0

memset又不是O(1)的


by ZY_202301005129 @ 2024-11-19 15:39:06

@lhz2022搞不懂,用了memset速度难道还比手动慢吗?那memset存在的意义是什么


by ZY_202301005129 @ 2024-11-19 16:31:08

搞清楚错因了,供大家参考一下挨: 1.清零操作是一个非常消耗性能的事,但是不清不行,所有根据上一次所累积到的p值为清零的界限,手动和memset的区别不大 2.使用取消同步流可能会导致输出错误(没学,搞不太懂)

我分析的原因大致就是这样,有讲错的地方请指正


|