原版代码模板：https://discourse.xinyoudui.com/t/topic/1136
图论算法
Tarjan
// 找点tarjan
for (int i = 1;i <= n;i ++)
if (!dfn[i])
tarjan(i);
// 核心
void tarjon(int x) {
dfn[x] = low[x] = ++ top, vis[x] = 1; q.push(x);
for (auto i : mp[x]) {
if (!dfn[i]) {
tarjan(i);
low[x] = min(low[x],low[i]);
} else if (vis[i] && dfn[i] < low[x]) low[x] = dfn[i];
}
if (dfn[x] == low[x]) {
cnt ++;
while(q.top() != x) {
vis[q.top()] = 0,b[q.top()] = cnt;
q.pop();
}
vis[x] = 0,b[x] = cnt; q.pop();
}
}
最小生成树
Prim
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct node {
int pos, dis;
bool operator<(const node &x) const { return x.dis < dis; }
};
const int maxn = 5001, maxm = 200005 << 1;
int n, m, cnt, k, ans, vv[maxm], ww[maxm], he[maxn], to[maxm];
void add_edge(int u, int v, int w) { vv[++cnt] = v, ww[cnt] = w, to[cnt] = he[u], he[u] = cnt; }
priority_queue<node> q;
int vis[maxn], dis[maxn];
void prim() {
memset(dis, 127, sizeof(dis)); dis[1] = 0;
q.push((node) { 1, 0 });
while (!q.empty() && k < n) {
int x = q.top().pos, w = q.top().dis; q.pop();
if (vis[x]) continue;
k++, vis[x] = 1, ans += w;
for (int i = he[x]; i; i = to[i])
if (ww[i] < dis[vv[i]]) {
dis[vv[i]] = ww[i];
q.push((node) { vv[i], ww[i] });
}
}
}
int main() {
cin >> n >> m;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
prim();
if (k == n) cout << ans;
else cout << "Unknown Error";
return 0;
}
Kruskal
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 5001;
const int maxm = 200005;
struct node { int u, v, w; } a[maxm];
bool cmp(node a, node b) { return a.w < b.w; }
int n, m, cnt, k, ans, fa[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void init() { for (int i = 1; i <= n; i++) fa[i] = i; }
void kruskal() {
sort(a, a + m, cmp);
for (int i = 0; i < m; i++) {
int u = a[i].u, v = a[i].v, w = a[i].w, eu = find(u), ev = find(v);
if (eu == ev) continue;
ans += w, fa[eu] = ev;
if (++cnt == n - 1) break;
}
}
int main() {
cin >> n >> m;
init();
for (int i = 0; i < m; i++) cin >> a[i].u >> a[i].v >> a[i].w;
kruskal();
if (cnt == n - 1) cout << ans;
else cout << "orz";
return 0;
}
树上问题
最近公共祖先 LCA
#include <iostream>
using namespace std;
const int N = 5e5 + 10, M = 1e6 + 10;
int n, m, s, depth[N], fa[N][20], q[N], hh, tt, idx = 1, e[M], h[N], ne[M];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
int query(int a, int b) {
if (depth[a] < depth[b]) swap(a, b); // 我们就让a往上跳，因此如果a在上面，交换下a，b
for (int k = 19; k >= 0; k--) // 二进制优化，循环后a与b深度一定相同
if (depth[fa[a][k]] >= depth[b]) // 对于跳出界的情况，左边为0，等式不可能成立
a = fa[a][k];
if (a == b) return a; // 深度相同先判断下是否已经在同一节点
for (int k = 19; k >= 0; k--)
if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];// 如果没跳到同一点就跳，因为如果跳到了相同的节点我们无法判断是否是最近的公共祖先，这里也是二进制优化，循环后a，b两点都一定在最近公共祖先的下一层
return fa[a][0]; // 返回最近公共祖先
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1, a, b; i < n; i++) {
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
depth[s] = 1, q[0] = s; // 根节点深度为1, 根节点入队
while (hh <= tt) {
// bfs求出每个点的depth
auto t = q[hh++];
for (int i = h[t]; i; i = ne[i]) {
int j = e[i];
if (!depth[j]) {
// 如果depth为0就说明还没搜过
depth[j] = depth[t] + 1, fa[j][0] = t, q[++tt] = j; // j跳2的0次方到j的父节点
for (int k = 1; k < 20; k++) // 递推更新，跳出界的节点值都为0
fa[j][k] = fa[fa[j][k - 1]][k - 1]; // 跳2的k次方相当于从j跳2的k-1次方到达的点跳2的k-1次方
}
}
}
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", query(a, b));
}
return 0;
}
树的直径
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, m, t, ans;
int f1[N], f2[N];
int first[N], v[N], w[N], nxt[N];
void add(int x, int y, int z) { nxt[++ t] = first[x], first[x] = t, v[t] = y, w[t] = z; }
void dp(int x, int father) {
int i, j;
for (i = first[x]; i; i = nxt[i]) {
j = v[i];
if (j == father)
continue;
dp(j, x);
if (f1[x] < f1[j] + w[i]) {
f2[x] = f1[x];
f1[x] = f1[j] + w[i];
} else if (f2[x] < f1[j] + w[i])
f2[x] = f1[j] + w[i];
ans = max(ans, f1[x] + f2[x]);
}
}
int main() {
int x, y, z, i;
scanf("%d%d", &n, &m);
for (i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
dp(1, 0);
printf("%d", ans);
return 0;
}
区间操作
RMQ
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000 + 5;
int a[N];
int mn[N][25];
int n, q, l, r;
struct RMQ {
int log2[N];
void init() {
for (int i = 0; i <= n; i++)
log2[i] = (i == 0 ? -1 : log2[i >> 1] + 1);
for (int j = 1; j < 20; j++)
for (int i = 1; i + (1 << j) <= n + 1; i++)
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
}
int query(int ql, int qr) {
int k = log2[qr - ql + 1];
return min(mn[ql][k], mn[qr - (1 << k) + 1][k]);
}
} rmq;
void work() {
rmq.init();
scanf("%d", &q);
while (q--) {
scanf("%d%d", &l, &r);
printf("%d\n", rmq.query(l, r));
}
}
int main() {
while (scanf("%d", &n) == 1) {
for (int i = 1; i <= n; i++)
scanf("%d", a + i), mn[i][0] = a[i];
work();
}
return 0;
}
线段树1（区间加）
#include<bits/stdc++.h>
#define ll long long
#define lson l,mid,rt << 1
#define rson mid + 1,r,rt << 1 | 1
using namespace std;
const int maxn = 100005;
int nowl,nowr;
long long a[maxn],sum[maxn << 2];
long long col[maxn << 2];
void update(int rt) { // rt = root number
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l,int r,int rt) {// sum[rt] = a[l] + .. + a[r]
if (l == r) {
sum[rt] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
void color(int l,int r,int rt,long long k) {
sum[rt] += k * (r - l + 1);
col[rt] += k;
}
void pushcol(int l,int r,int rt) {
if (!col[rt])
return ;
int mid = (l + r) >> 1;
color(lson,col[rt]);
color(rson,col[rt]);
col[rt] = 0; // 清零
}
long long query(int l,int r,int rt) { // a[nowl] + ... + a[nowr]
if (nowl <= l && r <= nowr) // [l,r] 包含在 [nowl,nowr] 区间内不，则 sum[rt] 就可以直接统计到答案里
return sum[rt];
pushcol(l,r,rt);
long long ans = 0ll;
int mid = (l + r) >> 1;
if (nowl <= mid) // [l,mid]
ans += query(lson);
if (mid + 1 <= nowr) // [mid + 1,r]
ans += query(rson);
return ans;
}
void modify(int l,int r,int rt,long long k) {
if (nowl <= l && r <= nowr) {
color(l,r,rt,k);
return ;
}
pushcol(l,r,rt);
int mid = (l + r) >> 1;
if (nowl <= mid)
modify(lson,k);
if (mid + 1 <= nowr)
modify(rson,k);
update(rt);
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++) {
scanf("%d",&a[i]);
}
build(1,n,1);
for (int i = 1,op,x,y,k;i <= m;++i) {
scanf("%d",&op);
if (op == 1) {
scanf("%d%d%d",&x,&y,&k);
nowl = x;
nowr = y;
modify(1,n,1,k);
} else {
scanf("%d%d",&x,&y);
nowl = x;
nowr = y;
printf("%lld\n",query(1,n,1));
}
}
return 0;
}
线段树2（区间加 & 乘）
#include<bits/stdc++.h>
#define ll long long
#define lson l,mid,rt << 1
#define rson mid + 1,r,rt << 1 | 1
using namespace std;
const int maxn = 100005;
int MOD,nowl,n,m,nowr; ll a[maxn],sum[maxn << 2],colx[maxn << 2],coly[maxn << 2];
void update(int rt) { sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % MOD; }
void build(int l,int r,int rt) {
coly[rt] = 1;
if (l == r) { scanf("%lld",&sum[rt]); sum[rt] %= MOD; return ;}
int mid = (l + r) >> 1;
build(lson); build(rson); update(rt);
}
void color_x(int l,int r,int rt,ll k) { sum[rt] = (sum[rt] + (r - l + 1) * k) % MOD; colx[rt] = (colx[rt] + k) % MOD; }
void color_y(int l,int r,int rt,ll k) { sum[rt] = (sum[rt] * k) % MOD; coly[rt] = (coly[rt] * k) % MOD; colx[rt] =(colx[rt] * k) % MOD; }
void pushcol(int l,int r,int rt) {
int mid = (l + r) >> 1;
if (coly[rt] != 1) {
color_y(lson,coly[rt]);
color_y(rson,coly[rt]);
coly[rt] = 1;
}
if (colx[rt] != 0) {
color_x(lson,colx[rt]);
color_x(rson,colx[rt]);
colx[rt] = 0;
}
}
void modify_x(int l,int r,int rt,ll k) {
if (nowl <= l && r <= nowr) { color_x(l,r,rt,k); return ; }
pushcol(l,r,rt);
int mid = (l + r) >> 1;
if (nowl <= mid) modify_x(lson,k);
if (mid < nowr) modify_x(rson,k);
update(rt);
}
void modify_y(int l,int r,int rt,ll k) {
if (nowl <= l && r <= nowr) { color_y(l,r,rt,k); return ; }
pushcol(l,r,rt);
int mid = (l + r) >> 1;
if (nowl <= mid) modify_y(lson,k);
if (mid < nowr) modify_y(rson,k);
update(rt);
}
ll query(int l,int r,int rt) {
if (nowl <= l && r <= nowr) return sum[rt];
pushcol(l,r,rt);
int mid = (l + r) >> 1; ll ans = 0;
if (nowl <= mid) ans += query(lson);
if (mid < nowr) ans += query(rson);
return ans % MOD;
}
int main() {
scanf("%d%d%d",&n,&m,&MOD);
build(1,n,1);
for (int i = 1,op,x,y;i <= m;i ++) {
scanf("%d",&op);
if (op == 1) { ll k; scanf("%d%d%lld",&x,&y,&k); nowl = x,nowr = y; modify_y(1,n,1,k % MOD); }
else if (op == 2) { ll k; scanf("%d%d%lld",&x,&y,&k); nowl = x,nowr = y; modify_x(1,n,1,k % MOD); }
else { scanf("%d%d",&x,&y); nowl = x,nowr = y; printf("%lld\n",query(1,n,1) % MOD);}
}
return 0;
}
树状数组1（单点加，区间问）
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int maxn = 5 * 1e5;
int b[maxn];
void add(int x,int v,int n) {
for (int i = x;i <= n;i += lowbit(i))
b[i] += v;
}
int query(int x) {
int ans = 0;
for (int i = x;i;i -= lowbit(i))
ans += b[i];
return ans;
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1,x;i <= n;i++) {
scanf("%d",&x);
add(i,x,n);
}
for (int i = 1,op,x,y;i <= m;++ i) {
scanf("%d%d%d",&op,&x,&y);
if (op == 1) add(x,y,n);
else printf("%d\n",query(y) - query(x - 1));
}
return 0;
}
树状数组2（单点问，区间加）
#include<bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
#define ll long long
using namespace std;
const int maxn = 500005;
int n,Q; ll a[maxn],b[maxn];
void add(int x,ll v) { for (int i = x;i <= n;i += lowbit(i)) b[i] += v; }
ll query(int x) { ll ans = 0; for (int i = x;i > 0;i -= lowbit(i)) ans += b[i]; return ans; }
int main() {
scanf("%d",&n); scanf("%d",&Q);
for (int i = 1; i <= n;i ++) { scanf("%lld",&a[i]); add(i,a[i] - a[i - 1]); }
for (int i = 1,op,x,y;i <= Q;i ++) {
scanf("%d%d",&op,&x);
if (op == 1) { ll v; scanf("%d%lld",&y,&v); add(x,v); add(y + 1,-v); }
else { printf("%lld\n",query(x)); }
}
return 0;
}
线段树1但是树状数组
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int maxn = 100005;
int a[maxn],d[maxn],s[maxn],t[maxn];
ll b[maxn],c[maxn];
/*
void add(int x,int v,int n) {
for (int i = x;i <= n;i += lowbit(i))
b[i] += v;
}
int query(int x) {
int ans = 0;
for (int i = x;i;i -= lowbit(i))
ans += b[i];
return ans;
}*/
void add(ll x[],int idx,ll k,int n) {
for (int i = idx;i <= n;i += lowbit(i))
x[i] += k;
}
ll query(ll x[],int idx) {
ll ans = 0;
for (int i = idx;i;i -= lowbit(i))
ans += x[i];
return ans;
}
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 ++) d[i] = a[i] - a[i-1];
for (int i = 1;i <= n;i ++) s[i] = s[i-1] + d[i],t[i] = t[i-1] + i * d[i];
for (int i = 1;i <= n;i ++) b[i] = s[i] - s[i - lowbit(i)],c[i] = t[i] - t[i-lowbit(i)];
for (int i = 1,op,x,y;i <= m;i ++) {
scanf("%d",&op);
if (op == 1) {
ll k;
scanf("%d%d%lld",&x,&y,&k);
add(b,x,k,n);
add(b,y+1,-k,n);
add(c,x,x*k,n);
add(c,y+1,-k*(y+1),n);
} else {
scanf("%d%d",&x,&y);
printf("%lld\n",(y + 1) * query(b,y) - query(c,y) - x*query(b,x - 1) + query(c,x - 1));
}
}
return 0;
}
区间问题
最长上升子序列 LIS
#include <iostream>
using namespace std;
#include <cstdio>
const int MaxN = 100001;
int n, i, top = 0, x, stack[MaxN];
int main() {
cin >> n;
stack[top] = -1;
for (i = 1; i <= n; i++) {
cin >> x;
if (x > stack[top]) {
stack[++top] = x;
} else {
int low = 0, high = top, mid;
while (low < high) {
mid = (low + high) >> 1;
if (x > stack[mid])
low = mid + 1;
else
high = mid - 1;
}
stack[low] = x;
}
}
cout << top;
return 0;
}
最长公共子序列 LCS
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.size()][text2.size()];
}
int main() {
string s1;
string s2;
int n;
cin >> n;
while (n--) {
cin >> s1;
cin >> s2;
cout << longestCommonSubsequence(s1, s2) << endl;
}
}
图论最短路
Dijkstra
#include <bits/stdc++.h>
#define MOD 10000000007
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int maxn = 2000005;
int n, m, s;
// idx表示边的序数，e存终点，w存权值，h存表头，next存下一个点（h和next形成了链表）
// idx其实并没有实质性意义，只是用于确定一条边的前驱、后驱和权值(便于调用及确定与其顶点的关系)
int idx, e[maxn], w[maxn], h[maxn], ne[maxn];
int dis[maxn], vis[maxn]; // 距离，标记
struct Node {
int dis, x; // 距离和当前点
// 重载运算符（从小到大排序）
bool operator<(Node p) const {
return dis > p.dis;
}
Node(int dis, int x) : dis(dis), x(x) {}
};
// 快读
inline int read() {
int date = 0, w = 1;
char c;
c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
date = date * 10 + (c - '0');
c = getchar();
}
return date * w;
}
// 邻接表(顶点为表头，后面跟着的都是该顶点为起点的边)
void add(int a, int b, int c) {
e[++idx] = b;
w[idx] = c;
ne[idx] = h[a]; // 同一个起点的边形成邻接表关系
h[a] = idx;
}
void dijkstra() {
memset(dis, INF, sizeof(dis)); // 初始化
priority_queue<Node> q; // 按照结构体中的重载符进行排序（从小到大排序，先将dis小的出队）
dis[s] = 0; // 初始化起点
Node u(dis[s], s);
q.push(u);
while (!q.empty()) {
Node u = q.top();
q.pop();
if (vis[u.x])
continue; // 已标记过的点，即这个点为起点的这条链已走完
vis[u.x] = 1; // 标记
// for(表头;链尾非NULL;链的下一个结点)
for (int i = h[u.x]; i; i = ne[i]) {
if (dis[e[i]] > dis[u.x] + w[i]) {
dis[e[i]] = dis[u.x] + w[i];
Node v(dis[e[i]], e[i]); // dis[终点]，终点（距离起点最近）
q.push(v);
}
}
}
}
int main() {
n = read(), m = read(), s = read();
for (int i = 1; i <= m; i++) {
int a = read(), b = read(), c = read();
add(a, b, c); // 建立邻接表关系（以边为单位）
}
/*for(int i=0; i<=n; i++)
cout<<h[i]<<" "<<e[i]<<" "<<w[i]<<" "<<next[i]<<endl;*/
dijkstra();
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
背包问题
0/1背包
#include <bits/stdc++.h>
using namespace std;
int n, m, v[1001], w[1001], f[1001], g[1001];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
printf("%d\n", f[m]);
}
分组背包
#include <bits/stdc++.h>
using namespace std;
int n, m, v[1001], w[1001], a[1001], f[1001];
vector<int> c[1001];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i], &v[i], &w[i]);
c[a[i]].push_back(i);
}
for (int i = 1; i <= 1000; i++)
for (int j = m; j > 0; j--) {
for (auto k : c[i]) // k是一个下标,枚举选这组里的几种选择
if (v[k] <= j)
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
printf("%d\n", f[m]);
system("pause");
}
完全背包
#include <bits/stdc++.h>
using namespace std;
int n, m, v[1001], w[1001], f[1001], g[1001];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
printf("%d\n", f[m]);
system("pause");
}
混合背包
#include <bits/stdc++.h>
using namespace std;
int n, m, k[10001], v[10001], w[10001], f[10001], l[10001];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
cin >> k[i] >> v[i] >> w[i];
if (k[i] == 3) {
cin >> l[i];
}
}
for (int i = 1; i <= n; i++) {
if (k[i] == 2) { // 完全背包
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
if (k[i] == 1) {
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
} else { // 多重背包和01
int res = l[i];
for (int p = 1; p <= res; res -= p, p *= 2) // 切成l份
for (int j = m; j >= v[i] * p; j--) {
f[j] = max(f[j], f[j - v[i] * p] + w[i] * p);
}
for (int j = m; j >= v[i] * res; j--) // 多出来的，好比8=1+2+4+1，多出来一个1
f[j] = max(f[j], f[j - v[i] * res] + w[i] * res);
}
}
cout << f[m] << "\n";
system("pause");
}
多重背包
// (数学方法：1,2,...,2^m选一些数字相加，可以得出[0,2^(m+1))
#include <bits/stdc++.h>
using namespace std;
int n, m, v[2001], w[2001], f[2001], l[2001];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &v[i], &w[i], &l[i]);
}
for (int i = 1; i <= n; i++) {
int res = l[i];
for (int k = 1; k <= res; res -= k, k *= 2) // 切成l份
for (int j = m; j >= v[i] * k; j--) {
f[j] = max(f[j], f[j - v[i] * k] + w[i] * k);
}
for (int j = m; j >= v[i] * res; j--) // 多出来的，好比8=1+2+4+1，多出来一个1
f[j] = max(f[j], f[j - v[i] * res] + w[i] * res);
}
printf("%d\n", f[m]);
system("pause");
}
二维背包
#include <bits/stdc++.h>
using namespace std;
int n, m, v[1001], w[1001], t[1001], f[101][101], k;
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &v[i], &w[i], &t[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
for (int x = k; x >= t[i]; x--) {
f[j][x] = max(f[j][x], f[j - v[i]][x - t[i]] + w[i]);
}
printf("%d\n", f[m][k]);
system("pause");
}
各种排序
基数排序
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int maxBit(vector<int> vec) {
int max = vec[0];
for (int i = 1; i < vec.size(); i++) {
if (vec[i] > max)
max = vec[i];
}
int p = 1;
while (max / 10 != 0) {
max = max / 10;
p++;
}
return p;
}
vector<int> countSort(vector<int> vec, int place) {
// 按指定位置的值进行计数排序
vector<int> temp(vec); // 临时数组，存储place位置的值
vector<int> ordered(vec); // 排好序的数组放进ordered
int count[10] = {0};
for (int i = 0; i < vec.size(); i++) {
temp[i] = (int)(vec[i] / pow(10, place - 1)) % 10; // 找到每个元素place位置上的数字存在temp中
}
for (int i = 0; i < vec.size(); i++) {
count[temp[i]]++; // 统计数字出现的频率
}
for (int i = 1; i < 10; i++) {
count[i] = count[i] + count[i - 1]; // 此时count中存放着temp中每个数字的索引
}
for (int i = vec.size() - 1; i >= 0; i--) {
int index = count[temp[i]] - 1;
count[temp[i]]--;
ordered[index] = vec[i];
}
// cout << "next:" << endl;
return ordered;
}
void radixSort(vector<int> &vec) {
int maxbit = maxBit(vec); // 最长位数是多少，代表要进行几次排序
for (int i = 1; i <= maxbit; i++) {
// i为多少，代表按第几位数字比较(从右向左)
vec = countSort(vec, i);
}
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
}
int main() {
vector<int> vec {3, 5, 34, 10, 8, 6, 16, 5, 8, 6, 2, 4, 900, 4, 7, 0, 1, 8, 9, 7, 38, 1, 2, 5, 9, 7, 4, 0, 2, 6};
radixSort(vec);
return 0;
}
归并排序
#include <bits/stdc++.h>
using namespace std;
int a[114514], b[114514]; // 必须有
void merge(int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (a[i] < a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= mid)
b[k++] = a[i++];
while (j <= high)
b[k++] = a[j++];
for (int i = low; i <= high; i++)
a[i] = b[i];
}
void mergesort(int x, int y) {
if (x >= y)
return;
int mid = (x + y) / 2;
mergesort(x, mid);
mergesort(mid + 1, y);
merge(x, mid, y);
}
int main() {
return 0;
}
快速排序
#include <bits/stdc++.h>
using namespace std;
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);
}
int main() {
return 0;
}
字符串操作
字符串匹配 KMP
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char q[N], s[M]; // q为模式串(长串),s为模板串(短串)
int ne[N], n, m;
int main() {
cin >> n >> q + 1 >> m >> s + 1; // q,s的下标均从1开始
for (int i = 2, j = 0; i <= n; i++) // j表示匹配成功的长度,i表示q数组中的下标
// 因为q数组的下标是从1开始的,只有1个时,ne[1]一定为0,所以i从2开始
{
while (j && q[i] != q[j + 1])
j = ne[j]; // 如果不行可以换到next数组
if (q[i] == q[j + 1])
j++; // 成功了就加1
ne[i] = j; // 对应其下标
}
// j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != q[j + 1])
j = ne[j];
// 如果匹配不成功,则换到j对应的next数组中的值
if (s[i] == q[j + 1])
j++;
if (j == n) { // 说明已经完全匹配上去了
printf("%d ", i - j);
// 因为题目中的下标从0开始,所以i-j不用+1;
j = ne[j];
// 为了观察其后续是否还能跟S数组后面的数配对成功
}
}
return 0;
}
Trie树
#include <iostream>
using namespace std;
const int N = 100010;
// son[][]存储树中每个节点的子节点，由于这里都是小写字母，所以26个
// cnt[]存储以每个节点结尾的单词数量
// idt表示数组的下标，下标是0的点，既是根节点又是空节点。
int son[N][26], cnt[N], idt;
void insert(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - 'a';
if (!son[p][u])
son[p][u] = ++idt;
p = son[p][u];
}
cnt[p]++;
}
int query(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - 'a';
if (!son[p][u])
return 0;
p = son[p][u];
}
return cnt[p];
}
int main() {
int m;
scanf("%d", &m);
char opt[2];
char str[N];
while (m--) {
scanf("%s%s", opt, str);
if (opt[0] == 'I') {
insert(str);
} else if (opt[0] == 'Q') {
printf("%d\n", query(str));
}
}
return 0;
}
数学运算
三分法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-7; //eps一般设为1e-(精确位数+2)
int n;
double l,r,lmid,rmid;
double num[20];
inline double val(double x) //求f[x]
{
double tmp=1,ans=0; //tmp=x^i
for(int i=0;i<=n;i++)
{
ans+=tmp*num[i];
tmp*=x;
}
return ans;
}
inline void sanfen() {
while(r-l>eps)
{
lmid=l+(r-l)/3;
rmid=r-(r-l)/3;
if(val(lmid)<val(rmid)) l=lmid;
else r=rmid;
}
}
int main()
{
scanf("%d%lf%lf",&n,&l,&r);
for(int i=n;i>=0;i--) scanf("%lf",&num[i]);
sanfen();
printf("%.5f\n",l);
return 0;
}
高斯消元法
#include<bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
void fun(vector<vector<double> > & mat) {
int n = mat.size(), m = mat[0].size() - 1;
for (int col = 0, row = 0; col < m && row < n;col ++) {
int pivot_row = row;
for (int i = row + 1;i < n;i ++)
if (abs(mat[i][col]) > abs(mat[pivot_row][col]))
pivot_row = i;
if (abs(mat[pivot_row][col]) < EPS)
continue;
if (pivot_row != row) swap(mat[row],mat[pivot_row]);
for (int i = 0;i < n;i ++)
if (i != row) {
double factor = mat[row],mat[pivot_row];
for (int j = col;j <= m;j ++)
mat[i][j] -= factor * mat[row][j];
}
double divisor = mat[row][col];
for (int j = col;j <= m;j ++)
mat[row][j] /= divisor;
++ row;
}
}
int main() {
vector<vector<double> > mat = {
{ 1, 2, 1, 7 },
{ 3, -1, 2, 1 },
{ 2, -1, 3, 5 }
};
fun();
for (int i = 0;i < mat.size();i ++)
cout << "x" << i + 1 << "=" << mat[i].
return 0;
}
排列组合
void init() {
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (ll i = (ll)2; i < (ll)maxn; i++) {
fac[i] = fac[i - 1] * i % p;
inv[i] = (p - p / i) * inv[p % i] % p;
}
for (ll i = (ll)2; i < (ll)maxn; i++) {
inv[i] = inv[i] * inv[i - 1] % p;
}
}
__int128 C(int n, int m) {
if (m > n) return 0;
return fac[n] * inv[m] % p * inv[n - m] % p;
}
线性筛欧拉函数
phi[1] = 1;
for (int i = 2;i <= n;i ++) {
if (!vis[i]) {
p[++ cnt] = i;
phi[i] = i - 1;
}
for (int j = 1;i * p[j] <= n && j <= cnt;j ++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j];
break;
} else phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
线性筛逆元
inv[1] = 1;
for (int i = 2;i <= n;i ++) {
if (!vis[i]) {
p[++ cnt] = i;
inv[i] = pow(i,P - 2);
}
for (int j = 1;i * p[j] <= n && j <= cnt;j ++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) {
inv[i * p[j]] = inv[i] * inv[p[j]];
break;
} else inv[i * p[j]] = inv[i] * inv[p[j]];
}
}
线性筛因数个数
cnt[1] = 1, mincnt[1] = 0;
for (int i = 2;i <= n;i ++) {
if (!vis[i]) {
p[++ cnt] = i;
cnt[i] = 2, mincnt[i] = 1;
}
for (int j = 1;i * p[j] <= n && j <= cnt;j ++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) {
cnt[i * p[j]] = cnt[i] * (mincnt[i] + 2) / (mincnt[i] + 1);
mincnt[i * p[j]] = mincnt[i] = 1;
break;
} else {
cnt[i * p[j]] = cnt[i] * cnt[p[j]];
mincnt[i * p[j]] = 1;
}
}
}
线性筛因子之和
sum[1] = 1;
for (int i = 2;i <= n;i ++) {
if (!vis[i]) {
p[++ cnt] = i;
sum[i] = i + 1, mincnt[i] = i + 1;
}
for (int j = 1;i * p[j] <= n && j <= cnt;j ++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) {
sum[i * [j]] = sum[i] * (1 + p[j] * minsum[i]) / minsum[i];
minsum[i * p[j]] = minsum[i] * p[j] + 1;
break;
} else {
sum[i * p[j]] = cnt[i] * cnt[p[j]];
minsum[i * p[j]] = p[j] + 1;
}
}
}
线性筛
bool vis[maxn]; int p[maxn];
void fun() {
for (int i = 2;i <= n;i ++) {
if (!a[i]) p[++ cnt] = i;
for (int j = 1;i * p[j] <= n && j <= cnt;j ++) {
vis[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}
}
- 复杂度 O(n)
- a 范围之内的质数个数级别约为 \frac{a}{\log a}
分解质因数
// 目标为n，分解完后为a[]，指数为c[]，个数为tot
int a[maxn], c[maxn];
int fun(int n) {
int tot = 0;
for (ll i = 2;i * i <= n;i ++)
if (!(n % i) {
a[++ tot] = i;
while (!(n % i)) c[tot] ++, n /= i;
}
if (n > 1) a[++ tot] = n, c[tot] = 1;
return tot;
}
快速幂
long quick_pow(int a, int b) {
long x = a;
long res = 1;
while (b > 0) {
if (b & 1)
res *= x;
b >>= 1; // 右移一位
x = x * x;
}
return res;
}
gcd & lcm
int gcd(int x,int y) { return !y ? x : gcd(y, x % y); }
int lcm(int x,int y) { return x * y / gcd(x,y); }
扩展欧几里得 exgcd
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,a,b,k;
//快读
inline int read(){
register int x = 0, t = 1;
register char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
t=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*t;
}
//快写
inline void write(int x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
void exgcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}
signed main()
{
a=read(),b=read();
exgcd(a,b);
cout<<(x+b)%b;
return 0;
}
文件
freopen
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a, b;
freopen("D:\\in.txt", "r", stdin); //输入重定向，输入数据将从D盘根目录下的in.txt文件中读取
freopen("D:\\out.txt", "w", stdout); //输出重定向，输出数据将保存在D盘根目录下的out.txt文件中
cin >> a >> b;
cout << a + b << endl; // 注意使用endl
fclose(stdin);//关闭重定向输入
fclose(stdout);//关闭重定向输出
return 0;
}