不同接入商备案网站,广州网络哪家比较好,网站店招用什么软件做的,长沙网站建设外包文章目录 一、快速排序二、归并排序三、二分1. 二分的本质2. 整数二分3. 实数二分 四、前缀和1. 一维前缀和2. 二维前缀和 五、差分1. 一维差分2. 二维差分 六、常用位运算1. 求二进制的第 k 位2. lowbit 七、其他常用算法1. 去重2. 表达式求值3. 单调栈4. 单调队列5. 并查集 一… 文章目录 一、快速排序二、归并排序三、二分1. 二分的本质2. 整数二分3. 实数二分 四、前缀和1. 一维前缀和2. 二维前缀和 五、差分1. 一维差分2. 二维差分 六、常用位运算1. 求二进制的第 k 位2. lowbit 七、其他常用算法1. 去重2. 表达式求值3. 单调栈4. 单调队列5. 并查集 一、快速排序
void quick_sort(int a[], int l, int r)
{if(l r) return;int i l - 1, j r 1, x a[l r 1];while(i j){while(a[i] x);while(a[--j] x);if(i j) swap(a[i], a[j]);}quick_sort(a, l, j);quick_sort(a, j 1, r);
}应用快速选择 第k个数
//如果第k个数在左就在左区间找在右就在右区间找
//由此保证答案在区间中
int quick_sort(int a[], int l, int r, int k)
{//区间长度为1时就是答案if(l r) return a[l];int i l - 1, j r 1, x a[l r 1];while(i j){while(a[i] x);while(a[--j] x);if(i j) swap(a[i], a[j]);}//一趟快排后 前j个的数有哪些已经确定int lcnt j - l 1;if(k lcnt) return quick_sort(a, l, j, k);return quick_sort(a, j 1, r, k - lcnt);
}二、归并排序
int tmp[N];
void merge_sort(int a[], int l, int r)
{//递归出口 区间长度为0或1时已经有序if(l r) return;//先把左右区间都排好序int mid (l r) / 2;merge_sort(a, l, mid);merge_sort(a, mid 1, r);//再有序合并两个区间到辅助数组int i l, j mid 1, k 0;while(i mid j r){if(a[i] a[j]) tmp[k] a[i];else tmp[k] a[j];}//扫尾while(i mid) tmp[k] a[i];while(j r) tmp[k] a[j];//再把辅助数组拷贝给原数组for(int i l, j 0; i r; i, j) a[i] tmp[j];
}应用逆序对的个数
int tmp[N];
int merge_sort(int a[], int l, int r)
{//递归出口 区间长度为0或1时逆序对个数为0if(l r) return 0;int mid l r 1;//先分别求左右区间内部的逆序对个数int res merge_sort(a, l, mid) merge_sort(a, mid 1, r);//再求两个区间之间的逆序对个数int i l, j mid 1, k 0;while(i mid j r){if(a[i] a[j]) tmp[k] a[i];else{tmp[k] a[j];res mid - i 1;}}while(i mid) tmp[k] a[i];while(j r) tmp[k] a[j];for(int i l, j 0; i r; i, j) a[i] tmp[j];//最后返回总共的逆序对个数return res;
}三、二分
1. 二分的本质 根据某种性质将一段区间分成有这个性质和没有这个性质的两段二分出的就是这两段的边界。 因此有单调性一定可以二分没单调性也可能可以二分。
2. 整数二分
先确定答案所在区间 [ L , R ] [L, R] [L,R]考虑用什么性质来二分每次更新区间都要包含答案当 L R L R LR 时区间长度为 1 1 1就是答案
//第一种写法
while(l r)
{int mid (l r) / 2;if(check(mid)) r mid;else l mid 1;
}//第二种写法
while(l r)
{int mid (l r 1) / 2;//(1)if(check(mid)) l mid;//(2)else r mid - 1;
}
//注意(1)(2)
//当 r l 1 时如果 mid (l r) / 2 l l mid l就会死循环
//因此改为 mid (l r 1) / 2二分一定有答案可以根据二分答案判断题目是否有解。
3. 实数二分
double eps 1e-8;//经验值一般比题目保留位数多两位
while(r - l eps)
{double mid (l r) / 2;if(check(mid)) l mid;else r mid;
}
//r - l eps 时就认为 l 或 r 是答案了四、前缀和
建议下标从 1 1 1 开始
1. 一维前缀和
//定义
a[1] ... a[i] s[i]//核心操作
s[i] s[i - 1] a[i]
a[l] ... a[r] s[r] - s[l - 1]2. 二维前缀和
//定义
s[i][j] 第i行j列格子左上部分所有元素的和//以(x1, y1)为左上角(x2, y2)为右下角的矩阵的所有元素的和
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]五、差分
建议下标从 1 1 1 开始
1. 一维差分
//差分就是前缀和的逆运算
b[i] a[i] - a[i - 1]//核心操作
//给区间[l, r]中的每个数加上c
//只需对差分数组b这样操作
b[l] c, b[r 1] - c
//然后对b求前缀和就是操作后的原数组2. 二维差分
//给以(x1, y1)为左上角(x2, y2)为右下角的子矩阵中的所有元素加上c
b[x1][y1] c;
b[x2 1][y1] - c;
b[x1][y2 1] - c;
b[x2 1][y2 1] c;六、常用位运算
1. 求二进制的第 k 位
设最低位为第 0 0 0 位
//右移 k 位再 1
x k 12. lowbit
返回二进制最后一个1
//eg: x 1110 -x 0010
//x -x 0010
int lowbit(int x)
{return x -x;
}七、其他常用算法
1. 去重
vectorint v;sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());2. 表达式求值
#includebits/stdc.h
using namespace std;stackint num;//操作数栈
stackchar op;//运算符栈void eval()
{int b num.top(); num.pop();int a num.top(); num.pop();char c op.top(); op.pop();int res;if(c ) res a b;else if(c -) res a - b;else if(c *) res a * b;else res a / b;num.push(res);
}int main()
{//运算符优先级表unordered_mapchar, int p{{, 1}, {-, 1}, {*, 2}, {/, 2}};string s; cin s;for(int i 0; i s.size(); i){if(isdigit(s[i])){int x 0, j i;while(j s.size() isdigit(s[j]))x x * 10 s[j] - 0;i j - 1;num.push(x);}else if(s[i] () op.push(s[i]);else if(s[i] )){while(op.top() ! () eval();op.pop();}else{while(!op.empty() op.top() ! ( p[op.top()] p[s[i]]) eval();op.push(s[i]);}}while(!op.empty()) eval();cout num.top() \n;
}3. 单调栈
常见题型
求每个数左边第一个比它小的数求每个数左边第一个比它大的数求每个数右边第一个比它小的数求每个数右边第一个比它大的数
以求每个数左边第一个比它小的数为例。我们只要维护一个栈每枚举一个数入栈之前都把栈里不小于它的数弹出这样每次求一个数左边第一个小于它的数就只需要取栈顶元素。
题目链接
参考代码
#includebits/stdc.h
using namespace std;int main()
{int n; cin n;stackint stk;for(int i 1; i n; i){int x; cin x;while(!stk.empty() stk.top() x) stk.pop();if(stk.empty()) cout -1 ;else cout stk.top() ;stk.push(x);}
}4. 单调队列
常见题型滑动窗口求最值
首先滑动窗口可以用一个队列来维护滑动窗口每次向右走一步队尾就插入一个数由于滑动窗口的长度是定值如果此时队头不合法就要弹出一个数。 暴力的做法是滑动窗口每走一步都扫描一遍滑动窗口的区间求最值。显然这种做法是 O ( N 2 ) O(N^2) O(N2) 的。 如何优化呢以求最大值为例每枚举一个数入队之前都把队列里不大于它的数弹出再将这个数入队以此来维护一段单调递减的区间。这样滑动窗口每次求最大值就只需要取队头元素。
题目链接
参考代码
#includebits/stdc.h
using namespace std;const int N 1e6 10;
int a[N];int main()
{int n, k; cin n k;for(int i 1; i n; i) cin a[i];dequeint dq;//队列存下标才能判断队头合法性//滑动窗口最小值for(int i 1; i n; i){//判断队头合法性: 右端为i长度为k的区间[i - k 1, i]if(!dq.empty() dq.front() i - k 1) dq.pop_front();//维护队列单调递增while(!dq.empty() a[dq.back()] a[i]) dq.pop_back();dq.push_back(i);//滑动窗口最小值取队头即可if(i k) cout a[dq.front()] ;}cout \n;//清空队列dq.clear();//滑动窗口最大值for(int i 1; i n; i){//判断队头合法性: 右端为i长度为k的区间[i - k 1, i]if(!dq.empty() dq.front() i - k 1) dq.pop_front();//维护队列单调递减while(!dq.empty() a[dq.back()] a[i]) dq.pop_back();dq.push_back(i);//滑动窗口最大值取队头即可if(i k) cout a[dq.front()] ;}
}5. 并查集
题目链接
参考代码
#includebits/stdc.h
using namespace std;const int N 1e5 10;
int p[N];
//p[x]是x的父亲
//p[x]x表示x是根//返回根
int find(int x)
{if(p[x] ! x) p[x] find(p[x]);//路径压缩return p[x];
}int main()
{int n, m; cin n m;//初始化for(int i 1; i n; i) p[i] i;while(m--){string s;int a, b;cin s a b;if(s M) p[find(a)] find(b);//合并else{if(find(a) find(b))//查询cout Yes \n;elsecout No \n;}}
}
