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

NO.81十六届蓝桥杯备战|数据结构-Trie树-字典树-前缀树|于是他错误的点名开始了|最大异或对 The XOR Largest Pair(C++)

news 来源：原创 2025/9/19 18:12:36

字典树的概念
Trie树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。
我们可以把字典树想象成⼀棵多叉树，每⼀条边代表⼀个字符，从根节点到某个节点的路径就代表了⼀个字符串。例如，要存储 “abc” 、 “abd” 、 “acde” 以及 “cd” 时，构建的字典树如下
字典树的作⽤
当我们在字典树的每⼀个结点位置，额外维护⼀些信息时，就可以做到很多事情：

查询某个单词是否出现过，并且出现⼏次；
查询有多少个单词是以某个字符串为前缀；
查询所有以某个前缀开头的单词；（这个作⽤可以⽤到输⼊法中，输⼊拼⾳的时候，可以提⽰可能的单词）
当然，除了上述作⽤以外，字典树还可以解决别的问题，后续可以在做题中体会

字典树的实现
实现⼀个能够查询单词出现次数以及查询有多少个单词是以某个字符串为前缀的字典树，默认全是⼩写字⺟。

准备⼯作：

#include <iostream>  
#include <cstring>  
using namespace std;  
const int N = 1e6 + 10;  //表示所有的字符串中一共有多少个字符
int tree[N][26], p[N], e[N];
int idx;

tree：二维数组，第一维表示字符串中一共有多少个字符，第二维表示字符里的规模，全是小写字母的话就是26
tree[i]：表示i号节点的孩子信息
tree[i][0]：表示‘a’的路径信息
tree[i][1]：表示‘b’的路径信息
tree[i][3]：表示‘c’的路径信息
p[i]：表示i号节点的pass信息
e[i]：表示i号节点的end信息
idx：新来一个字符之后，为它分配位置
![[Pasted image 20250409121839.png]]

插⼊字符串：

void insert(string& s)  
{  int cur = 0; // 从根结点开始  p[cur]++; // 这个格⼦经过⼀次  for(auto ch : s)  {  int path = ch - 'a';  // 如果没有路  if(tree[cur][path] == 0) tree[cur][path] = ++idx;  cur = tree[cur][path];  p[cur]++;  }  e[cur]++;  
}

查询字符串出现的次数

int find(string& s)  
{  int cur = 0;  for(auto ch : s)  {  int path = ch - 'a';  if(tree[cur][path] == 0) return 0;  cur = tree[cur][path];  }  return e[cur];  
}

查询有多少个单词以字符串 s 为前缀

int find_pre(string& s)
{  int cur = 0;  for(auto ch : s)  {  int path = get_num(ch);  if(tree[cur][path] == 0) return 0;  cur = tree[cur][path];  }  return p[cur];  
}

P8306 【模板】字典树 - 洛谷

#include <bits/stdc++.h>
using namespace std;const int N = 3e6 + 10;int n, q;
int tr[N][62], p[N];
int idx;int get_num(char ch)
{if (ch >= 'a' && ch <= 'z') return ch - 'a';else if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 26;else return ch - '0' + 52;
}void insert(string& s)
{int cur = 0;p[cur]++;for (auto ch : s){int path = get_num(ch);if (tr[cur][path] == 0) tr[cur][path] = ++idx;cur = tr[cur][path];p[cur]++;}
}int find_pre(string& s)
{int cur = 0;for (auto ch : s){int path = get_num(ch);if (tr[cur][path] == 0) return 0;cur = tr[cur][path];}return p[cur];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--){//初始化//memset(tr, 0, sizeof tr);//memset(p, 0, sizeof p);for (int i = 0; i <= idx; i++){for (int j = 0; j < 62; j++){tr[i][j] = 0;        }}for (int i = 0; i <= idx; i++) p[i] = 0;idx = 0;cin >> n >> q;        while (n--){string s; cin >> s;insert(s);}while (q--){string s; cin >> s;cout << find_pre(s) << endl;}}return 0;
}

P2580 于是他错误的点名开始了 - 洛谷

⽤字典树维护字符串，当查询之后，将e数组修改成-1即可

#include <bits/stdc++.h>
using namespace std;const int N = 5e5 + 10;int n, m;
int tr[N][26], e[N];
int idx;void insert(string& s)
{int cur = 0;for (auto ch : s){int path = ch - 'a';if (tr[cur][path] == 0) tr[cur][path] = ++idx;cur = tr[cur][path];}e[cur]++;
}int find(string &s)
{int cur = 0;for (auto ch : s){int path = ch - 'a';if (tr[cur][path] == 0) return 0;cur = tr[cur][path];}if (e[cur] > 0){e[cur] = -1;return 1;}return e[cur];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;while (n--){string s; cin >> s;insert(s);}cin >> m;while (m--){string s; cin >> s;int ret = find(s);if (ret == 0) cout << "WRONG" << endl;else if (ret == 1) cout << "OK" << endl;else cout << "REPEAT" << endl;}return 0;
}

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

将所有数按照⼆进制位存在字典树中，针对每⼀个数x ，按照⼆进制匹配最优的⽅案

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int tr[N * 32][2], idx;void insert(int x)
{int cur = 0;for (int i = 31; i >= 0; i--){int path = ((x >> i) & 1);if (tr[cur][path] == 0) tr[cur][path] = ++idx;cur = tr[cur][path];}
}int find(int x)
{int cur = 0;int ret = 0;for (int i = 31; i >= 0; i--){int path = ((x >> i) & 1);//贪心，要去相反的路if (tr[cur][path^1]){ret |= (1 << i);cur = tr[cur][path^1];}else{cur = tr[cur][path];}}return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];insert(a[i]);}int ret = 0;for (int i = 1; i <= n; i++){ret = max(ret, find(a[i]));        }cout << ret << endl;return 0;
}

NO.81十六届蓝桥杯备战|数据结构-Trie树-字典树-前缀树|于是他错误的点名开始了|最大异或对 The XOR Largest Pair(C++)

字典树的概念 Trie树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。我们可以把字典树想象成⼀棵多叉树，每⼀条边代表⼀个…...

编程日记 2025/9/19 18:12:36

go语言应该如何学习

以下是学习Go语言的高效路径及关键技巧，结合多个优质来源整理而成，适合不同基础的学习者： 一、基础语法快速入门（1-2周） 1、环境搭建下载安装Go SDK，配置GOPATH和GOROOT环境变量，推荐使用Go…...

编程日记 2025/9/19 18:09:34

struct结构体、union联合体和枚举

目录一、结构体的声明和使用 1.1 结构体正常声明和创建 1.2 结构体特殊声明 1.3 结构体的自引用二、结构体内存对齐 2.1 对齐规则 2.2 #pragma修改三、结构体传参四、结构体位段 4.1 位段内存分配 4.2 位段内存应用五、结构体中的柔性数组概念六、union联合…...

编程日记 2025/9/18 11:44:05

el-tree 实现树形菜单子级取消选中后父级选中效果不变

背景在复杂的企业级管理系统中，树形菜单是一种常见的数据展示和交互组件。传统的树形菜单通常存在以下交互局限：子节点取消选中时，父节点会自动取消选中无法满足复杂的权限分配和数据筛选场景实际应用场景：组织架构权限管理多层级资源分配复杂的数据筛选与展示实现需求…...

编程日记 2025/9/16 4:33:05

centos7系统搭建nagios监控

~监控节点安装 1. 系统准备 1.1 更新系统并安装依赖 sudo yum install -y httpd php php-cli gcc glibc glibc-common gd gd-devel make net-snmp openssl-devel wget unzip sudo yum install -y epel-release # 安装 EPEL 仓库 sudo yum install -y automake autoconf lib…...

编程日记 2025/9/16 6:06:18

Gitlab的迁移升级

Gitlab11.6.5的迁移升级 Gitlab升级是不能跨大版本升级的，根据官方升级路径来操作。 gitlab迁移首先需要查看当前gitlab版本 cat /opt/gitlab/embedded/service/gitlab-rails/VERSION 当前版本是11.6.5 备份源数据原仓库备份所有的文件 /opt/gitlab/bin/git…...

编程日记 2025/9/17 11:10:36

C++11QT复习（十九）

文章目录 Day13 C 时间库和线程库学习笔记（Chrono 与 Thread）一、时间库 <chrono>1.1 基本概念1.2 使用示例1.3 duration 字面量单位二、线程库 <thread>2.1 基本用法2.2 数据竞争（Race Condition）2.3 加锁&#xff…...

编程日记 2025/9/18 18:39:22

3 版本控制：GitLab、Jenkins 工作流及分支开发模式实践

一、引言在软件开发过程中，版本控制是保障代码质量、提高开发效率的关键环节。有效的版本控制能够帮助团队成员更好地协作，追踪代码变更，快速定位和解决问题。GitLab 和 Jenkins 作为两款广泛使用的工具，在版本控制和持续集成 / 持续部署（CI/CD）流程中发挥着重要作用。本…...

编程日记 2025/9/19 11:52:54

docker配置远程连接，dockerfile-maven-plugin插件打包到远程

我开发机器上的内存不大，能不安装在本地的应用就都跑在服务器上了，但是本地打包时需要用到docker打包成镜像，这时会本地运行docker，所以准备本地只使用docker客户端，连接服务器上的docker服务端服务端配置 docker服…...

编程日记 2025/9/19 14:56:30

Skyline配置指南-微信小程序

Skyline 是微信小程序推出的新一代渲染引擎，提供了更强大的渲染能力和更流畅的性能体验。以下是配置 Skyline 的详细步骤： 一、app.json文件配置 "componentFramework": "glass-easel", "lazyCodeLoading": "requi…...

编程日记 2025/9/18 23:53:30

【c语言】倒置字符串

将一句话的单词进行倒置，符号不变，用例长度不超过100 思路： 逆序整个字符串逆序每个单词 #include <stdio.h> #include <string.h> void reverse(char* left, char* right) {while (left < right) {//char *tmp left;//error…...

编程日记 2025/9/18 3:20:39

MySQL多表查询实战指南：从SQL到XML映射的完整实现（2W+字深度解析）

MySQL多表查询实战指南：从SQL到XML映射的完整实现（2W+字深度解析）第一章多表查询基础与核心原理 1.1 关系型数据库设计范式以电商系统为例的三范式实践： -- 原始数据表（违反第三范式） CREATE TABLE orders (order_id INT PRIMARY KEY,customer_name VARCHAR(50),p…...

编程日记 2025/9/11 0:13:37

【图书管理系统】全栈开发图书管理系统获取图书列表接口（后端：计算图书页数、查询当前页展示的书籍）

图书列表实现服务器代码(计算图书总数量查询当前页需要展示的书籍) 后端响应时，需要响应给前端的数据 records：第 pageNum 页要展示的图书有哪些（存储到List集合中）total：计算一共有多少本书（用于告诉前…...

编程日记 2025/9/10 0:21:21

SpringMvc的请求-获得请求参数

客户端请求参数的格式是: namevalue&namevalue..… 服务器端要获得请求的参数，有时还需要进行数据的封装，SpringMVC可以接收如下类型的参数: 基本类型参数 POJO类型参数数组类型参数集合类型参数获得基本类型参数 Controller中的业务方法…...

编程日记 2025/9/17 19:58:59

CSS 笔记——Flexbox（弹性盒布局）

目录 1. Flex 容器与 Flex 项目 2. 主轴与交叉轴 3. Flex 容器的属性 display flex-direction justify-content align-items align-content flex-wrap 4. Flex 项目的属性 flex-grow flex-shrink flex-basis flex align-self 5. Flexbox 的优点 6. Flexbox 的…...

编程日记 2025/9/19 8:55:18

Redis 缓存 + MySql 持久化实现点赞服务

前言为什么所用 redis 作为缓存来实现点赞服务, 而不是直接就使用 mysql 来完成? 使用 Redis 的集合数据结构来存储点赞用户的 ID，方便快速判断用户是否已点赞; 当用户频繁的点赞和取消点赞时, 无需操作数据库, 减轻服务器压力 Redis 可以承受高并发的读写操作…...

编程日记 2025/9/15 19:00:38

Oracle OCP知识点详解2：yum 等服务的搭建

一、YUM/DNF 服务架构解析 1.1 核心组件交互流程 sequenceDiagram participant Client participant YUM participant Repository participant RPMDBClient->>YUM: yum install oracle-database-preinstall YUM->>Repository: 获取元数据(repodata) Repository--&…...

编程日记 2025/9/15 1:14:18

JavaScript Hook XMLHttpRequest操作：逆向与调试实战指南

在JavaScript逆向工程中，Hook XMLHttpRequest操作是一种重要的技术，可以用来捕获、修改或分析网络请求的发送和接收过程。本文将结合具体案例，详细讲解如何实现XMLHttpRequest的Hook操作。一、Hook XMLHttpRequest的基本原理 （…...

编程日记 2025/9/15 9:42:47

21 天 Python 计划：MySQL视图、触发器、存储过程、函数与流程控制

文章目录一、视图1.1 创建视图1.2 使用视图1.3 修改视图1.4 删除视图二、触发器2.1 创建触发器2.2 使用触发器2.3 删除触发器三、存储过程3.1 介绍3.2 创建简单存储过程（无参）3.3 创建存储过程（有参）3.4 执行存储过程3.5 删除存…...

编程日记 2025/9/19 16:30:57

机器学习 Day10 逻辑回归

1.简介流程就是： 就是我们希望回归后激活函数给出的概率越是1和0. 2.API介绍 sklearn.linear_model.LogisticRegression 是 scikit-learn 库中用于实现逻辑回归算法的类，主要用于二分类或多分类问题。以下是对其重要参数的详细介绍： 2.1.…...

编程日记 2025/9/17 1:59:22

Hadoop的序列化和反序列化

//1 package com.example.sei;import org.apache.hadoop.io.Writable;import java.io.DataInput; import java.io.DataOutput; import java.io.IOException;//学生类，姓名，年龄 //支持hadoop的序列化 //1.要实现Writable接口 //2.补充一个空参构造 publi…...

编程日记 2025/9/18 19:02:08

Altera Cyclone EP1C20F400C8N FPGA 阿尔特拉介绍

在可编程逻辑器件领域，Altera 的 Cyclone 系列 FPGA 以其低成本、低功耗和灵活的 I/O 支持而著称。EP1C20F400C8N 作为 Cyclone I 家族中规模最大的成员之一，提供约 20 060 个逻辑单元，面向通信、工业控制、视频处理等多种嵌入式应用场景。…...

编程日记 2025/9/19 15:14:38

VTK随笔十四：QT与VTK的交互示例（平移）

VTK（Visualization Toolkit）是一个开源的软件系统，用于三维计算机图形学、图像处理和可视化。它提供了丰富的工具和类来处理三维数据和交互。在 VTK 中，拾取操作通常通过 vtkCellPicker 或 vtkPointPicker 等类来实现。本文将展示…...

编程日记 2025/9/17 16:39:01

用户注册（阿里云手机验证码）

阿里云开通三网106短信 ①、在阿里云市场搜索“短信”，开通三网短信，并可以查看其中的请求示例（java PHP^） 并在个人中心的管理控制台中查到，获取其中的AppKey AppCode ②、接口开发 service-user模块中依赖spr…...

编程日记 2025/9/16 0:55:31

【BFT帝国】20250409更新PBFT总结

2411 2411 2411 Zhang G R, Pan F, Mao Y H, et al. Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms[J]. ACM COMPUTING SURVEYS, 2024,56(5).出版时间: MAY 2024 索引时间（可被引用）: 240412 被引:…...

编程日记 2025/9/19 9:21:21

学习海康VisionMaster之边缘交点

一：进一步学习了今天学习下VisionMaster中的边缘交点，这个还是拟合直线的衍生应用，可以同时测量两条直线并且输出交点或者判定是否有交点二：开始学习 1：什么是边缘交点？ 按照传统的算法，必须…...

编程日记 2025/9/9 3:40:14

公司级项目-AD9914扫频源（三）评估板与上位机的初步调试

硬件平台搭建1-评估板与上位机第一阶段，先使用评估板配套的上位机软件进行控制，学习一下各种功能的实现方式和寄存器配置方式。硬件连接需要的设备仪器包括：多路直流稳压电源、信号发生器、示波器、电脑。按照图中的方式进行连接&am…...

编程日记 2025/9/19 12:39:38

技术优化实战解析：Stream重构与STAR法则应用指南

目录一、真实案例背景：老代码的"历史厚重感" 二、屎山代码解剖课：这些写法到底烂在哪？ 三、Stream流式重构：给老代码做个大保健 2.1 重构后代码实现 2.2 核心API技术拆解 2.3 进阶优化技巧三、STAR法则技术文档…...

编程日记 2025/9/16 20:07:35

基于Qt的串口通信工具

程序介绍该程序是一个基于Qt的串口通信工具，专用于ESP8266 WiFi模块的AT指令配置与调试。主要功能包括： 1. 核心功能串口通信：支持串口开关、参数配置（波特率、数据位、停止位、校验位）及数据收发。 AT指令操作&a…...

编程日记 2025/9/14 20:47:37

Xilinx FPGA XCZU5EV‑2FBVB900I Zynq UltraScale+™ MPSoC EV 系列

XCZU5EV‑1FBVB900I XCZU5EV‑2FBVB900E XCZU5EV‑1FBVB900I 是 Xilinx Zynq UltraScale™ MPSoC EV 系列中功能最为丰富的器件之一，采用 16 nm FinFET 工艺，封装为 31 mm  31 mm、900‑ball FCBGA（FBVB900）。该系列在传统的…...

编程日记 2025/9/19 17:23:13

如何更改OCP与metadb集群的连接方式 —— OceanBase运维管理

背景许多用户都会借助OCP平台来进行OceanBase集群的运维与监控，且因为考虑单节点的OCP部署，在遇故障时可能会短时间出现无法管控 OceanBase集群，多数用户倾向于采用多节点方式来部署OCP，即 OCP的 metadb集群也是三节点的集群部署…...

编程日记 2025/9/19 13:42:24

Databricks: Why did your cluster disappear?

You may found that you created a cluster many days ago, and you didnt delete it, but it is disapear. Why did this happen? Who deleted the cluster? Actually, 30 days after a compute is terminated, it is permanently deleted automaticlly. If your workspac…...

编程日记 2025/9/11 12:47:26

准备⼯作：

插⼊字符串：

查询字符串出现的次数

查询有多少个单词以字符串 s 为前缀

相关文章：