第一章 基础算法
一、排序
快速排序 (不稳定)
板子:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void quick_sort (int q[],int l,int r) { if (l>=r) return ; int x=q[(l + r) >> 1 ]; int i=l-1 ,j=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); }
归并排序(稳定的)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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 <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0 ; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
二、二分
有单调性的一定可以二分,能二分的不一定有单调性
本质:具有二段性,寻找边界
整数二分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 bool check (int x) {} int bsearch_1 (int l, int r) { while (l < r) { int mid = l + r >> 1 ; if (check (mid)) r = mid; else l = mid + 1 ; } return l; } int bsearch_2 (int l, int r) { while (l < r) { int mid = l + r + 1 >> 1 ; if (check (mid)) l = mid; else r = mid - 1 ; } return l; }
浮点数二分
1 2 3 4 5 6 7 8 9 10 11 12 13 bool check (double x) {} double bsearch_3 (double l, double r) { const double eps = 1e-6 ; while (r - l > eps) { double mid = (l + r) / 2 ; if (check (mid)) r = mid; else l = mid; } return l; }
三、高精度
存储都是用vector,且从低位到高位存储
加法:A + B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <iostream> #include <algorithm> #include <vector> using namespace std;string a,b; vector<int > add (vector<int > &A,vector<int > &B) { vector<int > C; if (A.size ()<B.size ()) return add (B,A); 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 (1 ); return C; } int main () { cin>>a>>b; vector<int > A,B,C; for (int i=a.size ()-1 ;i>=0 ;i--) A.push_back (a[i]-'0' ); for (int i=b.size ()-1 ;i>=0 ;i--) B.push_back (b[i]-'0' ); C=add (A,B); for (int i=C.size ()-1 ;i>=0 ;i--) cout<<C[i]; return 0 ; }
减法:A - B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <iostream> #include <algorithm> #include <vector> using namespace std;string a,b; bool cmp (vector<int > &A,vector<int > &B) { if (A.size ()!=B.size ()) return A.size ()>B.size (); for (int i=A.size ();i>=0 ;i--) { if (A[i]!=B[i]) return A[i]>B[i]; } return true ; } vector<int > sub (vector<int > &A,vector<int > &B) { vector<int > C; int t=0 ; for (int i=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; } int main () { cin>>a>>b; vector<int > A,B,C; for (int i=a.size ()-1 ;i>=0 ;i--) A.push_back (a[i]-'0' ); for (int i=b.size ()-1 ;i>=0 ;i--) B.push_back (b[i]-'0' ); if (cmp (A,B)) { C=sub (A,B); for (int i=C.size ()-1 ;i>=0 ;i--) cout<<C[i]; } else { C=sub (B,A); cout<<'-' ; for (int i=C.size ()-1 ;i>=0 ;i--) cout<<C[i]; } return 0 ; }
乘法:A * a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <iostream> #include <algorithm> #include <vector> using namespace std;string a; int b;vector<int > mul (vector<int > &A,int b) { vector<int > 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 ; } while (C.size ()>1 && C.back ()==0 ) C.pop_back (); return C; } int main () { cin>>a; cin>>b; vector<int > A,C; for (int i=a.size ()-1 ;i>=0 ;i--) A.push_back (a[i]-'0' ); C=mul (A,b); for (int i=C.size ()-1 ;i>=0 ;i--) cout<<C[i]; return 0 ; }
除法:A / a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> #include <algorithm> #include <vector> using namespace std;string a; int b;vector<int > div (vector<int > &A,int b,int &r) { vector<int > C; 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; } int main () { vector<int > A,C; cin>>a; cin>>b; int r=0 ; for (int i=a.size ()-1 ;i>=0 ;i--) A.push_back (a[i]-'0' ); C=div (A,b,r); for (int i=C.size ()-1 ;i>=0 ;i--) cout<<C[i]; cout<<endl<<r<<endl; return 0 ; }
四、前缀和
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 :
S i S_i
S i
为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换
s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]
前缀和的作用 :快速求出元素组中某段区间的和
求 [l, r]中的和, 即为 S[r] - S[l-1]
五、差分
作用:给某一区间的数都加上一个值
差分是前缀和的逆运算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void insert (int l,int r,int c) { b[l]+=c; b[r+1 ]-=c; } while (m--){ int l,r,c; cin>>l>>r>>c; insert (l,r,c); } for (int i=1 ;i<=n;i++){ b[i]+=b[i-1 ]; printf ("%d " ,b[i]); }
六、双指针算法
本质:优化多重循环
例题1: 799. 最长连续不重复子序列
给定一个长度为 n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 nn个整数(均在 0∼10^5 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例:
输出样例:
核心思路:
遍历数组a中的每一个元素a[i], 对于每一个i,找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列,长度为i - j + 1, 将这一长度与r的较大者更新给r。
对于每一个i,如何确定j的位置:由于[j, i - 1]是前一步得到的最长连续不重复子序列,所以如果[j, i]中有重复元素,一定是a[i],因此右移j直到a[i]不重复为止(由于[j, i - 1]已经是前一步的最优解,此时j只可能右移以剔除重复元素a[i],不可能左移增加元素,因此,j具有“单调性”、本题可用双指针降低复杂度)。
用数组s记录子序列a[j ~ i]中各元素出现次数,遍历过程中对于每一个i有四步操作:cin元素a[i] -> 将a[i]出现次数s[a[i]]加1 -> 若a[i]重复则右移j(s[a[j]]要减1) -> 确定j及更新当前长度i - j + 1给r。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> using namespace std;const int N=100010 ;int a[N],s[N];int main () { int n; cin>>n; for (int i=0 ;i<n;i++) cin>>a[i]; int res=1 ; for (int i=0 ,j=0 ;i<n;i++){ s[a[i]]++; while (j<=i && s[a[i]]>1 ) { s[a[j]]--; j++; } res=max (res,i-j+1 ); } cout<<res<<endl; return 0 ; }
例题2: 800. 数组元素的目标和
给定两个升序排序的有序数组 A 和 B,以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j] = x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x 分别表示 AA的长度,B 的长度以及目标值 x。
第二行包含 n 个整数,表示数组 A。
第三行包含 m 个整数,表示数组 B。
输出格式
共一行,包含两个整数 i 和 j。
数据范围
数组长度不超过 10^5。
同一数组内元素各不相同。
1≤数组元素≤10^9
输入样例:
输出样例:
核心思路:
双指针的核心:将上一状态指针所表达的信息传递至下一状态,从而减少无谓的搜索。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std;const int N=100010 ;int a[N],b[N];int main () { int n,m,x; cin>>n>>m>>x; for (int i=0 ;i<n;i++) cin>>a[i]; for (int j=0 ;j<m;j++) cin>>b[j]; for (int i=0 ,j=m-1 ;i<n;i++){ while (j>=0 && a[i]+b[j]>x) j--; if (a[i]+b[j]==x) { cout<<i<<' ' <<j<<endl; break ; } } return 0 ; }
七、位运算
常用操作:
n的二进制表示中第k位是几 n>>k&1
①先把第k位数字移到最后一位 n>>k
②看个位是几 x&1
应用:
输出一个十进制数的八位二进制表示:
1 for (int i=k;k>=0 ;k--) cout << (x>>k & 1 );
lowbit(x) : 返回x的最后一位 1 x&-x
eg: x = 10 lowbit(x) = 10
x = 101000 lowbit(x) = 1000
应用:
返回一个数的二进制表示中1的个数
1 2 int res=0 ;while (x) x-=lowbit (x),res++;
八、离散化
前置知识:
unique函数:
erase函数:
a.erase(pos,n);
删除从pos
开始的n
个字符,比如 erase(0,1)
就是删除第一个字符
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std;typedef pair<int ,int > PII;const int N=300010 ;int a[N],s[N];vector<int > alls; vector<PII> add,query; int find (int 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 ; } int main () { int n,m; cin>>n>>m; for (int i=0 ;i<n;i++) { int x,c; cin>>x>>c; add.push_back ({x,c}); alls.push_back (x); } for (int i=0 ;i<m;i++) { int l,r; cin>>l>>r; query.push_back ({l,r}); alls.push_back (l); alls.push_back (r); } sort (alls.begin (),alls.end ()); alls.erase (unique (alls.begin (),alls.end ()),alls.end ()); for (auto item : add) { int x = find (item.first); a[x] += item.second; } for (int i=1 ;i<=alls.size ();i++) { s[i] = a[i] + s[i-1 ]; } for (auto item : query) { int l = find (item.first),r = find (item.second); cout<<s[r]-s[l-1 ]<<endl; } return 0 ; }
return 0;
}