排序地方
一、排序快速排序给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1 ≤ n ≤ 100000
输入样例：
1253 1 2 4 5
输出样例：
11 2 3 4 5
解答
12345678910111213141516171819202122232425262728293031323334353637#include <iostream>using namespace std;const int N = 100010;int q[N];void quick_sort(int q[], int l, int r){ if (l >= r) return ; int i = l - 1, j = r + 1, x = q[l + r >> 1]; whil ...
Cpacket类 （协议包封装）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112#pragma once#include "pch.h"#include "framework.h"#pragma pack(push)#pragma pack(1)class CPacket{public: CPacket():sHead(0), nLength(0), sCmd(0), sSum(0) {} // 打包 CPacket(WORD nCmd, const BYTE* pData, size_t nSize) &# ...
这部分内容有下面几块12341、 数论2、 组合计数3、 高斯消元4、 简单博弈论
一、数论1、质数1、判断质数质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
说明
12345·试除法·判断条件的选择 i < n和i <= n / 2时间复杂度都是O(n), 过高 i * i <= n虽然时间复杂度是O(n^½ ), 但i * i可能会溢出 因此最好的判别条件是i <= n / i，时间复杂度是O(n^½ )
2、分解质因数1234567891011void divide(int x){ for (int i = 2; i <= x / i; i ++ ) // 注意循环条件 if (x % i == 0) { int cnt = 0; while (x % i == 0) x /= i, cnt ++ ; cout < ...
———————————————————–还没整理好——————————————————————————–
图论有哪些部分？123456789101、 深度优先搜索 DFS2、 宽度优先搜索 BFS3、 树与图的存储4、 树与图的深度优先遍历5、 树与图的宽途优先遍历6、 拓扑排序7、 单源最短路径8、 多源最短路径9、 最小生成树10、二分图
DFS 和 BFS
数据结构
空间
特点
DFS
stack
O(h)
不具有最短性
BFS
queue
O(2^h)
最短路径
DFS例题给定一个整数 n ，将数字 1 ∼ n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式共一行，包含一个整数 n。
输出格式按字典序输出所有排列方案，每个方案占一行。
数据范围1 ≤ n ≤ 7
输入样例：13
输出样例：1234561 2 31 3 22 1 32 3 13 1 23 2 1
12345678910111213141516171819202122232425262728293031323334353637#in ...
s
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364vector：变长数组， 倍增的思想 size() empty() clear() front()/back() push_back()/pop_back() begin() / end() [] 支持比较运算 pair<int, int> first 第一个元素 second 第二个元素 支持比较运算，以 first 为第一关键字， 以 second 为第二关键字() string：字符串，substr()，c_str() size() empty() clear() queue, 队列, push(),front(), pop() push() 队尾插入一个元素 front() 返回头元素 back() 返回队尾元素 pop() 弹出队头元素 priority_queue, 优先队列, 默认是大根堆 push() 插 ...
哈希表1、 存储结构
把一个有非常大值域的 x 直接取模，由于数值很多，取完模之后可能发生冲突，所有有了下面两种处理冲突的方法。
1️⃣开放寻址法
2️⃣ 拉链法
2、字符串哈希方式
例题维护一个集合，支持如下几种操作：
I x，插入一个整数 x；
Q x，询问整数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1 ≤ N ≤ 10^5−10^9 ≤ x ≤ 10^9
输入样例：
1234565I 1I 2I 3Q 2Q 5
输出样例：
12YesNo
开放寻址法
一维数组的长度要开到题目的两到三倍，冲突概率很低。
12345678910111213141516171819202122232425262728293031323334353637383940414243#inc ...
如何手写一个堆？1、 插入一个数
12heap[ ++ size] = x;up[size];
2、 求集合中的最小值
1heap[1]
3、 删除最小值
123heap[1] = heap[size];size -- ;down(1);
4、 删除任意一个元素
1234heap[k] = heap[size];size -- ;down(k);up(k);
5、 修改任意一个元素
123heap[k] = x;down(k);up(k);
堆是一个完全二叉树
小根堆：根节点就是最小值， 每个点都满足小于左右两个点
存储：使用一维数组来存储， 一号点是根节点，x的左儿子 2x， 右儿子 是 2x + 1
堆的两种操作
1、 down 2、 up
例题1输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1 ≤ m ≤ n ≤ 10^51 ≤ 数列中元素 ≤ 10^9
输入样例：
125 3 ...
并查集1、 将两个集合合并。
2、 询问两个元素是否在一个集合当中。
基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，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， 这样就完成合并了。
合并集合一共有 nn 个数，编号是 1∼n1∼n，最开始每个数各自在一个集合中。
现在要进行 mm 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集 ...
