| ACM算法模板总结（分类详细版） | 您所在的位置：网站首页 › 直通率算法模板 › ACM算法模板总结（分类详细版） |
|
本文模均引用于y总的算法模板，网址：AcWing (转载请注明出处，本文属于持续更新ing.......biubiubiu......) 本人码风比起y总真的差远了，所以敲一遍后，还是想把y总的搬上来，见笑了qaq...（模板更新的是我经常用到的，如有缺，留评） 目录 基础算法 C++常用便捷技巧 前言.1 lower_bound/upper_bound set map 迭代器的使用 unordered.... bitset String __int128读写模板子 快速排序 归并排序 二分/三分模板 整数二分模板 浮点数二分模板 整数三分模板 浮点数三分模板 高精度加法 高精度减法 高精度乘低精度 高精度除以低精度 位运算模板 子矩阵的和 差分矩阵 双指针算法 数据离散化 保序离散化 非保序离散化 RMQ（ST表查询区间最值） 数学知识 试除法判定质数 试除法分解质因数 朴素筛法求素数（质数） 线性筛法求素数 区间素数筛 Min_25求1~n质数和 试除法求约数（求一个数的所有因子） 约数个数与约数之和 欧几里得算法 求欧拉函数 筛法求欧拉函数 卡特兰数 Catalan数的典型应用： 模板 快速幂 位运算处理大数相乘(1e18) 扩展欧几里得算法 高斯消元 求组合数 递归法求组合数（数据规模小） 通过预处理逆元的方式求组合数（数据规模上万） Lucas定理（数据规模上亿） 分解质因数法求组合数（不取模求真实值） 几何模板 数学公式 图论 有向图的拓扑序 树的直径 最短路算法模板 前言.2 朴素版Dijkstra O(n^2) 堆优化版Dijkstra O(mlogn) spfa算法(带优化) O(km) SPFA判负环正环 floyd算法 O(n^3) 差分约束系统 最长路径算法 最短路径计数 dijkstra拆点最短次短路计数 最小生成树 前言.3 prim算法 kruskal算法 最小生成森林 prim算法修改 次最小生成树 最近公共祖先 前言.4 倍增在线算法 targin离线算法 有向图的强连通分量 无向图的点双连通分量 二分图 前言5 染色法 匈牙利算法（把妹算法） 数据结构 单链表 双链表 单调栈 单调队列 滑动窗口 最大子段和（限制区间长度） 并查集 字符串哈希 KMP——字符串匹配 高级数据结构 线段树 最大连续子段和（单点修改） 区间整体加和乘（区间修改） 树状数组的三个操作 Trie (字符串) DP（模型） 最长上升子序列模型 前沿6 O(N^2) O(NlogN) 最长公共序列模型 最长公共上升序列模型 编辑距离 基础算法 C++常用便捷技巧 前言.1基于平衡二叉树（红黑树）的存储方式，set, map, multiset, multimap，unordered_map, unorder_set 甚至vector等等容器他们都用一些共同的操作 size() empty() clear() begin()/end() lower_bound/upper_bound 这两个二分查找操作可以在set，数组，vector，map中使用； 数组 或者 vector 中的语法： 序列是升序的（从小到大） lower_bound(begin(),end(),x) //返回序列中第一个大于等于x的元素的地址 upper_bound(begin(),end(),x) //返回序列中第一个大于x的元素的地址 序列是降序的（从大到小） lower_bound(begin(),end(),x,greater()) //返回序列中第一个小于等于x的元素的地址 upper_bound(begin(),end(),x,greater()) //返回序列中第一个小于x的元素的地址 set 或者 map 中的语法： 和数组差不多，只不过返回的是迭代器： s.lower_bound(x) //返回序列中第一个大于等于x的元素的地址 s.upper_bound(x) //返回序列中第一个大于x的元素的地址 重点注意：如果当前序列中找不到符合条件的元素，那么返回end(),对于数组来说，返回查询区间的首地址位置，对于set来讲，返回end()-1后面元素的迭代器，也就是begin(); set set/multiset 前者去重后者不去重 intsert() 插入一个数 find() 查找一个数 count() 返回一个数的个数 erase() (1) 输入是一个数x，删除所有x O(k + logn) (2) 输入一个迭代器，删除这个迭代器 map map/multimap (它们都是关联容器，增删效率为log级别，并且依据key能自动排序，默认小于，前者key不允许重复，后者允许) insert() 插入的数是一个pair erase() 输入的参数是pair或者迭代器 find() [] 注意multimap不支持此操作。 时间复杂度是 O(logn) lower_bound()/upper_bound() 迭代器的使用 vector::iterator iter; map::iterator iter; set::iterator iter; 等等..... 迭代器可以像指针一样，遍历STL时可以直接对迭代器 ++ -- ； 访问迭代器的值的形式： *iter iter->first iter->second unordered.... unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表 和上面类似，增删改查的时间复杂度是 O(1) 不支持 lower_bound()/upper_bound()， 迭代器的++，-- bitset之前写过一篇博客介绍bitset：c++中Bitset用法 bitset, 圧位（存放一个十进制数的二进制，可以像数组一样来使用） bitset s; ~, &, |, ^ >>, ='0'&&ch= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); } 归并排序 void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i eps) { double mid = (l + r) / 2;//注意double类型不能用右移运算 if (check(mid)) r = mid; else l = mid; } return l; } 整数三分模板三分整数求极值的时候，往往不在 最后l 或者 r的地方取，而是遍历l~r之后取极值 //以凸函数位例子 int check(x){.....} //返回判断当前点对应的函数值 int bsearch_1(int l, int r) { while (l < r-1) { //三分的两个中点有两种写法 // m1 = l+(r-l)/3; // m2 = r-(r-l)/3; m1 = l+r>>1; m2 = m1+r>>1; if(check(m1) > check(m2)) r=m2; else l=m1; } return l; } //对于极大值的求法我觉得有个技巧吧，就是while里面的范围，l和 r 差的 范围可以扩大一点点 //这样最后求极大值时可以遍历l到r，避免的精度不到位出现问题； 浮点数三分模板 //以凸函数位例子 double check(x){.....} //返回判断当前点对应的函数值 double bsearch_1(double l, double r) { while (r-l>eps) { //三分的两个中点有两种写法 // m1 = l+(r-l)/3; // m2 = r-(r-l)/3; m1 = (l+r)/2; m2 = (m1+r)/2; if(check(m1) > check(m2)) r=m2; else l=m1; } return l; } 高精度加法 // 注意 A 和 B 是将两个数的每一位倒着放进了vector里面； // C = A + B, A >= 0, B >= 0,也就是说A的长度要大于B； vector add(vector &A, vector &B) { if (A.size() < B.size()) return add(B, A); vector C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } 高精度减法 // 注意 A 和 B 是将两个数的每一位倒着放进了vector里面； // C = A - B, 满足A >= B, A >= 0, B >= 0 vector sub(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back();//消除前导零 return C; } 高精度乘低精度 // 注意 A 和 B 是将两个数的每一位倒着放进了vector里面； // C = A * b, A >= 0, b > 0 vector mul(vector &A, int b) { vector C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } return C; } 高精度除以低精度 //注意vector A，B是将每个数的每一位倒着存储在A，B里面了 // A / b = C ... r, A >= 0, b > 0 vector div(vector &A, int b, int &r) { vector C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } 位运算模板 求n的二进制的第k位数字: n >> k & 1 返回n的二进制最后一位1所代表的十进制数：lowbit(n) = n & -n ### 当枚举状态时假设有n个点，每个点有两种状态，那么一共就有2^n个状态，所以可以用位运算来枚举每种方案里面的状态；1~2^n-1里面的所有的数都可以作为一种方案，比如n=5，那么枚举1~31，假设枚举到12，它的二进制为 01100 ，利用位运算判断12的哪一位是1，就证明对第几个点进行了相应的操作； 子矩阵的和 S[i, j] = 第i行j列格子左上部分所有元素的和（也就是矩阵前缀和） 矩阵前缀和的求法：S[i, j] = S[i-1, j] + s[i, j-1] -s[i-1, j-1] 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1] 差分矩阵简单的区间差分插入操作： void insert(int l,int r,int x) { b[l]+=x,b[r+1]-=x; } 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c： S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c 双指针算法 for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 数据离散化 保序离散化 vector alls; // 存储所有待离散化的值 sort(alls.begin(), alls.end()); // 将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素 // 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n } 非保序离散化 unordered_map mp;//增删改查的时间复杂度是 O(1) int res; int find(int x) { if(mp.count(x)==0) return mp[x]=++res; return mp[x]; } RMQ（ST表查询区间最值） //以查询最大值为例 状态表示： 集合：f(i,j)表示从位置i开始长度为2^j的区间的最大值； 属性：MAX 状态转移： f(i,j)=max(f(i,j-1),f(i+(1 |
| CopyRight 2018-2019 实验室设备网 版权所有 |