acwing-y总基础课算法笔记整理

本文主要是介绍acwing-y总基础课算法笔记整理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

技巧

vector, 变长数组，倍增的思想size()  返回元素个数 capacity() 容量empty()  返回是否为空clear()  清空front()/back()push_back()/pop_back()begin()/end()[]支持比较运算，按字典序pair<int, int>first, 第一个元素second, 第二个元素支持比较运算，以first为第一关键字，以second为第二关键字（字典序）string，字符串size()/length()  返回字符串长度empty()clear()substr(起始下标，(子串长度))  返回子串c_str()  返回字符串所在字符数组的起始地址queue, 队列size()empty()push()  向队尾插入一个元素front()  返回队头元素back()  返回队尾元素pop()  弹出队头元素priority_queue, 优先队列，默认是大根堆size()empty()push()  插入一个元素top()  返回堆顶元素pop()  弹出堆顶元素定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;stack, 栈size()empty()push()  向栈顶插入一个元素top()  返回栈顶元素pop()  弹出栈顶元素deque, 双端队列size()empty()clear()front()/back()push_back()/pop_back()push_front()/pop_front()begin()/end()[]set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列size()empty()clear()begin()/end()++, -- 返回前驱和后继，时间复杂度 O(logn)set/multisetinsert()  插入一个数find()  查找一个数count()  返回某一个数的个数erase()(1) 输入是一个数x，删除所有x   O(k + logn)(2) 输入一个迭代器，删除这个迭代器lower_bound()/upper_bound()lower_bound(x)  返回大于等于x的最小的数的迭代器upper_bound(x)  返回大于x的最小的数的迭代器map/multimapinsert()  插入的数是一个pairerase()  输入的参数是pair或者迭代器find()[]  注意multimap不支持此操作。 时间复杂度是 O(logn)lower_bound()/upper_bound()unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表和上面类似，增删改查的时间复杂度是 O(1)不支持 lower_bound()/upper_bound()， 迭代器的++，--bitset, 圧位bitset<10000> s;~, &, |, ^>>, <<==, !=[]count()  返回有多少个1any()  判断是否至少有一个1none()  判断是否全为0set()  把所有位置成1set(k, v)  将第k位变成vreset()  把所有位变成0flip()  等价于~flip(k) 把第k位取反

排序

基础算法

排序

快速排序

void quick_sort(int q[], int l, int r)
{if (l >= 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 <= 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];
}

二分

模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 结果是找到序列中满足要求最左边的数
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
//结果是找到序列中最右边的数
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;
}

数的范围

#include<iostream>
using namespace std;const int N=100010;
int n,m,q[N];
int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&q[i]);while(m--){int x; scanf("%d",&x);int l=0,r=n-1,mid;while(l<r){mid = l+r>>1;if(q[mid]>=x) r=mid;else l = mid+1;}if(q[l]!=x) cout<<"-1 -1"<<endl;else{cout<<l<<' ';l=0,r=n-1;while(l<r){mid = l+r+1>>1;if(q[mid]<=x) l=mid;else r=mid-1;}cout<<l<<endl;}}return 0;
}

数的三次方根

#include<iostream>
using namespace std;
int main(){double x,mid;cin>>x;double l=-10000,r=10000; while(r-l>1e-8){mid=(l+r)/2;if(mid*mid*mid>=x) r=mid;else l=mid;}printf("%lf",l);return 0;
}

高精度

高精度加法

#include<iostream>
#include<vector>using namespace std;
const int N=1e6+10;vector<int> add(vector<int> &A,vector<int> &B){int t=0;vector<int> C;for(int i=0;i<A.size()||i<B.size();i++){if(i<A.size()) 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(){string a,b;vector<int> A,B;cin>>a>>b;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');vector<int> C = add(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;
}

高精度减法

#include<iostream>
#include<vector>using namespace std;bool cmp(vector<int> &A,vector<int> &B){if(A.size()!=B.size()) return A.size()>B.size();else{for(int i=A.size()-1;i>=0;i--)if(A[i]!=B[i]) return A[i]>B[i];}return true;
}vector<int> sub(vector<int> &A,vector<int> &B){int t=0;vector<int> C;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(){string a,b;vector<int> A,B;cin>>a>>b;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)){vector<int> C = sub(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);}else{printf("-");vector<int> C = sub(B,A);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);}return 0;
}

乘法

#include<iostream>
#include<vector>using namespace std;
const int N=1e6+10;vector<int> mul(vector<int> &A,int b){int t=0;vector<int>C;for(int i=0;i<A.size()||t;i++){if(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(){string a;int b;vector<int> A;cin>>a>>b;for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');vector<int> C = mul(A,b);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;
}

除法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e6+10;vector<int> exc(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(){string a;int b,r=0;vector<int> A;cin>>a>>b;for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');vector<int> C = exc(A,b,r);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);cout<<endl<<r<<endl;return 0;
}

前缀和与差分

一维前缀和

	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];while(m--){scanf("%d%d",&l,&r);printf("%d\n",s[r]-s[l-1]);}

二维前缀和

for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);

一维差分

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];void insert(int l,int r,int c){b[l]+=c;b[r+1]-=c;
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) insert(i,i,a[i]);while(m--){int l,r,c; scanf("%d%d%d",&l,&r,&c);insert(l,r,c);	}for(int i=1;i<=n;i++) b[i]+=b[i-1];for(int i=1;i<=n;i++) printf("%d ",b[i]);return 0;
}

二维差分

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){b[x1][y1]+=c;b[x1][y2+1]-=c;b[x2+1][y1]-=c;b[x2+1][y2+1]+=c;
}int main(){int n,m,q;scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)insert(i,j,i,j,a[i][j]);while(q--){int x1,y1,x2,y2,c;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);insert(x1,y1,x2,y2,c);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%d ",b[i][j]);puts(""); 	}return 0;
}

双指针算法

最长连续不重复子序列

#include<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];//用于存储当前在看的区间 
int main(){int n,res=0; cin>>n;for(int i=0;i<n;i++) cin>>a[i];for(int i=0,j=0;i<n;i++){s[a[i]]++;
//		意义：停下来时j~i为连续序列，保证i扫过的数都只出现过一次while(s[a[i]]>1){//正在看的数出现过多次s[a[j]]--;//已经看过的数指针j往后移，使记录数组减小 j++;}res=max(res,i-j+1);} cout<<res; return 0;
}

数组元素的目标和

#include<iostream>
using namespace std;
const int N=100000;
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 i=0;i<m;i++) cin>>b[i];for(int i=0,j=m-1;i<n;i++){while(a[i]+b[j]>x) j--;if(a[i]+b[j]==x) cout<<i<<" "<<j;}return 0;
}

位运算-二进制表示中1的个数

#include<iostream>
using namespace std;
int lowbit(int x){return x&-x;//返回最后一个1的位置 
}
int main(){int n;cin>>n;while(n--){int x;cin>>x;int res=0;while(lowbit(x)) {res++;x-=lowbit(x);}cout<<res<<" ";}return 0;
}