题号 NC50349
名称 The XOR-longest Path
来源 信息学奥赛一本通
戳我进入往期每日一题汇总贴~
往期每日一题二期题单
如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468
题解
关于trie树的简单介绍:
trie树又叫前缀树,字典树,他用一个树型结构来表示一个字符串集合。树中的每一条边上都有一个字符,从根节点到某一个位置经过的边就是一个字符串,注意因为有的串是另外的串的子串,所以我们可以用一个字符集里没有的字母(比如$)作为字符串结束的标志。这样拥有同样前缀的字符串在树上就会走相同的路径,在储存上节约了空间,在查找目标串时也提高了效率(只需要顺着trie树走下来就好)。
例子:
aab aaaa cba abc caab aa
六个字符串在trie树上表示,如图:
特别的,当我们的字符集只有01两种元素的时候,我们可以构造一棵二叉树,0的分支在左边,1的分支在右边,这就是01trie树。它常被用来处理这样一个经典问题:给你若干个数,选出其中两个数使得他们异或之后最小/最大。(这里以最小为例)
我们遍历数组中的元素,对于每个元素在他前面找和他异或起来最小的值,显然,要最小肯定是这两个数要从最高位开始尽量一致,我们把它之前的数都按照二进制串的样子加入到01trie里面(所有数的位数统一成一致,不够的补零)。然后根据当前这个数对应的01串在trie上从根向下走,如果当前数这一位是0,在trie树上我们更希望走0的那一边,有0就往0那边走,没有0就只能走1了。
如图:
————————————我是基本知识介绍完毕的分割线—————————————
本题题解
作者:。。。201910131627798
原博客链接:https://blog.nowcoder.net/n/e09c16c6b0a14c2ba959aa740b98bbf0
分析
在一颗树上寻找一条异或值最大的简单路径。先考虑到异或有如下性质 。所以异或两个相同的值时等同于没有异或。所以,树上的简单路径的异或值其实可以看做
。
表示节点
到根的异或和。因为
的值计算了两次,相当于是抵消了。那么题目转化为,在一个序列上找两个节点使他们的异或值最大。显然这个过程需要优化。我们可以考虑
。我们按位由大到小建树。这一类的
有个非常好的性质。在父亲节点就可以知道数的大小关系。这个性质还是比较显然,因为我们是按位由高到低考虑的,那么这一位是
的数,一定大于这一位是
的数。有了这样优美的性质,
就可以维护一些关于值域的题了。所以直接贪心作就好了。时间复杂度为
。
关于01字典树
01 Trie
这个应该是 最常见的形态了。一般的
有按位考虑从高到低的,也有从低到高的。使用方法和处理的问题都有较大的区别。
按位从高到低建树
这一类的 有个非常好的性质。
- 在父亲节点就可以知道数的大小关系。
这个性质还是比较显然,因为我们是按位由高到低考虑的,那么这一位是 的数,一定大于这一位是
的数。有了这样优美的性质,
就可以维护一些关于值域的题了。
一个数字是否出现过
不要跟我说什么 。就考虑用
来考虑这个问题。我们从空节点
开始,按位转移。如果结束节点是被标记过了的,那么表示出现过,则否。时间复杂度为
。其实这个从低到高的建的
也可以维护,但是放在这里显得更自然。
维护整个序列的第 k 小
这个问题解决有非常多的解决方案,这里也不详细展开了。用 来考虑,记录每个节点可以到达的结束节点的个数,记录为
。那么这个
树的用法和权值线段树的用法基本也就一模一样了。考虑走左边还是走右边,
与
分类讨论就行了,比起权值线段树可以免去离散化的过程,但空间开销要大一点了。
可持久化改造
既然 有,类似权值线段树的功能。那么如果可以把
可以持久化,或者用树套一下。权值线段树可以解决的
也可以解决。
考虑什么时候会新建节点,这个只有在插入的时候才会新建节点。那么也只需要,在这个时候再复制节点就可以了。
异或极值
这里讨论最大值。一个数和一个序列中一个数的异或最大值是多少?要支持询问和修改。
朴素的单次处理需要
的复杂度,和
的修改。还是考虑平摊一下时间复杂度。
考虑把序列插入,构建一个
树。那么在询问时,只需要讨论该数的位是
还是
就行了。这样就需要
的预处理,
的询问和修改。
按位从到高位建树
这个按位从低到高的建树,也有一个很棒的性质,非常好维护异或和。
每一个节点保存该 树的异或和。那么在父亲信息合并时。就可以很自然的写出这样的代码,要记住
的最后一层其实是没有信息的,所以要把位数限制开高一点。
序列权值+1
今年的省选就考了这样一道题。 除开合并儿子信息,那么需要维护一下序列权值
的操作。按
的奇妙做法,只需要
,其实这个还是比较好理解的。对于每个数的操作,我们都是要从低到高找到第一个不为
的位置。然后把这一位改成
,后面的全部改为
。那么只需要这样递归处理就行了。
Trie 合并
由上一道题延伸出来的知识点,其实适用于所有 树。操作方法也比较简单,类似于线段树合并。
代码
#include<bits/stdc++.h> using namespace std; const int M = 1000011,N = 1e5 + 10; int read(){ int x;scanf("%d",&x);return x; } vector<int> G[N],W[N]; int n,dis[N],ch[M][2],size,val[M]; void Dfs(int x,int fa){ for(int i = 0;i < G[x].size();i++) { int y = G[x][i]; if(y == fa) continue; dis[y] = dis[x] ^ W[x][i]; Dfs(y,x); } } void Insert(int x) { int u = 0; for(int i = 30;i >= 0;i--) { int v = (x>>i)&1; if(!ch[u][v]){ ch[u][v] = ++size; } u = ch[u][v]; } val[u] = x; } int AskXor(int x) { int u = 0; for(int i = 30;i >= 0;i--) { int v = (x>>i)&1; if(ch[u][v^1]) u = ch[u][v^1]; else u = ch[u][v]; } return val[u]; } int main() { n = read(); for(int i = 1;i < n;i++) { int a = read(),b = read(),c = read(); G[a].push_back(b);W[a].push_back(c); G[b].push_back(a);W[b].push_back(c); } Dfs(1,0); int Ans = 0; for(int i = 1;i < n;i++) Insert(dis[i]); for(int i = 1;i <= n;i++) Ans = max(Ans,dis[i] ^ AskXor(dis[i])); printf("%d\n",Ans); }
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!
活动奖励:
在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)
本道题目9月24日中午12:00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
(14) 回帖