Posts tagged with Trie


分治+字典树+MST 综合好题 标题即题意,但是不一样的是边权是点权的异或。 不可能会出什么边权也是给定的完全图最小生成树计数的啦,现在看来,也算是套路题了。 当然点数不能太多………… 不卡常才是一个好题的前提条件。写 Trie 习惯性用了类,虽然慢了一些,但也不至于太慢。 题意: 给你 n 个点的点权,边权为其异或值,要你求出最小生成树,以及最小生成树的个数。 思路: 这道题的核心思想还是分治。…

简介 Trie ,又称前缀树或者是字典树,不仅在字符串的应用广泛,在数据结构中也有很多相应的题目,是数据结构中用空间兑换时间的典型。 下面是两个入门题 HDU 1251 统计难题 题意: 给定多个字符串,多个询问,问你以所询问字符串为前缀的字符串数量。 思路: 构造Trie,插入的时候打个顺便再对前缀计数即可。 AC Code #include <cstdio> #include <…