额外减小 发表于 2023-9-30 20:55:35

关于字典树的题目，奇怪的是：

最后一个点AC了 。
其他点都是RE。
是不是说明我的整体思路没毛病？

评测记录
https://www.luogu.com.cn/record/126745207
题目链接
https://www.luogu.com.cn/problem/P8306

rt.

我真的不理解，最后一个点AC是不是表示整体的逻辑没问题？

但找不到RE的原因。

求调，感激不尽

马蜂有点怪。希望您能原谅。

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

struct Node {
    char data;
    Node* next;
    int down_cnt;
};

typedef Node* Trie;

int trans(char ch) {
    if (ch >= 'A' && ch <= 'Z')
      return ch - 'A';
    return ch - 'a' + 26;
}

Trie init_Trie() {
    Trie trie = new Node;
    trie->data = '\0';
    trie->down_cnt = 0;
    memset(trie->next, 0, sizeof(trie->next));
    return trie;
}

void add(const char* str, Trie trie) {
    Trie ptr = trie;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
      if (ptr->next)] == nullptr) {
            ptr->next)] = init_Trie();
            ptr->next)]->data = trans(str);
      }
      ptr->down_cnt++;
      ptr = ptr->next)];
    }
}

void dfs(const char* str, int p, int len, Trie &trie) {
    if (p == len - 1) {
      cout << trie->down_cnt << endl;
      return;
    }
    if(trie->next)]==nullptr)
    {
      cout<<0<<endl;
      return ;
    }
    dfs(str, p + 1, len, trie->next)]);
}

void free_Trie(Trie trie) {
    if (trie == nullptr) {
      return;
    }
    for (int i = 0; i < 60; i++) {
      free_Trie(trie->next);
    }
    delete trie;
}

int main() {
    int t, n, q;
    string str;
    cin >> t;
    while (t--) {
      Trie trie = init_Trie();
      cin >> n >> q;
      for (int i = 0; i < n; i++) {
            cin >> str;
            add(str.c_str(), trie);
      }
      for (int i = 0; i < q; i++) {
            cin >> str;
            dfs(str.c_str(), 0, strlen(str.c_str()), trie);
      }
      free_Trie(trie);
    }

    return 0;
}

陶远航 发表于 2023-9-30 20:55:48

在这个问题中，RE错误通常会发生在内存访问超出范围时。在查看代码后，我发现可能存在以下问题：

1. 在 for 循环中，当对指针进行解引用并访问下一个字符的 next 指针时，可能会访问到空指针。在调用 add 函数时，应该先判断 ptr->next)] 是否为 nullptr。

2. 在递归 dfs 函数时，如果在字典树中找不到对应的字符节点，也会访问到空指针。在递归之前，应该首先判断 trie->next)] 是否为 nullptr。

因此，可以尝试使用以下代码实现修复：

void add(const char* str, Trie trie) {
    Trie ptr = trie;
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
      if (ptr->next)] == nullptr) {
            ptr->next)] = init_Trie();
            ptr->next)]->data = trans(str[ i]);
      }
      ptr->down_cnt++;
      ptr = ptr->next)];
    }
}

void dfs(const char* str, int p, int len, Trie &trie) {
    if (trie == nullptr) {
      cout << 0 << endl;
      return;
    }
    if (p == len - 1) {
      cout << trie->down_cnt << endl;
      return;
    }
    dfs(str, p + 1, len, trie->next)]);
}

int main() {
    int t, n, q;
    string str;
    cin >> t;
    while (t--) {
      Trie trie = init_Trie();
      cin >> n >> q;
      for (int i = 0; i < n; i++) {
            cin >> str;
            add(str.c_str(), trie);
      }
      for (int i = 0; i < q; i++) {
            cin >> str;
            dfs(str.c_str(), 0, strlen(str.c_str()), trie);
      }
      free_Trie(trie);
    }
    return 0;
}


同时，可以推荐一些调试技巧来帮助你寻找RE的原因：

1. 在本地使用调试器，例如GDB或LLDB，可以在程序崩溃时捕获Core Dump并分析其堆栈跟踪。这可以帮助你更好地了解程序何时崩溃，以及在哪个函数中发生了错误。

2. 手动添加调试输出语句，例如打印变量值、循环计数器等，以便更好地了解程序的执行流程和问题出现的位置。

3. 尝试使用在线调试工具，例如IDEOne或CodeSandbox，可以模拟在线评测平台的环境，并提供更多的调试选项和错误消息。
如果问题已经解决，请设置最佳答案

额外减小 发表于 2023-9-30 20:55:59

本帖最后由 额外减小 于 2023-9-30 23:26 编辑

isdkz 发表于 2023-9-30 20:55
这道题目的问题在于在添加字符串时没有对最后一个节点的 down_cnt 进行更新。在 dfs 的过程中，如果遇到了 ...

好好好

额外减小 发表于 2023-9-30 20:58:06

@元豪 @zhangjinxuan @Mike_python小 @Ewan-Ahiouy @sfqxx

Ewan-Ahiouy 发表于 2023-9-30 21:11:29

没有学过{:10_245:}

陶远航 发表于 2023-9-30 22:05:52

isdkz 发表于 2023-9-30 20:55
这道题目的问题在于在添加字符串时没有对最后一个节点的 down_cnt 进行更新。在 dfs 的过程中，如果遇到了 ...

代码？

isdkz 发表于 2023-9-30 22:07:27

陶远航 发表于 2023-9-30 22:05
代码？

可能是超过token限制了{:10_257:}
页: [1]
查看完整版本: 关于字典树的题目，奇怪的是：