算法刷题:最大异或对(Trie树扩展)、食物链(并查集扩展)

2023-12-30 07:28

本文主要是介绍算法刷题:最大异或对(Trie树扩展)、食物链(并查集扩展),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 引言
  • 一、最大异或对(Trie树扩展)
    • 1.题目描述
    • 2.解题思路
    • 3.代码实现
    • 4.测试
  • 二、食物链(并查集扩展)
    • 1.题目描述
    • 2.解题思路
    • 3.代码实现
    • 4.测试

引言

这两个扩展题能够让我们更加的熟悉Trie树和并查集的使用,这两道题可以说是比较难的了,所以说还是好好对待吧。

一、最大异或对(Trie树扩展)

1.题目描述

在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1~AN。输出格式
输出一个整数表示答案。数据范围
1≤N≤105,0≤Ai<231输入样例:
3
1 2 3输出样例:
3

2.解题思路

  • 首先最开始当然是用暴力做一下,如下所示,很明显是O(n^2)的一个时间复杂度,然后这个数据是10 ^ 5,那就是执行10 ^ 10次,然后一般C++的时间范围在10 ^ 9内一般都是可以过的,这个当然就TLE了。
int res = 0;
for (int i = 0; i < n; ++i)
{for (int j = 0; j < i; ++j){res = max(res, a[i] ^ a[j]);}
}
  • 然后就想怎么优化了,我们注意第二层循环是查找当然数中与a[i]异或的最大值,我们发现数据是小于 2 ^ 31 - 1的,也就是最多31位,那么是最大的,肯定先从最高位找有没有一个数跟a[i]的最高位不一样,如果有那就把他们集合到一块,没有那就挑相同的,然后找第29位有没有与a[i]第29位不同位的树,如果没有那就找相同的,然后就这样找到第0位,肯定就是与a[i]异或最大的数了,这也是一种贪心的思想,具体图解看如下的例子:
    如果右边是已经有的Trie树了,我们要找与110异或最大的,那么最高位是1,我们就要找0,然后有0,然后看下一位是1,我们就要找0,没有0,那就只能是1了,然后下一位是0,我们要找1,那就找到了,所以最终与110异或最大的数是011
    在这里插入图片描述

3.代码实现

#include <cstdio>
#include <iostream>using namespace std;const int N = 1e5+10, M = 31 * N;  // 最大有M个结点int a[N];
int son[M][2], idx;  // M个结点,每个结点两个儿子0,1
int n;void insert(int x)
{int p = 0;for(int i = 30; i >= 0; --i){int u = x >> i & 1;if(!son[p][u]) son[p][u] = ++idx;p = son[p][u];}
}int query(int x)
{int p = 0, res = 0;for(int i = 30; i >= 0; --i){int u = x >> i & 1;if(son[p][!u])  // 找不同的{res = res * 2 + !u;p = son[p][!u];}else  // 如果不存在,那只能退而求其次{res = res * 2 + u;p = son[p][u];}}return res;
}int main()
{scanf("%d", &n);for(int i = 0; i < n; ++i) scanf("%d", &a[i]);int res = 0;for(int i = 0; i < n; ++i){insert(a[i]);int t = query(a[i]);  //查询与a[i]异或最大的数res = max(res, a[i] ^ t);}printf("%d\n", res);return 0;
}

4.测试

在这里插入图片描述

在这里插入图片描述

二、食物链(并查集扩展)

1.题目描述

动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B 吃 C,C 吃 A。现有 N 个动物,以 1∼N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述:
第一种说法是 1 X Y,表示 X 和 Y 是同类。
第二种说法是 2 X Y,表示 X 吃 Y。此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
当前的话与前面的某些真的话冲突,就是假话;
当前的话中 X 或 Y 比 N 大,就是假话;
当前的话表示 X 吃 X,就是假话。你的任务是根据给定的 N 和 K 句话,输出假话的总数。输入格式
第一行是两个整数 N 和 K,以一个空格分隔。
以下 K 行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中 D 表示说法的种类。
若 D=1,则表示 X 和 Y 是同类。
若 D=2,则表示 X 吃 Y。输出格式
只有一个整数,表示假话的数目。数据范围
1≤N≤50000 ,0≤K≤100000输入样例:
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5输出样例:
3

2.解题思路

这道题是要输出谎话的次数,然后x,y > n,就不说了很好判断,然后其实就是判断是不是同类,是不是能吃的关系
思路就是如下图的关系,是不是同类取决于到根结点的距离是否相同,吃与被吃的关系却决于到根结点的距离,当然这些距离都要 mod 3

3.代码实现

关于最后 d[px] 的推导我画了张图,虽然很丑,但是关系描述的还是很清晰的,然后注释写的也比较详细,不懂得可以多看看
在这里插入图片描述

在这里插入图片描述

#include <cstdio>
#include <iostream>using namespace std;const int N = 5e5+10;int p[N], d[N];  // d[i]是i号结点到根结点的距离
int n, m;int find(int x)
{if(x != p[x]) {int t = find(p[x]);d[x] += d[p[x]];  // 必须先执行find操作,将d[p[x]是真正的到根结点的距离,而不是到上一个结点的距离p[x] = t;  // 路径压缩}return p[x];
}int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i) p[i] = i;int res = 0;while(m--){int t, x, y;scanf("%d%d%d", &t, &x, &y);int px = find(x), py = find(y);if(x > n || y > n) res++;else{if(t == 1)  // 同类{if(px == py && (d[x] - d[y]) % 3) res++;  //如果是一个集合的,并且到根结点的距离不同,说明不是一个类的else if(px != py)  // 刚开始还没插进集合里{p[px] = py;  // 让x的根结点的父亲为y的根结点d[px] = d[y] - d[x];  // 只用将x根结点到y根结点的距离一改,之后的话,会通过上面的find函数自动修改的}}else  // x吃y{int link = 1;  // 这里给出2也是可以的,x比y多1或者2 都表示x吃yif(px == py && (d[x] - d[y] - link) % 3) res++;else if(px != py){p[px] = py;d[px] = d[y] - d[x] + link;}}}}printf("%d\n", res);return 0;
}

4.测试

在这里插入图片描述

这篇关于算法刷题:最大异或对(Trie树扩展)、食物链(并查集扩展)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/552117

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系