竞赛讨论区 > 【每日一题】9月17日题目精讲
头像
王清楚
编辑于 2020-09-17 17:33
+ 关注

【每日一题】9月17日题目精讲

题号 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之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

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

全部评论

(14) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐