HDU5687字典树WA了求调

Question

rt,

HDU5687 https://acm.hdu.edu.cn/showproblem.php?pid=5687

WA了求调，c++错误代码：

//# pragma GCC optimize("Ofast,no-stack-protector")
//
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

typedef long long ll;

using namespace std;

int q, tr[3000005][30], s[3000005], tot;

bitset <3000005> lazy;

string op, a;

void pushdown (int x) {

    if (! lazy[x])
        return ;

    for (int i = 0; i < 26; ++ i)
        if (tr[x][i])
            s[tr[x][i]] = 0, lazy[tr[x][i]] = 1;

    lazy[x] = 0;

    return ;

}

void add () {

    int now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        if (tr[now][x])
            now = tr[now][x];
        else
            now = tr[now][x] = ++ tot;

        ++ s[now];

    }

    return ;

}

void del () {

    int now = 0, t;

    for (char& i : a) {

        const int x = i - 'a';

        if (s[tr[now][x]])
            now = tr[now][x];
        else
            return ;

        pushdown (now);

    }

    t = s[now], lazy[now] = 1, now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        now = tr[now][x];

        s[now] -= t;

        pushdown (now);

    }

    return ;

}

bool find () {

    int now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        if (s[tr[now][x]])
            now = tr[now][x];
        else
            return 0;

        pushdown (now);

    }

    return s[now];

}

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    cin >> q;

    while (q --) {

        cin >> op >> a;

        if (op[0] == 'i')
            add ();
        else if (op[0] == 'd')
            del ();
        else
            cout << (find () ? "Yes\n" : "No\n");

    }

    I AK IOI

}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

在调试你的代码之前，让我们先了解一下字典树（Trie）的基本概念以及你的代码中可能存在的问题。

字典树是一种用于快速检索字符串集合的数据结构，它允许你快速地插入、删除和查找字符串。在你的代码中，你实现了三个主要操作：插入（add）、删除（del）和查找（find）。让我们逐一检查这些操作，看看可能的问题在哪里。

1. 插入操作（add）：

   • 你的插入操作看起来是正确的，但是要注意，每次插入新字符时，应该检查tr[now][x]是否已经存在，如果不存在，则需要创建新的节点。

2. 删除操作（del）：

   • 删除操作看起来比较复杂，你需要确保在删除之前，路径上的所有节点都存在。此外，你的删除操作似乎没有正确地处理懒标记（lazy propagation）。在删除操作中，你需要确保在删除之前，路径上的懒标记已经被正确地应用。

3. 查找操作（find）：

   • 查找操作看起来是正确的，但是你需要确保在查找之前，路径上的懒标记已经被正确地应用。

4. 懒标记（lazy propagation）：

   • 你的代码中使用了懒标记来优化删除操作。但是，你的懒标记似乎没有正确地传递给子节点。在pushdown函数中，你需要确保将懒标记的值应用到子节点的s数组中，并且将子节点的懒标记设置为0。

5. 边界条件和特殊情况：

   • 确保你的代码能够处理空字符串的情况，以及只有一个字符的字符串。

6. 测试用例：

   • 确保你使用了足够的测试用例来覆盖所有可能的情况，包括但不限于边界条件、大量数据、随机数据等。

7. 代码风格和可读性：

   • 你的代码使用了宏定义和一些不常见的缩写，这可能会降低代码的可读性。考虑使用更清晰的变量名和注释来提高代码的可维护性。

8. 编译器优化：

   • 你的代码中包含了编译器优化的指令，但是这些指令可能不会对调试过程有帮助。在调试阶段，建议关闭优化，以便更容易地跟踪问题。

9. 调试技巧：

   • 使用调试器逐步执行代码，观察变量的值和程序的流程。
   • 打印关键变量的值，特别是在操作前后，以检查它们是否符合预期。

10. 参考链接：

    • 这里没有特定的参考链接，但是你可以查找关于字典树实现和懒标记应用的教程或文章来帮助你理解这些概念。

希望这些建议能帮助你调试代码。如果你需要更具体的帮助，可以提供更多的信息，比如错误发生的具体测试用例或者错误输出与预期输出的对比。