CygneNoir

![[Pasted image 20240213110207.png]] ![[Pasted image 20240213115501.png]] 最短路问题一般分为 1. 单源最短路：一般来说是求一个点到其他所有点的最短距离（一个起点到....） 例子：一号点到 N 号点的最短路径（求出来一号点到其他所有点的最短路之后，显然一号点到 N 号点的最短路就求出来了） 可以分成两大类： 1. 第一类是所有边权都是正数 1. 朴素 Dijkstra 算法 O (n^2) n 指点数 m 表示边数：基于贪心 最好稠密图用（边特别多） 2. 堆优化版 Dijkstra 算法 O (mlogn) 稀疏图

//特指整数的离散化 有序的离散化 假设a[] 1 3 100 2000 500000 0 1 2 3 4 // 映射的过程就叫离散化 // 1.a[]中可能有重复的元素 所以需要去重 // 2.如何算出x离散化后的值 // 即x的值在a中的下标是多少 （这一步是有序的，所以可以用二分来找） 3.离散化 vector<int> alls;/&#x

n 的二进制表示第 k 位是几 1. 先把第 k 位移到最后一位 n >> k 2. 看个位是几 x & 1 1.2. 结合一下 n >> & 1 看一下 n 的二进制第 k 位是几 lowbit (x) 返回 x 的最后一位 x = 1010 lowbit (x) = 10 x = 101000 lowbit(x) = 1000 x & -x = x & (~x + 1) x = 1010...100...0 ~x= 0101...011...1 最

/* vector 变长数组 数组长度可以动态变化 基本思想是倍增思想 size() 返回元素个数 empty() 返回是否为空 clear() 清空 front() 返回vector的第一个数 back() 返回vector的最后一个数 push_back() 向vector最后插入一个数 pop_back() 把vector最后一个数删掉 vector也是有迭代器的： begin() vector的第0个数 end() vector的最后一个数后面一个数 vector支持随机寻址 跟数组一样

数据结构 空间 (俗称暴搜) 即某一道题目的所有方案全部遍历一遍(比较方便) 1.深度优先搜索 DFS stack O(n) 不具有最短路性质 重点: 到底是用什么样的顺序来遍历这个方案 两个重要概念： 1) 回溯 2) 剪枝 凡是算法思路比较奇怪的 一般都用DFS来做 或者是对空间要求比较高的 2.宽度优先搜索 BFS queue O(2^n) 最短路 所以凡是最小步数 最短

#include <iostream> using namespace std; int main(){ double x; cin >> x; double l = 0, r = x; while(r - l > 1e-8){ //这里有精度问题所以整大点 1e-8 double mid = (l + r) / 2; if(mid * mid >= x) r &#x

// x = 1010 // 原码 0...01010 // 反码 1...10101 // 补码 1...10110 ~x + 1 //为甚么补码即负数这么奇怪 因为计算机底层实现是没有减法的 只能用加法抽象一层再做减法 //负数的性质：x + (-x) = 0 // -x = 0 - x // 32个0 - x

//1.看一下题目当中的哪儿些操作可以进行优化 操作有什么特点 //2.寻找一堆数里的最小值 或者最大值的时候用堆来做 //3.当想维护一个有序链表的时候就要用平衡树就是set来做 //4.当想维护区间最大值、区间和可能就要用树状数组或者线段树来做 //5.并查集的题目可能不是很好看出来 不是很直观 所以需要多练题 哈希表 1.存储结构 输入 h(x) 输出 (0, 10^5) //支持两种操作 1.插入一个数x 数的范围是（-10^9,10^9） 2.询问数x在集合中是

Trie:高效地存储和查找字符串集合的数据结构 并查集: 1、将两个集合合并 2、询问两个元素是否在一个集合当中 并查集可以在近乎O(1)的时间内完成这两个操作 基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点 问题1：如何判断树根:if(p[x] == x) 问题2：如何求x的集合编号:while(p[x] != x) x = p[x]; 问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y 优化：路径压缩、安置优化（不常用 不讲） 这里的堆是

#include <iostream> #include <string.h> using namespace std; int main(){ char str[1000]; fgets(str, 100, stdin); int n = strlen(str); for(int i = 0; i < n; i++){ int j = i; while(j < n && str[j] !&#x