1.基础算法

（1）一维前缀和

#include<iostream>using namespace std;const int N = 1e5+10;int p[N],res[N];
int n,Q,l,r;int main()
{cin >> n >> Q;for(int i = 1;i<=n;++i){cin >> p[i];res[i] = res[i - 1] + p[i];}while(Q--){cin >> l >> r;cout << res[r] - res[l - 1] << endl;}return 0;}

（2）二维前缀和

#include<iostream>using namespace std;const int N = 1005;int p[N][N],res[N][N];
int n,m,Q,x1,x2,y1,y2;int main()
{cin >> n >> m >> Q;for(int i = 1;i <= n; ++i){for(int j = 1;j<=m;++j){cin >> p[i][j];res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + p[i][j];}} while(Q--){cin >> x1 >> y1 >> x2 >> y2;cout << res[x2][y2] + res[x1 - 1][y1 - 1] - res[x1 - 1][y2] - res[x2][y1 - 1] << endl; }return 0;}

（3) 一维差分

#include<iostream>using namespace std;const int N = 1e5 + 10;int p[N],res[N];
int n,Q,l,r,x;int main(){cin >> n >> Q;for(int i = 1;i <= n;++i){cin >> p[i];res[i] = p[i] - p[i - 1];}while(Q--){cin >> l >> r >> x;res[l] += x;res[r + 1] -= x;}int tot = 0;for(int i = 1;i<=n;++i){tot += res[i];cout << tot << ' ';}return 0;
}

（4）二维差分

#include<iostream>using namespace std;const int N = 1005;int p[N][N],res[N][N];int n,m,Q,x1,y1,x2,y2,c;void add(int x1,int y1,int x2,int y2,int c)
{res[x1][y1] += c;res[x2 + 1][y2 + 1] += c;res[x1][y2 + 1] -= c;res[x2 + 1][y1] -= c; 
}int main()
{cin >> n >> m >> Q;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){cin >> p[i][j];add(i,j,i,j,p[i][j]);}}while(Q--){cin >> x1 >> y1 >> x2 >> y2 >> c;add(x1,y1,x2,y2,c);}for(int i = 1;i <= n; ++i){for(int j = 1;j <= m; ++j){res[i][j] += res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1];cout << res[i][j] << ' ';}cout << endl;}return 0;} 

（5）双指针

#include<iostream>using namespace std;const int N = 1e5 + 10;int cnt[N],p[N];
int n,len = -1;int main(){cin >> n;for(int i = 1;i<=n;++i){cin >> p[i];}for(int i = 1,j = 1;j <= n;++j){cnt[p[j]]++;while(cnt[p[j]] > 1){cnt[p[i]]--;i++;}len = max(j - i + 1,len);	}cout << len << endl;return 0;
}

（6）区间合并

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;const int N = 1e5 + 10;typedef pair<int,int>PII;vector<PII>q;int n;
int cnt = 0;int main(){cin >> n;for(int i = 1;i <= n; ++i){int l,r;cin >> l >> r;q.push_back({l,r}); }sort(q.begin(),q.end());for(int i = 0;i < q.size();++i){int l,r;if(i == 0){cnt ++;l = q[i].first;r = q[i].second;	continue;}if(q[i].first <= r) r = max(q[i].second,r);else{cnt ++;l = q[i].first;r = q[i].second;}}cout << cnt << endl;return 0;
} 

（7）归并排序与逆序对

#include<iostream>#include<vector>using namespace std; const int N = 1e5 + 10;int n,p[N];int cnt = 0;void merge(int l,int r){if(l >= r) return;vector<int>t;t.clear();int mid = (l + r) / 2;merge(l,mid),merge(mid + 1,r);int i = l,j = mid + 1;while(i <= mid && j <= r){if(p[i] > p[j]){cnt += mid - i + 1;t.push_back(p[j]);j++;}if(p[i] <= p[j]){t.push_back(p[i]);i++;}}while(i <= mid){t.push_back(p[i]);i++;}while(j <= r){t.push_back(p[j]);j++;}for(int i = 0;i < t.size(); ++i) p[i + l] = t[i];return; }int main(){cin >> n;for(int i = 1;i <= n; ++i) cin >> p[i];merge(1,n);cout << cnt << endl;for(int i = 1;i <= n; ++i) cout << p[i] << ' ';return 0;}

（8）单调栈

#include<iostream>
#include<stack>using namespace std;int n,p;
stack<int>q;int main()
{cin >> n;while(n--){cin >> p;while(q.size() != 0 && q.top() >= p){q.pop();}if(q.size() == 0) cout << -1 << ' ';else cout << q.top() << ' '; q.push(p); }return 0;
}

（9）单调队列

#include<iostream>using namespace std;const int N = 1e6 + 10;int q[N],p[N];
int n,len;int main()
{cin >> n >> len;for(int i = 0;i < n; ++i) cin >> p[i];int h,t;h = 0,t = -1;for(int i = 0;i < n; ++i){while(h <= t && q[h] < i - len + 1) h++;while(h <= t && p[q[t]] >= p[i]) t--;t++;q[t] = i;if(i >= len - 1) cout << p[q[h]] << ' ';}cout << endl;h = 0,t = -1;for(int i = 0;i < n; ++i){while(h <= t && q[h] < i - len + 1) h++;while(h <= t && p[q[t]] <= p[i]) t--;t++;q[t] = i;if(i >= len - 1) cout << p[q[h]] << ' ';}return 0;
} 

（10）整数二分

#include<iostream>using namespace std;const int N = 1e5 + 10;int p[N];
int n,Q,x;int leftfind(int x)
{int l = 1,r = n;while(l < r){int mid = (l + r) / 2;if(p[mid] < x) l = mid + 1;else r = mid;}if(p[l] == x) return l - 1;else return -1;
}int rightfind(int x){int l = 1,r = n;while(l < r){int mid = (l + r + 1) / 2;if(p[mid] > x) r = mid - 1;else l = mid;}if(p[l] == x) return l - 1;else return -1;
}int main(){cin >> n >> Q;for(int i = 1;i <= n; ++i) cin >> p[i];while(Q--){cin >> x;cout << leftfind(x) << ' ';cout << rightfind(x) << endl;	}return 0;
} 

2.数论

（1）快速幂

#include<iostream>using namespace std;typedef long long LL;int Q;LL qmi(LL a,LL b,LL mod){LL res = 1;while(b){if(b&1) res = res * a % mod;a = a * a % mod;b = b >> 1;}return res;
}int main()
{cin >> Q;while(Q--){LL a,b,c;cin >> a >> b >> c;cout << qmi(a,b,c) << endl;}return 0;
} 

（2）约数个数

#include<unordered_map>
#include<iostream>using namespace std;unordered_map<int,int>q;
unordered_map<int,int>::iterator it;const int mod = 1e9 + 7;typedef long long LL; void handle(int x){for(int i = 2;i * i <= x;++i){if(x % i == 0){int cnt = 0;while(x % i == 0){x = x / i;cnt++;}q[i] += cnt;}}if(x > 1) q[x] += 1;}int Q,x;
LL ans = 1;int main()
{cin >> Q;while(Q--){cin >> x;handle(x); }for(it = q.begin();it != q.end();++it){int a = it->first;int b = it->second;LL res = 1;for(int i = 1;i <= b; ++i){LL res = (res * a + 1) % mod;}ans = ans * res % mod;}cout << ans << endl;
}

（3）约数之和

#include<unordered_map>
#include<iostream>using namespace std;unordered_map<int,int>q;
unordered_map<int,int>::iterator it;const int mod = 1e9 + 7;typedef long long LL; void handle(int x){for(int i = 2;i * i <= x;++i){if(x % i == 0){int cnt = 0;while(x % i == 0){x = x / i;cnt++;}q[i] += cnt;}}if(x > 1) q[x] += 1;}int Q,x;
LL ans = 1;int main()
{cin >> Q;while(Q--){cin >> x;handle(x); }for(it = q.begin();it != q.end();++it){int a = it->first;int b = it->second;LL res = 1;while(b--) {res = (res * a + 1) % mod;}ans = ans * res % mod;}cout << ans << endl;return 0;
}

（4）组合数（一）

#include<iostream>using namespace std;typedef long long LL;const int mod = 1e9 + 7;
const int N = 2005;int c[N][N];
int main()
{for(int i = 0;i < N; ++i){for(int j = 0;j <= i; ++j){if(j == 0) c[i][j] = 1;else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;}}int Q;cin >> Q;while(Q--){int a,b;cin >> a >> b;cout << c[a][b] << endl; }return 0;
}

（5）组合数（二）

#include<iostream>using namespace std;const int N = 1e5 + 5;
const int mod = 1e9 + 7;typedef long long LL;LL f[N],inf[N];LL qmi(LL a,LL b,LL mod)
{LL res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b = b >> 1;}return res;
} int main()
{f[0] = inf[0] = 1;for(int i = 1;i < N;++i){f[i] = f[i - 1] * i % mod;inf[i] = qmi(f[i],mod - 2,mod);}int Q,a,b;cin >> Q;while(Q--){cin >> a >> b;LL ans = f[a] * inf[b] % mod * inf[a - b] % mod;cout << ans << endl;}return 0;	} 

（6）位运算

#include<iostream>using namespace std;int main(){int Q,x,cnt = 0;cin >> Q;while(Q--){cnt = 0;cin >> x;while(x){if(x&1) cnt++;x = x >> 1;}cout << cnt << ' ';}return 0;
}

（7）快速幂求解逆元

#include<iostream>using namespace std;typedef long long LL;LL qmi(LL a,LL b,LL mod){LL res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b = b >> 1;}return res;
} int main(){int Q;cin >> Q;while(Q--){LL a,p;cin >> a >> p;if(a % p == 0){cout << "impossible" << endl;continue; }cout << qmi(a,p - 2,p) << endl;}return 0;
}

（8）gcd

#include<iostream>using namespace std;int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}int Q,a,b;int main()
{cin >> Q;while(Q--){cin >> a >> b;	cout << gcd(a,b) << endl;}return 0;}

（9）欧拉函数

#include<iostream>using namespace std;typedef long long LL;LL euler(int x)
{LL res = x;for(int i = 2;i * i <= x;++i){if(x % i == 0){res = res * (i - 1) / i;while(x % i == 0) x = x/i;}	}if(x > 1) res = res * (x - 1) / x; return res;
}int main(){int Q,x;cin >> Q; while(Q--){cin >> x;cout << euler(x) << endl;} return 0;
}

3.图论

（1）djistra

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>using namespace std;const int N = 1e6 + 10;int dist[N];
bool st[N];
int ne[N],e[N],w[N],h[N],idx;int n,m;typedef pair<int,int>PII;
priority_queue<PII,vector<PII>,greater<PII>>q;void add(int a,int b,int c)
{e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}int djistra()
{dist[1] = 0;q.push({0,1});while(q.size() != 0){PII t = q.top();q.pop();int v = t.second,d = t.first;if(st[v]) continue;st[v] = true;for(int i = h[v];i != -1;i = ne[i]){int j = e[i];if(dist[j] > d + w[i]){dist[j] = d + w[i];q.push({dist[j],j});}}	}  if(dist[n] == 0x3f3f3f3f) return -1;else return dist[n];}int main()
{memset(h, -1 ,sizeof(h));memset(dist, 0x3f, sizeof(dist));cin >> n >> m;for(int i = 1;i <= m; ++i){int a,b,c;cin >> a >> b >> c;add(a,b,c);}cout << djistra() << endl;return 0;}

（2）floyd

#include<iostream>
#include<cstring>using namespace std;const int N = 205;int p[N][N];int n,m,k;void floyd(){for(int k = 1;k <= n; ++k){for(int i = 1;i <= n; ++i){for(int j = 1;j <= n; ++j){if(p[i][j] > p[i][k] + p[k][j]) p[i][j] = p[i][k] + p[k][j];}}}
}int main()
{cin >> n >> m >> k;memset(p,0x3f,sizeof(p));for(int i = 1;i <= n; ++i) p[i][i] = 0;for(int i = 1;i <= m; ++i){int a,b,c;cin >> a >> b >> c;p[a][b] = min(p[a][b],c);}floyd(); while(k--){int a,b;cin >> a >> b;if(p[a][b] > 0x3f3f3f3f/2) cout << "impossible" << endl;else cout << p[a][b] << endl;}return 0;}

（3）spfa

#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int N = 1e6 + 10;int dist[N];
int h[N],e[N],ne[N],w[N],idx;
bool st[N];int n,m;void add(int a,int b,int c)
{e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}void spfa()
{queue<int>q;dist[1] = 0;st[1] = true; q.push(1);while(q.size() != 0){auto t = q.front();q.pop();st[t] = false;for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(st[j]) continue;st[j] = true;q.push(j);		}	}	}if(dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;else cout << dist[n] << endl;	
}int main()
{memset(h,-1,sizeof(h));memset(dist,0x3f,sizeof(dist));cin >> n >> m;for(int i = 1;i <= m;++i){int a,b,c;cin >> a >> b >> c;add(a,b,c);}spfa();return 0; 
}

（4）树的遍历

#include<iostream>
#include<cstring>using namespace std;const int N = 1e5 + 10;bool st[N];
int e[N * 2],ne[N * 2],h[N * 2],idx = 0;
int n,ans = 0x3f3f3f3f;void add(int a,int b)
{e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}int dfs(int u)
{st[u] = true;int sum = 0,tot = -1;for(int i = h[u];i != -1;i = ne[i]){int j = e[i];if(st[j]){int k = dfs(j);sum += k;tot = max(tot,k);}		}tot = max(n - 1 - sum,tot);ans = min(tot,ans);return sum + 1;}int main()
{memset(h,-1,sizeof(h));cin >> n;for(int i = 1;i <= n-1;++i){int a,b;cin >> a >> b;add(a,b);add(b,a);}dfs(1);cout << ans << endl;return 0;}

（5）图的遍历

#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int N = 1e5 + 10;int ne[N],h[N],e[N],idx = 0;
int dist[N];
bool st[N];
int n,m;void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;
} void bfs(int u)
{st[u] = true;queue<int>q;q.push(1);while(q.size() != 0){int t = q.front();q.pop();st[t] = true;for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(st[j]) continue;if(dist[j] > dist[t] + 1) dist[j] = dist[t] + 1;q.push(j);}}return;}int main()
{memset(h,-1,sizeof(h));memset(dist,0x3f,sizeof(dist));cin >> n >> m;for(int i = 1;i <= m; ++i){int a,b;cin >> a >> b;add(a,b);}dist[1] = 0;bfs(1);if(dist[n] == 0x3f3f3f3f) cout << "-1" << endl;else cout << dist[n] << endl;return 0;
}

（6）拓扑序列

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int N = 1e5 + 10;int in[N];
int h[N],ne[N],e[N],idx = 0;
bool st[N];vector<int>ans;
int n,m;void add(int a,int b)
{e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}void bfs()
{	queue<int>q;for(int i = 1;i <= n; ++i) if(in[i] == 0) q.push(i);while(q.size() != 0){int t = q.front();q.pop();ans.push_back(t);for(int i = h[t];i != -1;i = ne[i]){int j = e[i];in[j]--;if(in[j] == 0) q.push(j);}} return;}int main()
{memset(h,-1,sizeof(h));cin >> n >> m;for(int i = 1;i <= m;++i){int a,b;cin >> a >> b;in[b]++;add(a,b);}bfs(); if(ans.size() != n) cout << "-1" << endl;else{for(int i = 0;i < n; ++i) cout << ans[i] << ' '; }return 0;}