欧拉函数求质数 #include<iostream> using namespace std; typedef long long ll; const int N = 1e6 + 10; int euler, primes, cnt; bool st; void get_eulers(int n){ euler = 1; for(int i = 2; i <

一、最小生成树什么？ 1.1 定义 最小生成树： 一个有n个结点的连通图的生成树是原图的最小连通图，且包含原图的所有n个结点，并且保持图的连通的最少的边。 最小生成树可以用：Prim算法和kruskal算法求出 1.2 应用 铺设电缆： 以尽可能低的总价去铺设城市之间的电缆（假设每两个城市可以连通） 旅行家： 某人自驾游想花费最短的路程去旅行到自己所想去的城市（城市有n个 n > 2） 连接

一、最短路是什么？ 最短路径： 从某个点A（位置）到另一个点B(位置)的最短距离，实现方法：点A途中可以经过很多个点C，然后通过不断更新点A到途中点 C 的最短距离，最后实现最短距离到达 点B。 A -> C1 -> C2 -> C3 -> B 最短路径的分类： 单源最短路：图中的一个点到其余各点的最短路径 多源最短路：图中每两个点的最短路径 框架图解：（如果看不清的话，放

一、邻接表与邻接矩阵 1.1 稠密图与稀疏图 图的储存方式分两种：邻接表和邻接矩阵。 了解邻接矩阵和邻接表之前我们要先学会稠密图、稀疏图。 百度百科来说：稠密图、稀疏图。 稀疏图：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph）。 稠密图：有很多条边或弧 (边的条数|E|接近|V|²) 的图称为稠密图（dense graph）。 简单来说：我们假设某个图的点

一、BFS是什么 先用百度百科的来讲： BFS（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。 简单来说，BFS是一种图搜索的算法

一、DFS是什么？ DFS（深度优先搜索算法）：一种用于遍历或者树或者图的算法，是一种递归程序，不断递归达到无法在到达的点，简单点来说：一条路一直走，走到没有路后就原路返回，重新选择另一条 dfs(step + 1)。 DFS = 暴搜 + 回溯算法 + 剪枝（大多数是这样）。DFS需要回溯算法，其他算法也需要回溯算法，两种是一种调用关系。 暴搜：一条路走到黑（直接递归走到底） 回溯：DFS 开启

一、KMP是什么 KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在文本中查找模式。它的核心思想是利用已经匹配的信息来避免重复匹配，从而提高效率。 二、暴力字符串匹配 暴时间复杂度O（n * m） //大概是这样的，可能有差别，但是模板基本上是这样 for (int i = 0; i < m;) { int j = 0; while (i < m &a

一、Trie树是什么？ Trie树又称字典树或前缀树，是一种能够快速查找一组字符串含有一个字符串的类似哈希表的树结构，是以空间换时间，利用字符串的前缀来降低查询时间。 与二叉树不同，Trie树有26子节点对应26个字母，根节点不包含字符串，从根节点到某个节点，经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后，尾节点会用cnt数组来说明该字符串的次数。 二、怎么建立Trie树

一、堆的定义： 堆是什么，堆就像是一个金字塔，最顶端的是最值（最大值和最小值），堆其实就是一个二叉树，将最值元素放到根节点。子节点要么都小于父节点，要么都大于父节点。但是写手堆的话，我们用的是数组来存储，所以堆通常也被看做一颗树的数组对象。 二、堆的分类及性质 2.1 堆的分类： 大根堆和小根堆，根节点最大的堆叫大根堆，根节点最小的堆叫小根堆。 2.2 STL的定义： 首先要调用堆的头文件: #i

一、哈希表是什么？ 哈希表（Hash table 又叫散列表）是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。通常，我们把这个关键字称为Key值，对应的值称为Value值。关键值和Value值是一种一一对应的关系（也就是映射关系），这个映射表，也叫做哈希函数，存放记录的数组就是哈希表。哈希表也类似于离散化。 哈希表的作用：哈希表的作用就是能够通过Key值快速获取Key对应的Valu