当前位置：首页 > news >正文

【数据结构】01Trie

news 来源：原创 2025/8/10 10:37:57

什么是 01Trie?

01Trie是字典树的一种变种，其只有两种情况，即 0 和 1，实现方式其实和字典树是一样的

有什么用呢？

其一般用于解决异或问题，是一种快速的数据结构，某些情况下可以无脑套用

实现方式？

和上面说的一样，其实就是字典树，我们利用实战来讲解一下

实战运用！

P10471 最大异或对 The XOR Largest Pair - 洛谷

思路：

板子

由于要让我们选择两个数使得异或和最大，如果我们直接双重循环的话指定会爆，那我们就需要优化了，而这时就可以请出我们的01Trie了，倒不如说这就是为它而生的

对于01Trie我们必备的两个操作就是插入和查询，我们先讲解插入

我们定义 ch[][] 数组为整个01Trie的大小，由于每个数都有31位，且每位都有01两种可能，所以数组大小就是 ch[N*31][2]，同时我们再定义一个 idx，其代表当前已经有了多少个节点，其中 ch[p][j]代表的是节点 p 到 j 是否存在一条边，且这条边的另一个点是谁，这样我们就能每次跳到下一个节点了，如果不存在我们就只需要把它变成新的节点即可

那么对于每次插入操作，我们都从高到低插入（之后会说为什么），然后判断是否存在这条边，如果存在那就跳到下一个节点，否则就赋予新的节点再跳

查询操作也很好写了，我们和上面插入操作类似，只不过这次我们要主动跳跃了，我们判断 x 的当前位是什么，如果是 0，那我们就判断此点与 1 是否有边，如果有那就跳，否则就跳 0，如果是 1 也是同理，那为什么要从最高位开始呢？因为如果对于 0 最高位有 1 的话，那我们跳到 1 即可，因为此后即使全是 1 也不可能比此时选 1 大，如 1000 0111

那么按照上面思路写完就结束了

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlconst int N = 100010;
int n, a[N];
int ch[N * 31][2], idx = 0;void insert(int x)
{int p = 0;for (int i = 30; i >= 0; i--){int j = x >> i & 1;if (!ch[p][j]){ch[p][j] = ++idx;}p = ch[p][j];}
}int query(int x)
{int p = 0, res = 0;for (int i = 30; i >= 0; i--){int j = x >> i & 1;if (ch[p][!j]){res += 1 << i;p = ch[p][!j];}else{p = ch[p][j];}}return res;
}void solve()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];insert(a[i]);}int ans = 0;for (int i = 0; i < n; i++){ans = max(ans, query(a[i]));}cout << ans;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P4551 最长异或路径 - 洛谷

思路：

思维题

这题乍一看根本不知道怎么和01Trie扯上关系，但是我们要仔细分析一下

对于这棵树，我们随便以一点为根，这里以 1 为根，那么我们可以计算出每个点 x 到 1 的异或和val(1，x)是多少，一次 dfs 即可，那么知道这个有什么用呢？

对于 u v 两个点，如果我们要计算 u ~ v 的异或和，由于异或有交换律，所以我们不需要考虑顺序，那么 val(u，v) = val(1，u) ^ val(1，v)，为什么呢？显然我们可以以 v 为一个中转站，然后链接 u v，如果其中有重复的路，由于 x ^ x = 0，所以重复的位置不会对答案造成影响，因此是可以这样的

所以题目就可以这样做：先 dfs 跑一边把 a[i] 求出来，然后将所有的 a[i] 加到 01Trie 中，然后跑一遍模板即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
const int N = 100010;
int n;
int ch[N * 31][2],idx = 0;
vector<vector<pair<int, int>>> g(N);
vector<int> a(N);void insert(int x)
{int p = 0;for (int i = 30; i >= 0; i--){int j = x >> i & 1;if (!ch[p][j]){ch[p][j] = ++idx;}p = ch[p][j];}
}int query(int x)
{int p = 0,res = 0;for (int i = 30; i >= 0; i--){int j = x >> i & 1;if (ch[p][!j]){res += 1LL << i;p = ch[p][!j];}else{p = ch[p][j];}}return res;
}void dfs(int self,int fa)
{for (auto son : g[self]){if (son.first == fa){continue;}a[son.first] = a[self] ^ son.second;dfs(son.first, self);}
}void solve()
{cin >> n;for (int i = 0; i < n - 1; i++){int u, v, x;cin >> u >> v >> x;g[u].push_back({ v,x });g[v].push_back({ u,x });}dfs(1, 1);for (int i = 1; i <= n; i++){insert(a[i]);}int ans = 0;for (int i = 1; i <= n; i++){ans = max(ans, query(a[i]));}cout << ans;
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

【数据结构】01Trie

什么是 01Trie? 01Trie是字典树的一种变种，其只有两种情况，即 0 和 1，实现方式其实和字典树是一样的有什么用呢？ 其一般用于解决异或问题，是一种快速的数据结构，某些情况下可以无脑套用实现方式&#…...

编程日记 2025/8/10 10:37:57

使用 CDN 在国内加载本地 PDF 文件并处理批注：PDF.js 5.x 实战指南

PDF.js 是一个强大的开源 JavaScript 库，用于在 Web 浏览器中渲染 PDF 文件。它由 Mozilla 开发，能够将 PDF 文档绘制到 HTML5 Canvas 或 SVG 上，无需任何本机代码或浏览器插件。对于许多需要在网页中展示 PDF 内容的应用场景来说&#xff0c…...

编程日记 2025/8/10 10:30:20

SpringBoot指定项目层日志记录

1、新建一个Springboot项目，添加Lombok依赖（注意：这里使用的Lombok下的Slf4j快速日志记录方式） <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId></dependenc…...

编程日记 2025/8/10 10:26:59

使用Mathematica内置函数绘制Sierpinski地毯

除了SierpinskiCurve之外，Mathematica还内置了SierpinskiMesh这个函数，用来绘制地毯。 SierpinskiMesh[n] gives a mesh region representing the n-step Sierpiński triangle. SierpinskiMesh[n,d] gives the n-step Sierpiński sponge in dimension…...

编程日记 2025/8/10 10:35:28

CMake笔记（简易教程）

CMake笔记概述（需要提前了解的知识） 一个c/c程序从代码到生成二进制文件，需要经历的几个关键步骤：预编译（预处理）、编译、汇编、连接【编译链接的几个步骤】编译器：目前市面常见的编译器有…...

编程日记 2025/8/10 10:32:32

现代健康养生新范式：多维度守护身心活力

在快节奏的现代生活中，健康养生是维持高品质生活的关键。从环境调节到生活习惯养成，多个维度的协同发力，才能为健康注入持久动力。良好的生活环境是健康的基础。室内空气流通至关重要，每天开窗通风 2-3 次，每次 30…...

编程日记 2025/8/10 9:33:51

推测式思维树：让大模型快速完成复杂推理

论文标题 Accelerating Large Language Model Reasoning via Speculative Search 论文地址 https://www.arxiv.org/pdf/2505.02865 作者背景中科大，华为诺亚方舟实验室，天津大学 ICML 2025接收动机之前介绍过多篇投机解码（推测式解…...

编程日记 2025/8/10 10:35:29

软考错题（三）

telnet协议是一种基于TCP的远程登录协议占用辅助空间最多的是归并排序直接插入，堆排，简单选择，冒泡的空间复杂度是O(1) 快排是O(logn) 归并是O(n) B树的叶子节点通过指针链接为有序表，不是b-树 python中切片语法[start,end,s…...

编程日记 2025/8/6 22:32:24

注解的定义

一、理论说明 1. 注解的定义 Java 注解是从 JDK 5.0 开始引入的一种元数据机制，它可以为代码添加额外的信息，这些信息不影响程序的运行逻辑，但可以在编译期、类加载期或运行期被读取和处理。注解本质上是一种特殊的接口，所有注解…...

编程日记 2025/8/10 10:32:31

企业微信自建消息推送应用

企业微信自建应用来推送消息前言最近有个给特定部门推送消息的需求，所以配置一个应用专门用来推送消息。实现过程大致为：服务器生成每天的报告，通过调用API来发送消息。以前一直都是发邮件，整个邮箱里全是报告文件&#xff0c…...

编程日记 2025/8/5 20:20:39

swagger3融入springboot

标签： 放controller上面 Api(description "xxx") 放方法上面 Operation(summary "xxx") 引入： 我用的是swagger3.X 需要在yml配置文件中加上： spring:mvc:pathmatch:matching-strategy: ant_path_matcher 然后生…...

编程日记 2025/8/10 10:35:10

CH32V208GBU6沁恒绑定配对获取静态地址

从事嵌入式单片机的工作算是符合我个人兴趣爱好的,当面对一个新的芯片我即想把芯片尽快搞懂完成项目赚钱,也想着能够把自己遇到的坑和注意事项记录下来,即方便自己后面查阅也可以分享给大家,这是一种冲动,但是这个或许并不是原厂希望的,尽管这样有可能会牺牲一些时间也有哪天原…...

编程日记 2025/8/5 20:20:35

[计算机科学#11]:编程语言简史，从二进制到简约表达的华丽转身，造就原因——“懒”

【核知坊】：释放青春想象，码动全新视野。我们希望使用精简的信息传达知识的骨架，启发创造者开启创造之路！！！ 内容摘要： 由于早期的编程需要直接操作硬件，例如使…...

编程日记 2025/8/5 20:20:33

Kubernetes HPA 深度解析：生产环境自动扩缩容实战指南

一、HPA 核心原理剖析 1. 运作机制三步曲 (图示：指标采集 → 决策计算 → 执行扩缩容的完整闭环) 指标采集层：通过 Metrics Server/Prometheus 等组件实时收集 CPU、内存或自定义指标决策计算层：根据当前指标值与目标阈值的比例计算所需副本…...

编程日记 2025/8/10 10:29:38

Matlab 四分之一车体被动和模糊控制对比

1、内容简介 Matlab215-四分之一车体被动和模糊控制对比可以交流、咨询、答疑 2、内容说明略 3、仿真分析略 4、参考论文略...

编程日记 2025/8/5 20:20:29

pm2如何执行脚本批量启动多个服务

在 PM2 中批量启动多个服务，可以通过以下几种高效方式实现，具体操作如下： 方法1：使用 ecosystem.config.js 配置文件（推荐） 步骤1：生成配置文件在项目根目录运行以下命令，生成模板…...

编程日记 2025/8/10 10:26:58

Debian系统详解

以下是关于 Debian 操作系统的超详细深度解析，涵盖历史、架构、功能特性、管理细节及应用场景等方面，帮助你全面掌握这一经典 Linux 发行版： 一、Debian 概述：开源社区的基石 1. 历史与定位 • 诞生：1993 年由 Ian…...

编程日记 2025/8/10 10:29:41

Dify X 奇墨科技，让AI大模型从“巨头专属”变为“触手可及”

AI大模型和AI Agent蓬勃发展，企业比拼的已不仅是AI技术储备，更是AI应用落地的实战能力。奇墨科技正式成为 AI 应用开发平台Dify中国大陆区企业版合作伙伴，帮助企业更便捷地接触到Dify并使用其开发AI应用。 Dify 是一款简单易用的 LLM 应用开…...

编程日记 2025/8/10 10:29:41

CSS相对定位与绝对定位

在网页设计里，相对定位（Relative Positioning）和绝对定位（Absolute Positioning）是 CSS（层叠样式表）里控制元素位置的关键手段。下面为你详细讲解它们的概念、特点与应用场景。相对定位概念…...

编程日记 2025/8/10 10:27:00

正则表达式（Regular Expression）详解

正则表达式（简称"regex"或"regexp"）是一种强大的文本模式匹配工具，它使用特定语法来描述、匹配和操作字符串。基本概念正则表达式是由普通字符（如字母a到z）和特殊字符（称为"元…...

编程日记 2025/8/10 9:21:26

OpenCV-Python (官方)中文教程(部分一)_Day22

22.3 2D直方图在前面的部分我们介绍了如何绘制一维直方图,之所以称为一维,是因为我们只考虑了图像的一个特征：灰度值。但是在 2D 直方图中我们就要考虑两个图像特征。对于彩色图像的直方图通常情况下我们需要考虑每个的颜色（Hue）和饱和度&…...

编程日记 2025/8/10 10:26:00

【软考-高级】【信息系统项目管理师】【论文基础】采购管理过程输入输出及工具技术的使用方法

采购管理概念项目采购管理包括从项目团队外部采购或获取所需产品、服务或成果的各个过程。项目采购管理包括编制和管理协议所需的管理和控制过程，例如合同、订购单、协议备忘录（MOA）和服务水平协议（SLA）。采购管理…...

编程日记 2025/8/5 9:31:59

基于STM32、HAL库的CP2102-GMR USB转UART收发器驱动程序设计

一、简介： CP2102-GMR是Silicon Labs公司生产的一款USB转UART桥接芯片，主要特点包括：集成USB 2.0全速功能控制器内置USB收发器，无需外部电阻工作电压：3.0V至3.6V 支持的数据格式：数据位8，停止位1，无校验最高支持1Mbps的波特率内置512字节接收缓冲区和512字节发送…...

编程日记 2025/8/5 9:31:57

信息系统项目管理工程师备考计算类真题讲解十四

一、最小生成树问题此问题采用破圈法来解决， 1）以1节点为例，找到路径最小点：1--5：距离为3 2）找1--5最短的节点，选择4：1--5--4：距离为：5 3）找…...

编程日记 2025/8/10 10:26:00

二叉树的基本操作

二叉树的基本操作（C 语言版） 1 二叉树的定义二叉树的图长这样：二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储…...

编程日记 2025/8/5 9:31:53

网络基础入门第6-7集（抓包技术）

前言： 来自小迪安全v2023 内容： 第六集： 大致内容：burpsuit、茶杯、fiddler的抓包流程 1、安装抓包软件的相关证书 2、各大抓包软件的测试注意用burp抓模拟器的数据包，需要将ip地址设置为本地的ip地址&#xff…...

编程日记 2025/8/5 9:31:51

自定义Widget开发：自定义布局实现

自定义Widget开发：自定义布局实现一、Flutter布局系统基础 1. 布局约束（Constraints） 在Flutter中，布局系统基于约束（Constraints）的概念。每个widget都会接收来自其父widget的约束，并根据这…...

编程日记 2025/8/6 6:24:36

MyBatis(进阶）（xml标签）

本节⽬标 1. 学习MyBatis的动态SQL查询 2. 掌握MyBatis在项⽬中的应⽤, 可以使⽤Spring MVC完成⼀些基础的功能 1. 动态SQL（XML） 动态 SQL 是Mybatis的强⼤特性之⼀，能够完成不同条件下不同的 sql 拼接可以参考官⽅⽂档： M…...

编程日记 2025/8/4 11:38:19

英皇娱乐X乐华娱乐携手造星！“英皇乐华青少年艺人培训班”正式启动！

2025年5月8日，英皇娱乐集团与乐华娱乐集团联合宣布，双方将在北京市燕京实验中学合作开设“英皇乐华青少年艺人培训班”，为8至18岁的青少年提供专业的演艺及才艺学习平台。此次合作旨在集合两大娱乐公司在演艺行业的资源与优势，共同…...

编程日记 2025/8/4 11:38:17

Linux云计算训练营笔记day04（Rocky Linux中的命令）

mv 移动(剪切) 源数据会消失格式: mv 源文件目标路径 touch /opt/a.txt 创建文件 mv /opt/a.txt /root 移动文件，没有改名 mkdir gongli 创建目录 mv gongli /opt/ 移动目录，没有改名 mv /opt/gongli tedu 移动目录，改名了 …...

编程日记 2025/8/8 0:38:34

枚举 · 例13-【模板】双指针

登录—专业IT笔试面试备考平台_牛客网代码区： #include<algorithm> #include<iostream> #include<vector> #include<unordered_set> using namespace std;struct INTER{int left,right; }; bool compare(const INTER&a,const INTER&a…...

编程日记 2025/8/10 0:44:54

Linux网络编程day7 线程池and UDP

线程池 typedef struct{void*(*function)(void*); //函数指针，回调函数void*arg; //上面函数的参数 }threadpool_task_t; //各子线程任务的结构体/*描述线程池相关信息*/struct threadpool_t{pthread_mutex_t lock; …...

编程日记 2025/8/6 12:46:48

WHAT - ahooks vs swr 请求

文章目录 ahooks特点常用 Hooks 示例1. useRequest — 封装网络请求逻辑（比 SWR / React Query 更轻量）2. useDebounce — 防抖值3. useLocalStorageState — 本地存储的状态4. useBoolean — 快速管理布尔状态5. useEventListener — 添加事件监听 ahoo…...

编程日记 2025/8/4 11:38:09

算法训练营第十一天|150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值题目思路与解法第一思路： 比较简单 class Solution:def evalRPN(self, tokens: List[str]) -> int:stack []for item in tokens:if item ! and item ! - and item ! * and item ! / :stack.append(item)else:b int(stack.pop())a …...

编程日记 2025/8/8 6:28:30

可视化图解算法35：在二叉树中找到两个节点的最近公共祖先（二叉树的最近公共祖先）

1. 题目描述给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。数据范围：树上节点数满足 1≤n≤105 , 节点值val满足区间 [0,n) 要求：时间复杂度 O(n) 注：本题保…...

编程日记 2025/8/6 22:29:41

如果说开启的TIM3定时器有ccr1,ccr2,ccr3,我想要关闭ccr2的PWM输出，怎么通过代码实现

目录作用概述： 具体原理： 代码的操作细节： 实际效果： 示意全文： 小结： TIM3->CCER & ~TIM_CCER_CC2E; 作用概述： 作用是禁用 TIM3 的通道 2（CCR2）的捕获…...

编程日记 2025/8/4 11:38:02

高能数造全固态电池干法电极高品质原纤化技术：驱动干法和全固态电池制造新进程

技术背景传统湿法电极制备工艺的局限:传统的湿法电极制备工艺需要使用大量的溶剂来溶解粘结剂和分散活性物质，后续还需要复杂的干燥工序来去除溶剂。这不仅增加了生产成本和能源消耗，溶剂的使用和处理还会带来环境污染和安全隐患。新能源产业发展的需…...

编程日记 2025/8/4 11:38:01

AI驱动的制造工艺：系统化探索与创新

DeepSeek 技术全景在当今 AI 技术蓬勃发展的时代，DeepSeek 已成为该领域中一颗耀眼的明星。自 2023 年 7 月 17 日成立以来，这家由知名私募巨头幻方量化孕育而生的公司，迅速在 AI 领域崭露头角。DeepSeek 的目标是开发顶尖的大语言模型（LLM），并利用数据蒸馏技术打造更精…...

编程日记 2025/8/8 6:41:45

Mac 平台获取地区标识符号

以下是添加了详细中文注释的代码版本，解释每一行代码的作用： #include <CoreFoundation/CoreFoundation.h> #include <vector> #include <string> #include <iostream>// 将 Core Foundation 的字符串(CFStringRef)转换为标准 …...

编程日记 2025/8/4 11:37:55

PyTorch 实战：从 0 开始搭建 Transformer

导入必要的库 python import math import torch import torch.nn as nn from LabmL_helpers.module import Module from labml_n.utils import clone_module_List from typing import Optional, List from torch.utils.data import DataLoader, TensorDataset from torch imp…...

编程日记 2025/8/4 11:37:53

Java 显式锁与 Condition 的使用详解

Java 显式锁与 Condition 的使用详解在多线程编程中，线程间的协作与同步是核心问题。Java 提供了多种机制来实现线程同步，除了传统的 synchronized 关键字外，ReentrantLock 和 Condition 是更灵活且功能强大的替代方案。本文将详细介绍显式…...

编程日记 2025/8/4 11:37:51

【MySQL】存储引擎 - CSV详解

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/8/4 11:37:49

LeetCode算法题(Go语言实现)_62

题目有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 7 取模的值。平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不…...

编程日记 2025/8/4 11:37:47

矿井设备通信破局：ModbusTCP转DeviceNet网关应用实践

矿井设备通信破局：ModbusTCP转DeviceNet网关应用实践在500米深的金属矿井中，传统人工操控采掘设备存在高风险、低效率问题。某矿业集团引入海希无线遥控器远程控制掘进机，却因通信协议冲突陷入困局：海希遥控器采用DeviceNet协议…...

编程日记 2025/8/4 11:37:45

GrassRoot备份项目

Windows服务项目 Grass.cs using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Net.Http.Headers; using System.Net.Http; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Time…...

编程日记 2025/8/5 21:42:01