二分
AcWing 789. 数的范围 - AcWing
#include<iostream>using namespace std;const int N = 100009;int arr[N];int findLeft(int v,int left,int right){int i = left,j = right,candidate=-1;while(i<=j){//有等于号int mid = (i+j)>>1;//每次二分是对更新后的左右坐标二分if(arr[mid]>v){j = mid-1;}else if(arr[mid]<v){i = mid+1;}else{j = mid-1;candidate = mid;}}return candidate;
}int findRight(int v,int left,int right){int i = left,j = right,candidate=-1;while(i<=j){int mid = (i+j)>>1;if(arr[mid]>v){j = mid-1;}else if(arr[mid]<v){i = mid+1;}else{i = mid+1;candidate = mid;}}return candidate;
}int main(){int n,q;scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&arr[i]);}while(q--){int v;scanf("%d",&v);int le = findLeft(v,1,n);if(le==-1){printf("-1 -1\n");continue;}else{int ri = findRight(v,1,n);printf("%d %d\n",le-1,ri-1);}}return 0;
}高精度加法
AcWing 791. 高精度加法 - AcWing
#include<iostream>
#include<vector>
#include<string>
using namespace std;const int N = 100009;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=t/10;}if(t) C.push_back(t);return C;
}int main(){string s1,s2;cin>>s1>>s2;vector<int> A,B,C;for(int i=s1.size()-1;i>=0;i--) A.push_back(s1[i]-'0');//这里size()返回实际长度，但是vector是从0开始的。for(int i=s2.size()-1;i>=0;i--) B.push_back(s2[i]-'0');C = add(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;
}高精度减法
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int N = 1e5+9;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];}}}
}vector<int> sub(vector<int> &A,vector<int> &B){int t=0;vector<int> C;for(int i=0;i<A.size() || i<B.size();i++){t = A[i] -t;if(i<B.size()) t = t-B[i];if(t>=0){ //等于0注意，这里减为0也在这个位置直接放**********C.push_back(t);t = 0; //大于0说明没有借位，要把t重新改成0}else{C.push_back(t+10);t=1; //小于0时有借位，要更新t=1}}while(C.size()>1 && !C.back()) C.pop_back(); //如果前面位置都减为0了要去掉，但是第一个位置无论是不是0都不能去掉，因为如果去掉那就为空，连第一个0也不能打印出来return C;
}int main(){string s1,s2;vector<int> A,B,C;cin>>s1>>s2;for(int i=s1.size()-1;i>=0;i--) A.push_back(s1[i]-'0');for(int i=s2.size()-1;i>=0;i--) B.push_back(s2[i]-'0');if(cmp(A,B)){C = sub(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);}else{C = sub(B,A);if(C.back()==0){//而外判断减号，如果是0就不需要加减号了。printf("0");}else{printf("-");for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);}}return 0;
}
二维前缀和
记住这个图：
https://i-blog.csdnimg.cn/direct/28425e36aad949c9880897524b657dea.jpeg
#include<iostream>using namespace std;
const int N = 1009;
int g[N][N];
int summ[N][N];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",&g[i][j]);summ[i][j] = summ[i-1][j] + summ[i][j-1] -summ[i-1][j-1] + g[i][j];}}while(q--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",summ[x2][y2]-summ[x2][y1-1] -summ[x1-1][y2] + summ[x1-1][y1-1]);}return 0;
}差分
797. 差分 - AcWing题库
#include<iostream>using namespace std;const int N = 100009;
int arr[N],subb[N];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&arr[i]);subb[i] = arr[i]-arr[i-1];//这个也要记住，如何构建subb的？}while(m--){int l,r,c;scanf("%d%d%d",&l,&r,&c);subb[l]+=c;subb[r+1]-=c;}for(int i=1;i<=n;i++){arr[i] = arr[i-1] + subb[i];//主要是记住这个，由公式推出来的，也不知道为什么。printf("%d ",arr[i]);}return 0;
}双指针
799. 最长连续不重复子序列 - AcWing题库
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int arr[N],map[N];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&arr[i]);}int start = 1,res=1;for(int end =1;end<=n;end++){map[arr[end]]++;while(map[arr[end]]>1){map[arr[start]]--;start++;}res = max(res,end-start+1);}cout<<res;return 0;
}
位运算
AcWing 801. 二进制中1的个数 - AcWing
#include<iostream>using namespace std;
const int N = 100009;
int arr[N];int lowbit(int x){return x & -x;
}int main(){int n;scanf("%d",&n);while(n--){int x,res=0;scanf("%d",&x);while(x){int ans = lowbit(x);res++;x-=ans;}printf("%d ",res);}return 0;
}
离散化
802. 区间和 - AcWing题库
注意一定不要用add、search这些关键词做变量。
#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int N = 300009;
typedef pair<int,int> PII;
vector<int> alls;//要初始化的坐标
vector<PII> myadd,mysearch;
int a[N],s[N];
int find(int x){int i=0,j=alls.size()-1,candidate=-1;while(i<=j){int mid = (i+j)>>1;if(alls[mid] >x){j=mid-1;}else if(alls[mid]<x){i=mid+1;}else{candidate = mid;break;}}return candidate + 1;
}int main(){int n,m;scanf("%d%d",&n,&m);while(n--){int x,c;scanf("%d%d",&x,&c);myadd.push_back({x,c});alls.push_back({x});}while(m--){int l,r;scanf("%d%d",&l,&r);mysearch.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 temp:myadd){int x = find(temp.first);a[x]+=temp.second;;}for(int i=1;i<=alls.size();i++) s[i] = s[i-1] +a[i];for(auto temp:mysearch){int ll = temp.first,rr=temp.second;ll = find(ll);rr = find(rr);printf("%d\n",s[rr]-s[ll-1]);}return 0;
}单调栈
830. 单调栈 - AcWing题库
#include<iostream>
#include<stack>
using namespace std;const int N = 1e5+10;int main(){int n;stack<int> stk;scanf("%d",&n);while(n--){int x;scanf("%d",&x);while(!stk.empty() && stk.top() >= x) stk.pop();if(stk.empty()) printf("-1 ");//注意如果栈为空，那么stk.empty()返回true!!!!!!!!!!!!!!!else{printf("%d ",stk.top());}stk.push(x);}}#include<iostream>
using namespace std;
const int N = 1e5+10;
int stk[N],tt=-1;//一定要在这里初始化为-1......只有栈和队列初始化为-1.链表不需，切记切记。。。。。。
int main(){int n;scanf("%d",&n);while(n--){int x;scanf("%d",&x);while(tt!=-1 && stk[tt]>=x) tt--;//注意这里的tt--是出栈，真正出来元素，所以这里的tt是指向真正的元素的，而不是指向栈顶的上一个位置if(tt==-1) printf("-1 "); //上面while一定要有等于号，相等的只要留一个就行了********************else{printf("%d ",stk[tt]);}stk[++tt] = x;//**********************}
}单调队列
154. 滑动窗口 - AcWing题库
#include<iostream>using namespace std;
const int N = 1e6+10;
int arr[N];
int q[N],hh,tt=-1;int main(){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&arr[i]);for(int i=1;i<=n;i++){if(hh<=tt && i-k+1>q[hh]) hh++;//这里判断每一个“当前最小坐标”是否已经“过去了”while(hh<=tt && arr[q[tt]]>=arr[i]) tt--;//注意是arr[q[tt]]，q里面是坐标。q[++tt] = i;//其实可以先写后面两行if(i-k>=0) printf("%d ",arr[q[hh]]);}printf("\n");hh=0,tt=-1;for(int i=1;i<=n;i++){if(hh<=tt && i-k+1>q[hh]) hh++;while(hh<=tt && arr[q[tt]]<=arr[i]) tt--;q[++tt] = i;if(i-k>=0) printf("%d ",arr[q[hh]]);}return 0;
}并查集
836. 合并集合 - AcWing题库
837. 连通块中点的数量 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5+10;
int p[N],n,m;int myfind(int x){if(p[x] != x) p[x] = myfind(p[x]);//注意，如果其父节点不等于自身，那么将其父节点赋值为其父节点的父节点。return p[x];
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) p[i] = i; //******刚开始时每一个元素都是独立的******while(m--){char op[2];int a,b;scanf("%s",op);scanf("%d%d",&a,&b);if(op[0]=='M'){p[myfind(b)] = myfind(a);}else{if(myfind(a)==myfind(b)){printf("Yes\n");}else{printf("No\n");}}}return 0;
}#include<iostream>
using namespace std;
const int N = 1e5+10;int par[N],counter[N];int myfind(int x){if(x != par[x]) par[x] = myfind(par[x]);return par[x];
}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){par[i] = i;counter[i] = 1;}while(m--){char op[3];scanf("%s",op);if(op[0]=='C'){int a,b;scanf("%d%d",&a,&b);if(myfind(a)==myfind(b)) continue;else{counter[myfind(a)] +=counter[myfind(b)];//只有根节点才有用,***注意顺序，一定要先相加然后再合并*****par[myfind(b)] = myfind(a);}}else{if(op[1]=='1'){int a,b;scanf("%d%d",&a,&b);if(myfind(a)==myfind(b)) printf("Yes\n");else printf("No\n");}else{int a;scanf("%d",&a);printf("%d\n",counter[myfind(a)]);}}}return 0;
}哈希表
840. 模拟散列表 - AcWing题库
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int head[N],e[N],ne[N],idx;int mapp(int x){return (x%N+N)%N;
}bool query(int x){int k = mapp(x);for(int i=head[k];i!=-1;i=ne[i]){if(e[i]==x) return true;}return false;
}int main(){memset(head,-1,sizeof(head));int n;scanf("%d",&n);while(n--){char s[2];int x;scanf("%s%d",s,&x);if(s[0]=='I'){int k = mapp(x);e[idx] = x;ne[idx] = head[k];head[k] = idx;idx++;}else{if(query(x)){printf("Yes\n");}else{printf("No\n");}}}return 0;
}树的重心
846. 树的重心 - AcWing题库
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int h[N],e[2*N],ne[2*N],idx,st[N],res=N+1,n;void myadd(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx;idx++;
}
//以当前节点为根节点的子树的大小
int dfs(int u){st[u] = 1;int summ=1,ant=0;for(int i = h[u];i!=-1;i=ne[i]){int j = e[i];if(!st[j]){int s =dfs(j);summ+=s;ant = max(ant,s);}}ant = max(ant,n-summ);res = min(res,ant);return summ;
}int main(){memset(h,-1,sizeof(h));scanf("%d",&n);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);myadd(a,b);myadd(b,a);}dfs(1);cout<<res<<endl;//打印res而不是打印dfsreturn 0;
}
宽度遍历
847. 图中点的层次 - AcWing题库
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5+10;
const int INF = 10000000;
int h[N],e[N],ne[N],idx,d[N],n,m;void add(int a,int b){if(a==b) return;e[idx] = b;ne[idx] = h[a];h[a] = idx;idx++;
}int bfs(){queue<int> q;q.push(1);d[1] = 0;while(!q.empty()){int t = q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j = e[i];if(d[j]==INF){d[j] = d[t] + 1;q.push(j);//别忘了入队}}}return d[n];}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));fill(d+1,d+n+1,INF);//注意如果d从下标1开始存储，那么初始化时要加1！！！！！！！！！！！！while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);}int res = bfs();if(res==INF) cout<<-1;else cout<<res;return 0;
}Dijkstra
#include<iostream>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
const int N =510;
const int INF = 100000000;
int g[N][N],dist[N],st[N],n,m;int dijkstra(){for(int i=0;i<N;i++) dist[i] = INF;dist[1] = 0;for(int i=1;i<=n;i++){int t = -1;for(int j=1;j<=n;j++){if(!st[j] && (t==-1 || dist[t]>dist[j])){t = j;}}st[t] = 1;for(int j =1;j<=n;j++){if(g[t][j]==INF || t==j) continue;if(!st[j] && dist[j]>dist[t]+g[t][j]){dist[j] = dist[t]+g[t][j];}}}return dist[n];}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){g[i][j]=INF;}}}while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b] = min(g[a][b],c);}int res = dijkstra();if(res!=INF) cout<<res;else cout<<-1;return 0;
}SPFA
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e5+10,INF=1000000000;
int h[N],e[N],ne[N],w[N],idx,st[N],dist[N],n,m;void add(int a,int b,int c){if (a == b) return;for(int i=h[a];i!=-1;i=ne[i]){int j = e[i];if(j == b){w[i] = min(w[i],c); return ;}}e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx;idx++;
}int spfa(int start){dist[start] = 0;queue<int> q;q.push(start);st[start] = 1;while(!q.empty()){int t = q.front();q.pop();st[t] = 0;for(int i = h[t];i!=-1;i=ne[i]){//注意是i=ne[i]!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!int j =e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t]+w[i];if(!st[j]){q.push(j);st[j]=1;}}}}return dist[n];
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));fill(dist,dist+N,INF);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int res = spfa(1);if(res>INF/2) cout<<"impossible";else cout<<res;return 0;
}面向答案的二分
P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int arr[N];
int n,m,highest=0,lowest = 400000;bool check(int h){long summ=0;for(int i=1;i<=n;i++){int s = arr[i]-h;if(s<=0) s=0;summ+=s;}if(summ>=m) return true;else return false;
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);arr[i] = x;highest = max(highest,x);lowest = min(lowest,x);}int low =lowest,high = highest;long candicate = -1;while(low<=high){int mid = (low+high)>>1;if(check(mid)){low = mid+1;candicate = mid;}else{high = mid-1;}}cout<<candicate;return 0;
}
DFS零钱兑换
322. 零钱兑换 - 力扣（LeetCode）
const int N = 1e4+10;
class Solution {
public:int mem[N];int dfs(vector<int>& coins, int amount){if(mem[amount]) return mem[amount];int n = coins.size();int res = 1e9;if(amount==0) return 0;if(amount<0) return 1e9;for(int i=0;i<n;i++){if(amount>=coins[i])res = min(res,dfs(coins,amount-coins[i])+1);}mem[amount] = res;return res;}int coinChange(vector<int>& coins, int amount) {int tag = dfs(coins,amount);if(tag==1e9) return -1;else return tag;}
};仔细想一下：
DP首先要看，找到一个答案的最后一部是什么？
最后一步就是找到一个硬币，正好拼成amount元。
接着想一下，把最后一部去掉，问题变成了什么？
假如最后一个是x元，那么问题就变成找到一个。用最少的硬币数，拼成amount-x元。
原问题 = 子问题+1。
那么原问题就是用最少的硬币拼成amount-x元。
但是这里的x是可变的，所以需要从第一个枚举到最后一个x。在这里面取出最少的数量的那个组合。
