51Nod 1601 完全图的最小生成树计数

By NodeKey in ACM on

分治+字典树+MST 综合好题 标题即题意，但是不一样的是边权是点权的异或。 不可能会出什么边权也是给定的完全图最小生成树计数的啦，现在看来，也算是套路题了。 当然点数不能太多………… 不卡常才是一个好题的前提条件。写 Trie 习惯性用了类，虽然慢了一些，但也不至于太慢。 题意： 给你 n 个点的点权，边权为其异或值，要你求出最小生成树，以及最小生成树的个数。 思路： 这道题的核心思想还是分治。 我们对给定区间的点权进行处理，并假设这个区间的前面 k – 1 位全部相同。那么对于第 k 位，我们根据 01 将其划分为两个集合，这时候两个集合的前 k 位分别相同，再对这两个集合分别进行同样的处理。 其正确性不言而喻。 在处理的过程中，我们需要将两个集合之间建边，因为是MST，所以要找最小的边。将其中一个集合插入 字典树，再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值，再更新答案与边数。 最小生成树的个数只要根据乘法原理将边的数量相乘即可。…

Trie入门与模板

By NodeKey in ACM on

简介 Trie ，又称前缀树或者是字典树，不仅在字符串的应用广泛，在数据结构中也有很多相应的题目，是数据结构中用空间兑换时间的典型。 下面是两个入门题 HDU 1251 统计难题 题意： 给定多个字符串，多个询问，问你以所询问字符串为前缀的字符串数量。 思路： 构造Trie，插入的时候打个顺便再对前缀计数即可。 AC Code #include #include #include using namespace std; const int N = 1000005; int ch[N][30], val[N], sz; void insert(char *s) { int u = 0, len = strlen(s); for (int i = 0;…