The XOR Largest Pair
奶牛异或
Vitya and Strange Lesson
Perfect Security
Xor-MST
最大异或和

题解

10月26-10月30日更新以上题目题解~

NC50993 The XOR Largest Pair
01trie模板题，主要给还不会写01trie的同学学习：
（在之前每日一题出现过的）
关于trie树的简单介绍：
trie树又叫前缀树，字典树，他用一个树型结构来表示一个字符串集合。树中的每一条边上都有一个字符，从根节点到某一个位置经过的边就是一个字符串，注意因为有的串是另外的串的子串，所以我们可以用一个字符集里没有的字母（比如$)作为字符串结束的标志。这样拥有同样前缀的字符串在树上就会走相同的路径，在储存上节约了空间，在查找目标串时也提高了效率（只需要顺着trie树走下来就好）。
例子：
aab aaaa cba abc caab aa
六个字符串在trie树上表示，如图：

特别的，当我们的字符集只有01两种元素的时候，我们可以构造一棵二叉树，0的分支在左边，1的分支在右边，这就是01trie树。它常被用来处理这样一个经典问题：给你若干个数，选出其中两个数使得他们异或之后最小/最大。（这里以最小为例）
我们遍历数组中的元素，对于每个元素在他前面找和他异或起来最小的值，显然，要最小肯定是这两个数要从最高位开始尽量一致，我们把它之前的数都按照二进制串的样子加入到01trie里面（所有数的位数统一成一致，不够的补零）。然后根据当前这个数对应的01串在trie上从根向下走，如果当前数这一位是0，在trie树上我们更希望走0的那一边，有0就往0那边走，没有0就只能走1了。

那么对于本题求最大，只是想走的方向反过来而已——这一位是1则尽量往0走，是0则尽量往1走即可。

——————————————我是下一个题的分割线————————————
NC22998 奶牛异或
对于区间的问题，我们希望转化成和两个端点相关的问题去做——区间[l,r]的异或和等于前r个数的异或和和前l-1个数的异或和异或，所以，我们只需要在前缀异或和数组里面任选两个数让他们异或和最大即可，于是就和前一个题一样了。

——————————————我又是一个萌萌哒的分割线————————————
NC 112209 Vitya and Strange Lesson
每次操作我们可以认为是原数异或上之前所有操作的异或和（这样trie树不会发生变化）。
于是我们每次要做的是在01trie中找到一个和当前的x（也就是本次和之前操作的异或和）异或值最小且不存在于树上的树——如果x的当前位是1，我们这一层往下也倾向于往1走，此时判断1的子树是否满了，如果满了就不能走了只能往0走，如果没满就往1走使得当前位异或的结果为0；当前位为0也类似的思考，一直找下去就行了。

——————————————啦啦啦啦，分割线又来了————————————
NC112567 Perfect Security
因为要字典序最小，显然就可以从前往后，先让第一个数最小，然后让第二个数在选了第一之后最小……
于是我们要做的操作是：将待选的每一个数加入到01trie中，然后找出和当前数异或和最小的数，并把它删掉。
于是就需要对trie树做删除操作——对于每个节点，都记录一下经过了几次他，删除的时候先减少次数，当减到0次的时候就把这个节点删掉即可。

——————————————完结倒计时————————————
NC 112412 Xor-MST
考虑最小生成树的kruskal算法——我们每次需要找到最小的两条边连着的点将他们合并到一棵树上，那么最短的边在哪里呢？
如果我们把所有的点的点权都加入到01trie树上，那么权值最小的边的两个端点他们的在01trie上的LCA一定是最深的（LCA之前的每一位异或之后都成了0，但是注意LCA深度一样的几对节点的异或值还是有大有小的）。所有直观的，我们需要遍历整个trie树，在所有的最深的LCA对应的边中，找到一条最小的边，对两个点进行合并，然后再找再合并——但是这样复杂度太高。
我们再仔细观察这个01trie树，看到可能作为最小边的lca的这些点（即有两个儿子的深度最深的点），不可能出现两个不同的lca有共同的儿子，也就是说，如果我们只把这一层lca对应的点都连起来，那么即使不按照从小到大顺序连也没有关系，因为根本不会出现环。于是lca在最深一层的时候就可以不用排序了。
同理，当最深一层处理完了，再去看一层的lca的时候，也是一样的道理——每个lca对应的两个集合是没有重复的，于是他们之间不需要排序，我们只需要对每个lca对应的两个集合选最小的边做合并即可。（过了lca之后分叉然后在各自的子树中尽量往一个方向走。）
这样就在trie树中从下到上枚举可能作为lca的点然后合并即可。
这样的话写起来都还有一点麻烦，其实你会发现，因为不同子树里面的点是不一样的，所以我们完全可以在trie树上后序遍历每个点，当他可能作为某些点的lca的时候，合并他左右的两个子树对应的集合。
（其实是用了最小生成树的Boruvka算法思想，但是不知道他也能用上述方式分析出来）

——————————————最后一个题————————————
NC 51120 最大异或和
可持久化trie树的板子题，之前9月17日的每日一题已经用过这个板子了，大家也可以复习一下这个题。
首先，既然是求区间异或和，肯定要用前缀异或和转化到区间端点上，添加新数很简单，查询是在查什么东西？
对应一个num=x xor sum[n]，在找[l-1,r-1]里面的一个前缀和让他们的异或和最大。
如果没有区间限制就直接01trie就好了，现在有了区间限制，就需要用可持久化01trie——查询的时候只查对应版本的树就可以了。

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

11月6日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴