堆优化，主要用于m~n数量级较近，换句话说m~n2数量级较远 时间复杂度o(mlogn)，相当于遍历了每条边，如果插入用logn 伪代码 优先队列--小根堆<距离，点号> q 起点入队，最小起点距离dist[起点]=0，st[起点]记录 while(非空){     目前最小点top=堆顶     出队     点var=top的点号， distance=top的距离     if&nbsp...

dijkstra伪代码     记录位置dist[i]=++++     dist[1]=0;     for(int i:1~n){o（n）         t=不在st中且距离1最近的点 o（n）         st中记录下t      &...

#include <iostream> #include <algorithm> using namespace std; long long f[21][4]; int t,n,m; void prework() {     f[0][0]=1;     for(int i=0;i<20;i++)     {    &n...

[当前位数][之前每一位的和][当前余数][当前位数字是否与原数相同] 打表 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 10; int f[N*N][N][N*N][N*N],power[10]; int n=9,m=81, num[10]; int ask(int x) {     int res = 0, d = 0;     for(int t=x; ...

😎vector 可增长数组 插n个数，申请o(logN)，copy平均o（1）； 申请三法：     vector<int> a;     vector<int> b(3);//建3个空间     vector<int> c(3,4);//建3个空间，每个是4 遍历三法：     for(int i=0;i<a.size();...

字符串哈希主要判断两段子串是否相等； 时间复杂度：它的效率除读入的N以外，操作时计算时间复杂度为O(1)； 除KMP算法可以解决求循环节（字符串哈希不能解决）以外，字符串哈希在字符串问题中完爆KMP 思路：每次读入一个字母求出目前的hash值：，然后每次要求l到r就hash【r】-hash【l-1】*Pr-(l-1)； 注意： 1.我们要保证各个串hash值不同，一般P=131或者13331，M=264，我们这里用unsigned long long来巧妙mod264； 2.字符串取值不为0 板子： #include <b...

先建一个槽，用公式计算出每一个数对应的槽t，然后每一个槽下吊链表（所有对应公式答案的数） 注意 ： 增加链表Insert（）函数是插在最上面不是插在最下，这样可以节省修改 板子 #include <bits/stdc++.h> using namespace std; const int N=100005,MOD=100003; int h[N],e[N],ne[N],idx=1,n,x;//h是槽，e，ne，idx是链表模板  char op[4]; void&n...

一般大根堆和小根堆可以用优先队列，但解决“把第n个插入数修改成x”类似的问题可能要用模拟堆 如果题目是先只修改，最后询问最小，可以先记录插入顺序修改插入顺序，然后输进堆中进行询问 如果询问后有修改第n插入、删除第n插入，就要模拟堆： 模拟堆板子： #include <bits/stdc++.h> using namespace std; int n,k,x; const int N=100009; int ph[N],h[N],hp[N],size=0,m=0;//ph:普通插入位置对应的...

堆排序在STL里就是优先队列priority_queue 这里初始化排序 暴力读一个插入尾部然后up上去，时间复杂度NlogN 先全部读入，在n/2开始用down起到优化时间复杂度2N，如下图 12 3 重要板块： void down(int x){//down函数 int p=x; if((x<<1)<=size&&h[x<<1]<h[p]) p=x<<1;//左儿子是否存在&&左儿子比目前最小的小  if((x<...

在普通并查集加上一个记录点数的size，只有头的size有意义 #include <bits/stdc++.h> using namespace std; const int N=100005; int n,m,a,b; char op[5]; int fa[N],size[N]; int find(int a){ if(fa[a]!=a) fa[a]=find(fa[a]); return fa[a]; } int main(int&nbs...

并查集主要处理：1.集合合并    2.查找两元素是否在同一集合 优雅地合并+压缩路径 int find(int a){//合并+压缩路径 if(fa[a]!=a) fa[a]=find(fa[a]); return fa[a]; } 代码 #include <bits/stdc++.h> using namespace std; int n,m,a,b; char op[5]; const int N=100005; int&nbs...

字典树就是用树的方式记录单词，大幅度提高单词存储和查找的效率 我一开始想每个节点包括1个char和多个指针，然后每次遍历到该点时再遍历它的指针所指的字母， 然后发现下面这个视频里北大硕士的空间换时间妙： https://www.acwing.com/video/260/ 他的做法： 因为只有26个英文字母，所以最多26个指针，且字母是有顺序的只要把下个字母-‘a’就可用o(1)复杂度知道是否存在该字母，字母在地址 设son【先字母地址】【下个字母】存下个字母的地址 板子： #include <bits/stdc++.h> u...

先暴力： for i遍历每一个a【】     for遍历每一个b【】          ifa【】+b【】==x     break 恰因为是a和b是严格单调的且只有一组解（找到一组就break） 所以可以用双指针 i从a左开始，j从b右开始  如果a+b>x，b就前移，这种方法就可以找出所有在小于等于x周边震荡的a+b组合 #include <bits/stdc++....

先暴力： for i遍历s每一点当起点 for j 从i到i+n-1 如果s[  i  ]!=p[ j ] break 但我们可以利用我们已经扫描过的s序列的信息看我们可以跳到p序列什么位置，使得p该位置之前和以扫描末尾段重合 板子如下： #include <bits/stdc++.h> using namespace std; const int N=10005; const int M=100005; char p[N],s[...