高精度 存储方式： 整数的长度一般小于1e6 大整数的每一位存储到数组里 存储时低位在前，高位在后，方便进位 高精度加法 每一位相加Ai+Bi+t,t表示进位取值0/1，逢十进一 模板：//存储方式 stringa,b;//a="123456" vector<int>A,B;//A=[6,5,4,3,2,1] for(inti=a.size()1;i>=0;i)A.push_back(a[i]'0'); for(inti=b.size()1;i>=0;i)B.push_back(b[i]'0'); //加法 vector<int>add(vect...

双指针 两个指针指向两个不同的序列 两个指针指向同一个序列（归并排序，快速排序） 主要作用：将暴力O(n^2)遍历通过两个指针的某种单调性质优化到O(n)，也就是说将内层循环变量j通过与外层循环变量i的关系，将内层循环次数降低不定次 模板：for(inti=1;i<n;i){ while(j<i&&check(i,j))j; //内部逻辑具体分析 } //例如将一个字符串中的单词按行输出 str="acvadfwers"; intlen=strlen(str); //双指针算法 for(inti=0;i<len;i){ intj=i; while...

链表 用数组模拟，不同于结构体加指针 调用new关键字开上万级别的节点非常慢，基本会超时 单链表 来构造邻接表 用于存图与树 基本结构： head表示头结点的下标 e[i]表示节点i的值 ne[i]表示节点i的下一个节点的下标 idx存储当前已经用到了哪个节点，表示新节点 基本操作： 向链表头插入一个节点 在节点k后面插入一个节点 删除节点k后面的一个节点 模板：inthead;//头指针，指向头结点 inte[N];//e[i]表示节点i的值 intne[N],//en[i]表示节点i的下一个节点 intidx;//存储新节点的下标 //初始化 voidinit(){ hea...

哈希表 作用：将庞大的空间，映射到小的空间，集中数据，一般用取模，取模的数尽量取质数，最大程度减小冲突 操作：一般是添加和查找元素，删除元素通常有一个标记数组，对元素标记为已删除 离散化相似，离散化是特殊的哈希方式，离散化处理的数据是单调的，相对位置不变 映射会出现冲突，如将两个不同的数映射成同一个数 存储结构： 解决了冲突 开放寻址法 仅仅一个数组，数组长度通常为最大范围的23倍 存储：当前位置有元素，就移到下一个位置，直到当前位置无元素为止 查找：当前位置有元素且不为x，就移动到下一个位置，直到当前位置是x，后返回下标 代码：constintN=2e5+3; constintnul...

深度优先搜索 一条路走到黑 回溯/剪枝 每一个dfs都对应一个搜索树 解决全排列，搜索所有可能解 宽度优先搜索 一层一层搜索 解决最短路问题 搜索方式 数据结构 空间 特点 DFS stack O(h) 不具有最短性 BFS queue O(2^h) 最短路 树与图的存储 有向图/树 每条边建一次add(a,b); 存储： 邻接矩阵： 存稠密图，无法存重边，浪费空间 邻接表： 单链表数组，有几个点就开几个单链表，每个单链表存储该点可以到的点 代码：//h[i]存储以节点i为起点的单链表，单链表中的节点存的是节点i能够到达的所有节点 //以节点...

常用STL： vector 变长数组，倍增的思想 初始化： //初始化 vector<int>a; vector<int>a(n); vector<int>a[n]; vector<int>a(n,0);//长度为n，值为0 操作： size()//返回元素个数 empty()//返回是否为空 clear()//清空 front()/back()//返回第一个/最后一个元素 push_back()/pop_back()//在尾端插入元素/删除元素 begin()/end()//迭代器 []//随机访问 遍历： for(inti=0;...

最短路 单源最短路 求从一个点到其他所有点的最短距离 所有边权是正数 朴素Dijkstra算法O(n^2) 用于稠密图m>=n 步骤： dist[i]：每个点离起点的距离 S：已经确定最短距离的点 V：没有确定最短距离的点 初始化所有点的距离dist[起点]=0；dist[其他点]=inf 循环找V中离起点最近的点t 将t放入S中 用t的距离更新其他点的距离 代码：constintN=510; intg[N][N];//稠密图用邻接矩阵 intdist[N];//到原点的距离 intst[N];//标记数组 intdijkstra(){ //初始化距离 memset...

最小生成树 Prim算法 朴素版PrimO(n^2) 稠密图 步骤： S：表示最小生成树的集合 初始化距离 找距离集合S最近的节点 将节点加入集合S 用该节点更新非S点到集合S点的距离 代码：constintN=510; constintINF=0x3f3f3f3f; intg[N][N]; intd[N];//非生成树节点与生成树节点的最短距离 intst[N]; intn,m; intprim(){ memset(d,0x3f,sizeofd);//初始化 intres=0;//记录生成树权值和 for(inti=0;i<n;i){//遍历n次选取n个点加入生成树 ...

数论 质数 在大于1的整数中，只包含1和本身这两个约数，就被称为质数，也叫素数 质数的判定 试除法 遍历2-n，若有约数则不为质数O(n) 优化： d整除n，则n/d也整除n，约数总是成对出现，只要找较小的约数，即取d<=n/d，则d<=sqrt(n)只用遍历2-sqrt(n)O(sqrt(n)) 不用ii<=n，i过大会溢出 sqrt()函数较慢，只用遍历d--n/d，即限制范围为i--n/i 代码：//不用for(inti=1;ii<=n;i)ii会溢出 //不用for(inti=1;i<=sqrt(n);i)sqrt()函数缓慢 //用for(...

欧拉函数 欧拉函数\(\varphi(N)\):1-N中与N互质的数的个数 若\(N=p_1^{a_1}·p_2^{a_2}·p_3^{a_3}····p_n^{a_n}\)其中p为N的所有质因子 则\(\varphi(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})···(1-\frac{1}{p_n})\) 证明： 互质：两数的公共因子只有1 去掉所有与N有(大于1的)公共因子的数，剩下的数就是与N互质的数 对N的所有质因子\(p_k\)，去掉所有\(\underline{质数p_k的倍数}\)(与N有公共因子的数)，\(\underline{每个质数的倍...

高斯消元 求解含有n个未知数，n个方程的多元线性方程组O(n^3) 初等行变换： 某行乘以一个非零数 交换两行 某行加上另一行的若干倍 利用初等行变换将方程组化为上三角矩阵 解的情况： 完美阶梯型：唯一解 非完美阶梯型： 0非0：无解 00：无穷解 步骤: 枚举每一列 找到这一列系数的绝对值最大的一行 将这一行与第一行交换 将改行的第一个数变成一(方程两边同乘某数) 把下面所有行的当前列的系数消成0(某行加上第一行的若干倍) 代码：constintN=110; constdoubleesp=1e-6;//x<esp,则x=0,否则x!=0,由于浮点数精度问题,0可...

容斥原理 \(|A\cupB\cupC|=|A|+|B|+|C|-|A\capB|-|A\capC|-|B\capC|+|A\capB\capC|\) \(|\displaystyle\cup_{i=1}^nA_i|=\sum_{i}|A_i|-\sum_{i,j}|A_i\capA_j|+\ldots+(-1)^{n+1}|\cap_{i=1}^nA_i|\) 时间复杂度：\(C_n^1+C_n^2+C_n^3···+C_n^n=2^n-1\)\(O(2^n-1)\) 等式右边有\(2^n-1\)项，每一项表示选取若干个集合相交的情况，可以通过DFS遍历每种选取的情况，也可以把每种选取的...

背包问题 动态规划思路： 状态表示f(i,j) 状态由几维表示 表示的集合是什么 所有选法 选法条件 只考虑前i个物品 总体积<=j 集合的属性是什么 最大值 最小值 元素的数量 状态计算 集合的划分f(i,j) 不含第i个物品 f(i1,j) 包含第i个物品 f(i1,jvi)已知第i个物品必选，那么只要保证前i-1个物品为最大值 01背包 每件物品最多取一次 朴素代码：constintN=1e3+10; intf[N][N],v[N],w[N]; intn,m; intmain(){ cin>>n>>m; for...