Trie 树 基础练习

求收藏 QwQ...

如果发现本题单有任何不妥或有未收录的 Trie 树 好题,可以私信。

动态更新

有一些其他 OJ 的题会在之后我的个人题库中出现,数据由本人手造,便于大家评测。 如果感觉这些题目有点问题(太卡常或数据出错等)可以私信我,会尽快处理。

\text{Trie}

Trie,即字典树,是一个非常强大的数据结构,可以高效处理字符串、异或最大值以及数集维护问题。而且常数非常小。

下面的题基本上是用 Trie 就可以完成的,难度还有待细分。

\texttt{Level I}

比较板子,作为入手 Trie 树的基础。

\texttt{Level II}

接下来是 01Trie ,即每个结点只有 0,1 两个儿子的 Trie 树。比较经典的是贪心计算最大异或值。

不好意思有些题在其他 OJ 上,部分题目以及可以在洛谷上评测, 点击题目即可

\texttt{Level III}

带一些技巧的 Trie 树 应用。会有一定的难度。

\texttt{Level IV}

接下来就要牵扯到 可持久化 Trie 树 了,虽说听起来高大上,但其实没有那么难。当然,最重要的也是最难的还是灵活运用。


  1. P2580 - 于是他错误的点名开始了
  2. SP4033 - PHONELST - Phone List
  3. P4551 - 最长异或路径
  4. P3879 - [TJOI2010] 阅读理解
  5. P2292 - [HNOI2004] L 语言
  6. P3294 - [SCOI2016] 背单词
  7. P5768 - [CQOI2016] 路由表
  8. P2922 - [USACO08DEC] Secret Message G
  9. P2536 - [AHOI2005] 病毒检测
  10. P3065 - [USACO12DEC] First! G
  11. P3732 - [HAOI2017] 供给侧改革
  12. P4407 - [JSOI2009] 电子字典
  13. CF817E - Choosing The Commander
  14. P4735 - 最大异或和
  15. P4592 - [TJOI2018] 异或
  16. P5283 - [十二省联考 2019] 异或粽子
  17. P4098 - [HEOI2013] ALO
  18. P6088 - [JSOI2015] 字符串树
  19. P3369 - 【模板】普通平衡树
  20. P6136 - 【模板】普通平衡树(数据加强版)
  21. P3835 - 【模板】可持久化平衡树
  22. P4683 - [IOI 2008] Type Printer
  23. P5460 - [BJOI2016] IP地址
  24. P5312 - [Ynoi2011] 竞赛实验班
  25. CF888G - Xor-MST
  26. AT_agc044_c - [AGC044C] Strange Dance