浮云世事改, 过月此心明

数据结构初见：Trie树今天，我们来了解一下Trie树这种数据结构，来看看专属于它的数据结构之美，(●ˇ∀ˇ●) Trie树的基本功能​ 在之前我们可能会遇到一种题，比如说，现在我们有m个小写字母字符串，然后，我们有n个询问，对于每一个询问会告诉我们一个字符串，让我们在那m个字符串里面找到一样的，找到的话就输出yes，不然就输出no ​ 一般情况下，我们会用一个二维数组，把所有的字符串保存在二维数组里面，对于每一次询问，我们对数组进行依次遍历，直到找到符合的字符串，但是呢，这么做的话，就会很麻烦，因此，伟大的前辈们研究出来了一种可以很好解决这一类题目的方法，那就是Trie树这么一种数据结构 ​ 那么，Trie树是怎么对于这些字符串数组进行存储的呢？欸，其实也是一个二维数组，只不过存储方式不太一样，假如说，我们现在有一下这些字符串 abcde abd abdc abc bcd ​ 在存储一个字符串之前，我们先设置一个根节点，这个节点的目的就是作为存储的根，可以让我们更加方便地查询。好的，现在我们开始存储第一个字符串吧 我们从根节点开 ...

算法初见：并查集这是一个类似于树的，可以将两个元素合并起来的一种数据结构。 —-作者感觉的，(●ˇ∀ˇ●) 并查集的基本功能今天，我们来看看并查集这么一个数据结构，来介绍一下它的基本功能 并查集的主要作用就是把两个树合并成一个树，但是，如果只是这么说的话，那就太笼统了，别人这么跟我说，我也不知道是什么意思，所以下面我们就来好好聊聊合并成一棵树，首先，我们来画个图，从图里面来了解这么一个数据结构 两棵树，生成！ 子树1 子树2 3 5 2 4 1 1 5 3 8 1 3 6 注意，这两棵树可以不是二叉树，比如子树2就不是二叉树 现在，我们来看看这两棵树的共同点，比如说，每一棵树都有自己的根节点，子树1的根节点是3，子树2的根节点是5，每一个根节点都会生成任意数的子节点(只要不是负数)，每一个子节点都会生成任意数的自己的子节 ...

寒假刷题计划计划范围 从12.17号开始，大约56天，每天去洛谷oj/acwing上找大概3 - 5道类似的题(题目难度在普及组或者普及/提高组)，每道题争取自己写出来，实在写不出来那只能就看大佬题解了嘤嘤嘤 注意算法的涉及：算法的涉及只是说可以用这种算法思路，不代表题目一定考这个 下面是题库 刷题题库12.17(排序算法)1.P5414 [YNOI2019]排序 P5414 [YNOI2019] 排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 涉及算法: 冒泡排序法，线性dp 2.P7714 [EZEC-10]排列排序 P7714 「EZEC-10」排列排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 涉及算法：双指针 3.P1908 逆序对 P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 涉及算法：归并排序 4.P1230 智力大冲浪 P1230 智力大冲浪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 涉及算法：贪心 结构体排序 5.P1142 轰炸 P1142 轰炸 - 洛谷 ...

单链表从出生到毕业​ 今天，我们来学习一下链表的基本操作，与其相关联的操作大致有9种，我们一个一个来讲解，来揭开链表的神秘面纱 单链表的操作首先，我们要先定义一个单链表，怎样才可以定义一个单链表呢？ 我们要创建一个结构体，来存储需要的数据还有该数据指向的下一个节点，因为单链表是按照创建malloc动态分配内存给它的,我们也要动态的创建链表 第一步 创建一个链表并初始化​ 我们要创建一个结构体来描绘我们所需要的对象，比如说，我们想描述一个游戏账号，他的id是多少，他在游戏中取得名字叫什么，这些信息需要我们来创建一个链表来依次查询的 //头文件 #include<iostream> #include<algorithm> using namespace std; const int N = 1001; typedef long long ll; //创建一个存储信息的结构体 typedef struct List { //游戏id int id;  ...

字典序排序​ 在这次的文章中将会介绍关于字典序排序的一些内容(包括一道复盘题)，但是在讲述字典序题目前，我们先要知道什么是字典序，字典序是指按照ascii码值来进行排序的序列来形成一个有序的集合。 ​ 有个经典的例子，比如说这样一道题，有1，2，3这三个数，你要把它们所组成的三位数按照从小到大的顺序依次排列，想都不用想就知道可以排列成123，132，213，231，312，321这6种情况，但是放在程序中要怎么写呢，这就是我们要解决的问题，这道题可以用回溯算法，数组和宽度优先搜索来解决，对于每一个数字进行判断是否满足一定的要求，满足的话就放入一个新的序列，这就是字典序排序 两个最简单的函数​ 给我们指定5个数字，例如1 8 9 0 4，要找出这五个树中组成的某个数的上一个字典序对应的数是什么，通俗的说，就是告诉你18940后，你要立刻回答给我18904，这道题可以用一个字典序排序的函数来解决prev_permutation()这个函数就可以立刻对18940这个数进行排序，代码如下 #include<iostream> #include<algorit ...

acm与寒训任务主线任务 争取在大三下以前可以打到icpc/ccpc的银牌及以上水平，如果可以打到wf的话就更好了(嘻嘻)(●’◡’●) 支线任务 1.蓝桥杯 2.天梯赛 3.robocom 4.pat 5.csp/ccf认证 寒假学习目标​ 首先，将一些基础模板背熟(参考yxc巨佬的模板，同时将模板改成自己的风格)，在写题的时候如果遇到了熟悉的模板一定要自己打出来，不要去看，这点很重要，基础模板一定要背牢，背牢，背牢 基础模板 1.基础算法 快速排序，归并排序，二分，高精度，前缀和与差分，双指针，位运算，离散化，区间合并 2.数据结构 单链表，双链表，栈与单调栈，队列与单调队列，KMP，Trie树，并查集，堆，哈希表 3.搜索与图论 树与图的遍历，拓扑排序，dijkstra，bellman_ford，spfa，floyd，prim，kruskal，染色法判定二分图，匈牙利算法 4.数学知识 质数与合数，欧拉函数，快速幂，扩展欧几里得算法，中国剩余定理，高斯消元，求组合数，容斥原理，博弈论 5.基础dp 背包问题，线性dp，区间dp，记数类dp，数位统计dp，状态压缩dp ...

质数和合数在这个内容中，我们将学习质数和合数的内容，有部分内容是我们小学的时候就已经学习过了，还有部分的知识就涉及到数论的内容中了 质数在学习质数之前，我们要先知道一下质数的定义，什么样的数才算是一个质数？ ​ 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数） —来源于百度百科 判断质数​ 知道质数的定义后，我们就要知道如何才能够求解出一个数是不是质数，判断一个数是不是质数，那就看从2开始到小于它一位的数是否都不能将它整除 这样来看，这个程序还是很好写的 代码如下 bool isprime(int m) { if(m<2) return false; for(int i = 2;i<m-1;i++) { if(m%i==0) return false; } return true; } ​ 这样的代码在求一个数是否是质数的时候是非 ...

vector容器今天，我们来讲解一下c++中的vector容器，它封装了动态大小数组的顺序容器，就相当于它能够存放各种类型的对象。可以简单的认为，vector是一个能够存放任意类型的动态数组 vector容器的特性为了更好叙述下面的内容，我在这里先新建一个vector容器 生成一个vector容器容器名 <容器存储对象的类型> 储存对象的名字 vector<int> tp; 顺序序列vector容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素 对vector容器的第6位元素的值进行修改(类似于数组的修改) tp[5] = 10; 动态数组支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作 对vector容器的尾部进行插入操作 tp.push_back(); 对vector容器的尾部进行删除操作 tp.pop_back(); 能够感知内存分配器容器使用一个内存分配器对象来动态地处理它的存储需求 vector容器的使用我们在知道vector容器的基本用法后，我们 ...

Floyd最短路算法(初版)今天，我们来讲讲在最短路中的第三种算法，floyd算法, 实际上这是第五个基础算法， dijstkra算法有朴素算法形式的，也有堆优化版的，它有两种形式 在处理负权边的时候有boolman_ford算法和优化版的spfa算法 所以这实际上是第五种了((^_^)) 算法来源在计算机科学中，Floyd算法是一种在具有正或负边缘权重（但没有负周期）的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。 虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。 该算法的版本也可用于查找关系R的传递闭包，或（与Schulze投票系统相关）在加权图中所有顶点对之间的最宽路径。 <来源于百度百科> floyd算法主要是来处理最短路问题中的多个点之间的距离，在需要使用这种算法的题目上会出现多次询问,让你求a点到b点的最短距离，包括负权边和闭环 下面以一道题目为例，来说明这个算法在处理实际题目上的应用 例题:Floyd求最短路给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定 k ...