【小结】简单的板子
持续更新中~
索引
1 快读快写
1.0 快读快写
2 数据结构
2.0 堆
2.0.0 二叉堆
2.0.1 左偏树
2.1 线段树
2.2 树状数组
2.3 st表
2.4 单调栈
2.5 单调队列
2.6 可持久化数据结构2.6.0 可持久化数组
2.6.1 可持久化线段树
3 图
3.0 图的遍历
3.0.0 图的深度优先遍历
3.0.1 图的广度优先遍历
3.1 最短路
3.1.0 floyd
3.1.1 spfa
3.1.2 dijkstra（堆优化）
3.2 图的连通性
3.2.0 割点
3.2.1 割边
3.2.2 点双连通分量
3.2.3 边双连通分量
3.2.4 强联通分量
3.3 图匹配
3.3.0 二分图最大匹配-匈牙利算法
3.4 网络流
3.4.0 网络最大流-Edmonds-Karp 算法
3.5 图（其他）
3.5.0 拓扑排序
3.5.1 差分约束
4 树
4.0 并查集
4.1 最小生成树
4.2 树链剖分4.3 重链剖分
5 动态规划
5.0 背包
5.0.0 01背包
5.0.1 完全背包
5.0.2 多重背包（二进制优化）
5.1 线性dp
5.1.0 最长上升子序列（优化）
5.1.1 最长公共子序列
5.2 区间dp
5.3 树形dp
6 高精度
6.0 高精乘
6.0.1 高精除单精
7 数学
7.0 快速幂
7.1 线性筛素数
7.2 乘法逆元
7.3 矩阵相关7.3.0 矩阵乘法
7.3.1 矩阵快速幂
8 字符串
8.0 字符串哈希
8.1 字典树
8.2 KMP 算法
快读快写：
#include<bits/stdc++.h>
using namespace std;
int n;
inline int read(){
int w=1,q=0;
char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return w*q;
}
void write(int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
int main(){
int n;
n=read();
return 0;
}
数据结构：
堆：
二叉堆：
#include <bits/stdc++.h>
using namespace std;
struct HeapBig
{
int value[100005];
int cnt;
bool empty()
{
return cnt == 0;
}
int size()
{
return cnt;
}
int top()
{
return value[1];
}
void shiftup(int k)
{
while(k > 1)
{
if(value[k] > value[k/2])
{
swap(value[k], value[k/2]);
k /= 2;
}
else break;
}
}
void shiftdown(int k)
{
while(2 * k <= cnt)
{
int tmp = k;
if(value[tmp] < value[2*k]) tmp = 2 * k;
if(2 * k + 1 <= cnt && value[tmp] < value[2*k+1]) tmp = 2 * k + 1;
if(tmp == k) break;
swap(value[k], value[tmp]);
k = tmp;
}
}
void push(int x)
{
value[++cnt] = x;
shiftup(cnt);
}
void pop()
{
value[1] = value[cnt];
cnt--;
shiftdown(1);
}
void print()
{
for(int i = 1; i <= cnt; i++)
cout << value[i] << " ";
cout << endl;
}
};
HeapBig q;
int main()
{
}
左偏树：
#### 可并堆：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
namespace Leftist_tree {
int fa[N];
bool vis[N];
struct node {
int v;
int ls, rs;
int dist;
}t[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (t[x].v > t[y].v) swap(x, y);
t[x].rs = merge(t[x].rs, y);
if (t[t[x].rs].dist > t[t[x].ls].dist) swap(t[x].rs, t[x].ls);
t[x].dist = t[t[x].rs].dist + 1;
return x;
}
}
using namespace Leftist_tree;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), std::cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> t[i].v, fa[i] = i;
while (m--) {
int op, x, y;
cin >> op >> x;
if (op == 1) {
cin >> y;
if (vis[x] || vis[y] || find(x) == find(y)) continue;
fa[find(x)] = fa[find(y)] = merge(find(x), find(y));
}
else {
if (vis[x]) cout << "-1\n";
else {
x = find(x), vis[x] = true, cout << t[x].v << "\n";
fa[x] = fa[t[x].ls] = fa[t[x].rs] = merge(t[x].ls, t[x].rs);
}
}
}
return 0;
}
#### 线段树：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m;
int a[N],t[N<<2];
int lazy[N<<2];
void pushup(int x){
t[x]=t[x<<1]+t[x<<1|1];
}
void f(int k,int v,int l,int r){
lazy[k]+=v;
t[k]+=(r-l+1)*v;
}
void pushdown(int k,int l,int r){
int m=l+((r-l)>>1);
f(k<<1,lazy[k],l,m);
f(k<<1|1,lazy[k],m+1,r);
lazy[k]=0;
}
void build(int k,int l,int r){
if(l==r)t[k]=a[l];
else{
int m=l+((r-l)>>1);
build(k<<1,l,m);
build(k<<1|1,m+1,r);
pushup(k);
}
}
void updata(int v,int k,int l,int r,int L,int R){
if(l>=L&&r<=R)f(k,v,l,r);
else{
pushdown(k,l,r);
int m=l+((r-l)>>1);
if(L<=m)updata(v,k<<1,l,m,L,R);
if(R>m)updata(v,k<<1|1,m+1,r,L,R);
pushup(k);
}
}
int query(int k,int l,int r,int L,int R){
if(l>=L&&r<=R)return t[k];
else{
int res=0;
pushdown(k,l,r);
int m=l+((r-l)>>1);
if(L<=m)res+=query(k<<1,l,m,L,R);
if(R>m)res+=query(k<<1|1,m+1,r,L,R);
return res;
}
}
signed main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--){
int op,l,r,x;
cin>>op>>l>>r;
if(op==1){
cin>>x;
updata(x,1,1,n,l,r);
}
else cout<<query(1,1,n,l,r)<<endl;
}
return 0;
}
树状数组：
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, m;
int c[N];
int lowbit(int x){return x & -x;}
void add(int u, int v)
{
for (int i = u; i <= n; i += lowbit(i))
c[i] += v;
return;
}
int sum(int x)
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i))
res += c[i];
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
add(i, x);
}
while (m--)
{
int op, x, y;
cin >> op >> x >> y;
if (op == 1) add(x, y);
else cout << sum(y) - sum(x - 1) << endl;
}
return 0;
}
st表：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], f[N][30];
inline int read()
{
int w = 1,q = 0;
char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
return w * q;
}
void write(int x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
int main()
{
int n, m;
n = read(); m = read();
for (int i = 1; i <= n; i++)
a[i] = read(), f[i][0] = a[i];
for (int j = 1; j <= 21; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
while (m--)
{
int x, y;
x = read(); y = read();
int k = log2(y - x + 1);
write(max(f[x][k], f[y - (1 << k) + 1][k]));
printf("\n");
}
return 0;
}
单调栈：
#include <bits/stdc++.h>
using namespace std;
const int N = 3000005;
int a[N], f[N];
stack<int>p;
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n; i >= 1; i--)
{
while (!p.empty() && a[p.top()] <= a[i]) p.pop();
if (!p.empty()) f[i] = p.top();
else f[i] = 0;
p.push(i);
}
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
return 0;
}
单调队列：
#include <bits/stdc++.h>
using namespace std;
namespace happy_zero
{
const int N = 1000005;
int a[N];
deque<int>p, q;
int f1[N], f2[N];
void main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (!p.empty() && p.front() < i - k + 1) p.pop_front();
while (!p.empty() && a[p.back()] <= a[i]) p.pop_back();
p.push_back(i);
f1[i] = a[p.front()];
while (!q.empty() && q.front() < i - k + 1) q.pop_front();
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
f2[i] = a[q.front()];
}
for (int i = k; i <= n; i++) cout << f2[i] << " ";
cout << endl;
for (int i = k; i <= n; i++) cout << f1[i] << " ";
}
}
int main()
{
happy_zero::main();
return 0;
}
可持久化数据结构
可持久化数组
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node
{
int l, r;
int v;
}t[N << 5];
int n, m, a[N];
int tree[N];
int cnt = 0;
int build(int l, int r)
{
int k = ++cnt;
if (l == r)
{
t[k].v = a[l];
return k;
}
int m = l + ((r - l) >> 1);
t[k].l = build(l, m);
t[k].r = build(m + 1, r);
return k;
}
int updata(int lst, int l, int r, int x, int v)
{
int k = ++cnt;
if (l == r)
{
t[k].v = v;
return k;
}
t[k] = t[lst];
int m = l + ((r - l) >> 1);
if (x <= m) t[k].l = updata(t[k].l, l, m, x, v);
else t[k].r = updata(t[k].r, m + 1, r, x, v);
return k;
}
int query(int k, int l, int r, int x)
{
if (l == r) return t[k].v;
int m = l + ((r - l) >> 1);
if (x <= m) return query(t[k].l, l, m, x);
else return query(t[k].r, m + 1, r, x);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
tree[0] = build(1, n);
int V = 0;
for (int i = 1; i <= m; i++)
{
int op, v, x, y;
scanf("%d%d%d", &v, &op, &x);
if (op == 1)
scanf("%d", &y), tree[i] = updata(tree[v], 1, n, x, y);
else
tree[i] = tree[v], cout << query(tree[v], 1, n, x) << "\n";
}
return 0;
}
可持久化线段树
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node
{
int l;
int r;
int v;
}t[N << 8];
int cnt;
int a[N], b[N];
int tree[N];
void pushup(int k)
{
t[k].v = t[t[k].l].v + t[t[k].r].v;
}
int build(int l, int r)
{
int k = ++cnt;
t[k].v = 0;
if (l == r) return k;
int m = l + ((r - l) >> 1);
t[k].l = build(l, m);
t[k].r = build(m + 1, r);
return k;
}
int updata(int lst, int l, int r, int o)
{
int k = ++cnt;
t[k] = t[lst];
if (l == r)
{
t[k].v++;
return k;
}
int m = l + ((r - l) >> 1);
if (o <= m) t[k].l = updata(t[lst].l, l, m, o);
else t[k].r = updata(t[lst].r, m + 1, r, o);
pushup(k);
return k;
}
int query(int o1, int o2, int l, int r, int pls)
{
if (l == r) return l;
int tmp = t[t[o2].l].v - t[t[o1].l].v;
int m = l + ((r - l) >> 1);
if (tmp < pls) return query(t[o1].r, t[o2].r, m + 1, r, pls - tmp);
return query(t[o1].l, t[o2].l, l, m, pls);
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];
sort(b + 1, b + 1 + n);
int len = unique(b + 1, b + 1 + n) - b - 1;
tree[0] = build(1, len);
for (int i = 1; i <= n; i++)
{
int tx = lower_bound(b + 1, b + 1 + len, a[i]) - b;
tree[i] = updata(tree[i - 1], 1, len, tx);
}
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
cout << b[query(tree[l - 1], tree[r], 1, len, k)] << "\n";
}
return 0;
}
图
图的遍历：
图的深度优先遍历：
#include<bits/stdc++.h>
using namespace std;
int vis[105],s;
vector<int>v[105];
bool dfs(int u){
vis[u]=1;
for(int i=0;i<v[u].size();i++){
if(v[u][i]==s)return 1;
if(vis[v[u][i]]==0)dfs(v[u][i]);
}
}
int main(){
int n,m;
int a,b,c;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;
v[a].push_back(b);
}
cin>>s;
if(dfs(s)==1)cout<<"yes";
else cout<<"no";
return 0;
}
图的广度优先遍历：
#include<bits/stdc++.h>
using namespace std;
int vis[105],s;
vector<int>v[105];
queue<int>q;
void dfs(){
s=1;
q.push(s);
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
cout<<u<<endl;
for(int i=0;i<v[u].size();i++){
int t=v[u][i];
if(!vis[t]){
q.push(t);
vis[t]=1;
}
}
}
}
int main(){
int n,m;
int a,b,c;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;
v[a].push_back(b);
}
dfs();
return 0;
}
最短路：
floyd:
#include<bits/stdc++.h>
using namespace std;
int n,m,sum;
int a[100];
int dist[100][100];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=1e9;
for(int i=1;i<=m;i++){
int x,y,op;
cin>>x>>y>>op;
dist[x][y]=1;
dist[y][x]=1;
}
for(int i=1;i<=n;i++)
dist[i][i]=0;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum+=dist[i][j]+a[j];
cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
}
}
return 0;
}
spfa:
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch == '-') f=-1;
ch = getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
int n,m,cnt,s;
struct node{
int to;
int next;
int w;
}e[5000005];
int head[100005];
int dist[100005];
queue<int>q;
bool vis[100005] ;
void add(int a,int b,int c){
e[++cnt].to=b;
e[cnt].w=c;
e[cnt].next=head[a];
head[a]=cnt;
}
void spfa(int u){
q.push(u);
for(int i=1;i<=n;i++)
dist[i]=1e9;
dist[u]=0;
vis[u]=true;
while(!q.empty()) {
int t=q.front();
q.pop();
vis[t]=false;
for(int i=head[t];i;i=e[i].next){
int tx=e[i].to,val=e[i].w;
if(dist[t]+val<dist[tx]){
dist[tx]=dist[t]+val;
if(!vis[tx]){
q.push(tx);
vis[tx]=true;
}
}
}
}
return;
}
signed main(){
n=read();m=read();s=read();
for(int i=1;i<=m;i++){
int a,b,c;
a=read();b=read();c=read();
add(a,b,c);
}
spfa(s);
for(int i=1;i<=n;i++){
write(dist[i]);
printf(" ");
}
}
dijkstra(堆优化):
#include <bits/stdc++.h>
#define pii pair <int, int>
using namespace std;
const int N = 1e4 + 5;
struct node
{
int tx;
int s;
};
int n, m;
int dis[N];
bool vis[N];
vector <node> p[N];
bool operator <(node x, node y)
{
return x.s > y.s;
}
priority_queue <node> q;
void dijkstra(int u)
{
for (int i = 1; i <= n; i++)
dis[i] = 1e9;
dis[u] = 0;
q.push({u, 0});
while (!q.empty())
{
int tx = q.top().tx;
q.pop();
if (vis[tx]) continue;
vis[tx] = true;
for (int i = 0; i < p[tx].size(); i++)
{
int k = p[tx][i].tx;
if (dis[k] > dis[tx] + p[tx][i].s)
{
dis[k] = dis[tx] + p[tx][i].s;
q.push({k, dis[k]});
}
}
}
}
int main()
{
freopen("dijkstra.in", "r", stdin);
freopen("dijkstra.out", "w", stdout);
int s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
p[x].push_back({y, z});
p[y].push_back({x, z});
}
dijkstra(s);
for (int i = 1; i <= n; i++)
{
if (dis[i] == 1e9) dis[i] = -1;
cout << dis[i] << endl;
}
return 0;
}
无向图的连通性
割点：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
const int M = 1e5 + 5;
int n, m, s, ans;
int dfn[N], low[N];
bool flag[N];
vector <int> p[N];
void tarjan(int k, int rt)
{
int cnt = 0;
dfn[k] = low[k] = ++s;
for (auto i : p[k])
{
if (!dfn[i])
{
cnt++;
tarjan(i, rt);
low[k] = min(low[k], low[i]);
if (k != rt && low[i] >= dfn[k])
{
if (!flag[k]) ans++;
flag[k] = true;
}
}
else low[k] = min(low[k], dfn[i]);
}
if (k == rt && cnt > 1)
{
if (!flag[k]) ans++;
flag[k] = true;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, i);
cout << ans << "\n";
for (int i = 1; i <= n; i++)
if (flag[i]) cout << i << " ";
return 0;
}
割边：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct node
{
int nxt;
int to;
}e[N];
int n, m, ecnt = 1;
int ans, s;
int head[N];
int dfn[N], low[N], bri[N];
bool vis[N];
void add(int u, int v)
{
e[++ecnt] = {head[u], v};
head[u] = ecnt;
}
void tarjan(int k)
{
dfn[k] = low[k] = ++s;
int cnt = 0;
for (int i = head[k]; i; i = e[i].nxt)
{
if (vis[i]) continue;
int v = e[i].to;
vis[i] = vis[i ^ 1] = true;
if (!dfn[v])
{
tarjan(v);
cnt++;
low[k] = min(low[k], low[v]);
if (low[v] > dfn[k])
bri[++ans] = i / 2;
}
else low[k] = min(low[k], dfn[v]);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
sort(bri + 1, bri + ans + 1);
for (int i = 1; i <= ans; i++)
cout << bri[i] << " ";
return 0;
}
点双连通分量
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, s, cnt, rt;
int dfn[N], low[N];
vector <int> p[N], ans[N];
stack <int> q;
void tarjan(int k)
{
q.push(k);
dfn[k] = low[k] = ++s;
int sum = 0;
for (auto i : p[k])
{
if (!dfn[i])
{
sum++;
tarjan(i);
low[k] = min(low[k], low[i]);
if (low[i] >= dfn[k])
{
cnt++;
int t;
do
{
t = q.top();
ans[cnt].push_back(q.top());
q.pop();
}while (t != i);
ans[cnt].push_back(k);
}
}
else low[k] = min(low[k], dfn[i]);
}
if (k == rt && sum == 0) ans[++cnt].push_back(k);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) rt = i, tarjan(i);
cout << cnt << endl;
for (int i = 1; i <= cnt; i++)
{
cout << ans[i].size() << " ";
for (auto j : ans[i])
cout << j << " ";
cout << "\n";
}
return 0;
}
边双连通分量：
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 5e5 + 5;
const int M = 5e6 + 5;
struct node
{
int to;
int nxt;
}e[M];
int n, m, rt;
int ecnt = 1, s, sum;
int head[N], dfn[N], low[N];
bool bri[M], vis[M];
vector <int> ans[N];
void add(int x, int y)
{
e[++ecnt] = {y, head[x]};
head[x] = ecnt;
}
void tarjan(int k)
{
int cnt = 0;
dfn[k] = low[k] = ++s;
for (int i = head[k]; i; i = e[i].nxt)
{
if (vis[i]) continue;
vis[i] = vis[i ^ 1] = true;
if (!dfn[e[i].to])
{
tarjan(e[i].to);
low[k] = min(low[k], low[e[i].to]);
if (low[e[i].to] > dfn[k])
bri[i] = bri[i ^ 1] = true;
}
else low[k] = min(low[k], dfn[e[i].to]);
}
}
void dfs(int k)
{
//cout << k << endl;
ans[sum].push_back(k);
vis[k] = true;
for (int i = head[k]; i; i = e[i].nxt)
{
if (bri[i]) continue;
int v = e[i].to;
if (!vis[v]) dfs(v);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++)
if (!vis[i]) sum++, dfs(i);
cout << sum << endl;
for (int i = 1; i <= sum; i++)
{
cout << ans[i].size() << " ";
for (auto j : ans[i])
cout << j << " ";
cout << endl;
}
return 0;
}
强联通分量
const int N = 1e4 + 5;
int ts, low[N], dfn[N], cnt, co[N];
bool vis[N];
vector <int> p[N];
stack <int> q;
void tarjan(int k) {
low[k] = dfn[k] = ++ts;
q.push(k), vis[k] = true;
for (auto i : p[k]) {
if (!dfn[i]) tarjan(i), low[k] = min(low[k], low[i]);
else if (vis[i]) low[k] = min(low[k], dfn[i]);
}
if (low[k] == dfn[k]) {
int t; cnt++;
do {
t = q.top(), q.pop();
co[t] = cnt, vis[t] = false;
}while (t != k);
}
}
图匹配：
二分图最大匹配-匈牙利算法：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int ans = 0;
vector <int> p[N];
int b[N];
bool vis[N];
bool dfs(int k)
{
vis[k] = true;
int j = -1;
for (auto i : p[k])
{
if (b[i] == 0)
{
j = i;
break;
}
}
if (j != -1)
{
b[j] = k;
return 1;
}
for (auto i : p[k])
{
if (!vis[b[i]] && dfs(b[i]))
{
b[i] = k;
return 1;
}
}
return 0;
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= q; i++)
{
int u, v;
cin >> u >> v;
p[u].push_back(v);
}
for (int i = 1; i <= n; i++)
sort(p[i].begin(), p[i].end());
for (int i = 1; i <= n; i++)
{
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
cout << ans << endl;
return 0;
}
网络流：
网络最大流-Edmonds-Karp 算法
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 35;
const int M = 405;
const int INF = 1000000000000;
int n, m, p[N][N];
int flow[N], pre[N];
int bfs(int s, int t)
{
memset(flow, 0, sizeof(flow));
memset(pre, -1, sizeof(pre));
queue <int> q;
q.push(s);
flow[s] = INF, pre[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == t) break;
for (int i = 1; i <= n; i++)
{
if (p[u][i] == 0) continue;
if (pre[i] == -1)
{
pre[i] = u;
q.push(i);
flow[i] = min(flow[u], p[u][i]);
}
}
}
if (pre[t] == -1) return -1;
return flow[t];
}
int maxflow(int s, int t)
{
int res = 0;
while (1)
{
int mflow = bfs(s, t);
if (mflow == -1) return res;
int lst = t;
while (lst != s)
{
p[pre[lst]][lst] -= mflow;
p[lst][pre[lst]] += mflow;
lst = pre[lst];
}
res += mflow;
}
}
signed main()
{
int s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++)
{
int u, v, c;
cin >> u >> v >> c;
p[u][v] += c;
}
cout << maxflow(s, t) << endl;
return 0;
}
图（其他）：
拓扑排序：
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int into[10005];
vector<int>p[10005];
queue<int>q;
queue<int>ans;
void tp(){
for(int i=1;i<=n;i++){
if(into[i]==0)q.push(i);
}
while(!q.empty()){
int t=q.front();
q.pop();
ans.push(t);
for(int i=0;i<p[t].size();i++){
int to=p[t][i];
into[to]--;
if(into[to]==0)q.push(to);
}
}
if(ans.size()<n){
cout<<-1;
return;
}
for(int i=1;i<=n;i++){
cout<<ans.front()<<endl;
ans.pop();
}
return;
}
int main(){
cin>>n;
while(cin>>a>>b){
p[a].push_back(b);
into[b]++;
}
tp();
return 0;
}
差分约束：
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
const int INF = 1e9;
struct node{
int from;
int to;
int val;
}p[N];
int n, m;
int dist[N];
bool bell()
{
for (int i = 2; i <= n; i++)
dist[i] = INF;
for (int i = 1; i <= n; i++)
{
bool flag = false;
for (int j = 1; j <= m; j++)
{
int u = p[j].from;
int v = p[j].to;
int t = p[j].val;
if (dist[v] > dist[u] + t)
{
dist[v] = dist[u] + t;
flag = true;
}
}
if (!flag) return 0;
if (i == n && flag == true) return 1;
}
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, v;
cin >> x >> y >> v;
p[i] = (node){y, x, v};
}
if(bell())cout << "NO" << endl;
else
{
for (int i = 1; i <= n; i++)
cout << dist[i] << " ";
}
return 0;
}
树：
并查集：
#include<bits/stdc++.h>
using namespace std;
int fa[100005],n,m,cnt[100005];
int find(int x){
if(x==fa[x])return x;
else return fa[x]=find(fa[x]);
}
void combine(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
if(cnt[x]<cnt[y])fa[fx]=fa[fy];
else fa[fy]=fa[fx],cnt[fx]++;
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
int z,a,b;
cin>>a>>b;
combine(a,b);
}
for(int i=1;i<=n;i++)
cout<<find(i)<<endl;
return 0;
}
最小生成树：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt,k,num,ans;
int fa[500005];
struct node{
int from;
int to;
int val;
}v[2000005];
bool cmp(node x,node y){
return x.val<y.val;
}
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
bool combine(int x,int y){
int tx=find(x),ty=find(y);
if(tx==ty)return 1;
fa[ty]=tx;
return 0;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
v[i].from=a;v[i].to=b;v[i].val=c;
}
if(m<n-1){
cout<<"orz";return 0;
}
for(int i=1;i<=n;i++)
fa[i]=i;
sort(v+1,v+1+m,cmp);
for(int i=1;i<=m;i++){
if(combine(v[i].to,v[i].from)==0){
k++;
ans+=v[i].val;
}
if(k==n-1)break;
}
if(k==n-1)cout<<ans<<endl;
else cout<<"orz"<<endl;
return 0;
}
树链剖分：
重链剖分：
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define pb push_back
using namespace std;
const int N = 1e5 + 5;
int n, m, rt, Mod, w[N], a[N];
vector <int> p[N];
namespace Segment_tree {
int t[N << 4], lazy[N << 4];
void pushup(int k) {
t[k] = t[k << 1] + t[k << 1 | 1];
t[k] %= Mod;
}
void f(int k, int l, int r, int v) {
lazy[k] += v, lazy[k] %= Mod;
t[k] += (r - l + 1) * v % Mod, t[k] %= Mod;
}
void pushdown(int k, int l, int r) {
if (!lazy[k]) return;
int m = l + ((r - l) >> 1);
f(k << 1, l, m, lazy[k]);
f(k << 1 | 1, m + 1, r, lazy[k]);
lazy[k] = 0;
}
void build(int k, int l, int r) {
if (l == r) {
t[k] = a[l];
return;
}
int m = l + ((r - l) >> 1);
build(k << 1, l, m);
build(k << 1 | 1, m + 1, r);
pushup(k);
}
void updata(int k, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) return f(k, l, r, v);
pushdown(k, l, r);
int m = l + ((r - l) >> 1);
if (L <= m) updata(k << 1, l, m, L, R, v);
if (R > m) updata(k << 1 | 1, m + 1, r, L, R, v);
pushup(k);
}
int query(int k, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[k];
pushdown(k, l, r);
int m = l + ((r - l) >> 1), res = 0;
if (L <= m) res += query(k << 1, l, m, L, R);
if (R > m) res += query(k << 1 | 1, m + 1, r, L, R);
return res % Mod;
}
}
namespace Tree_decomposition {
int d[N], siz[N], hson[N], top[N], dfn[N], r[N], f[N], ts;
void dfs1(int k, int fa) {
d[k] = d[fa] + 1, siz[k] = 1, f[k] = fa;
for (auto i : p[k]) {
if (i == fa) continue;
dfs1(i, k), siz[k] += siz[i];
if (siz[i] > siz[hson[k]]) hson[k] = i;
}
}
void dfs2(int k, int fa, int tp) {
top[k] = tp, dfn[k] = ++ts, a[ts] = w[k];
if (hson[k]) dfs2(hson[k], k, tp);
for (auto j : p[k])
if (j != hson[k] && j != fa) dfs2(j, k, j);
r[k] = ts;
}
void tree_updata(int k, int v) {Segment_tree::updata(1, 1, n, dfn[k], r[k], v);}
int tree_query(int k) {return Segment_tree::query(1, 1, n, dfn[k], r[k]) % Mod;}
void path_updata(int x, int y, int v) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
Segment_tree::updata(1, 1, n, dfn[top[x]], dfn[x], v);
x = f[top[x]];
}
if (d[x] < d[y]) swap(x, y);
Segment_tree::updata(1, 1, n, dfn[y], dfn[x], v);
}
int path_query(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
res += Segment_tree::query(1, 1, n, dfn[top[x]], dfn[x]);
res %= Mod, x = f[top[x]];
}
if (d[x] < d[y]) swap(x, y);
res += Segment_tree::query(1, 1, n, dfn[y], dfn[x]);
return res % Mod;
}
}
void init() {
Tree_decomposition::dfs1(rt, 0);
Tree_decomposition::dfs2(rt, 0, rt);
Segment_tree::build(1, 1, n);
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
cin >> n >> m >> rt >> Mod;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 1, x, y; i < n; i++)
cin >> x >> y, p[x].pb(y), p[y].pb(x);
init();
while (m--) {
int op, x, y, z;
cin >> op;
if (op == 1) cin >> x >> y >> z, z %= Mod, Tree_decomposition::path_updata(x, y, z);
if (op == 2) cin >> x >> y, cout << Tree_decomposition::path_query(x, y) << endl;
if (op == 3) cin >> x >> y, y %= Mod, Tree_decomposition::tree_updata(x, y);
if (op == 4) cin >> x, cout << Tree_decomposition::tree_query(x) << endl;
}
return 0;
}
动态规划：
背包：
01背包：
#include<bits/stdc++.h>
using namespace std;
int m,n;
int p[10005],t[10005];
int dp[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>p[i]>>t[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=t[i];j++)
dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
}
cout<<dp[m]<<endl;
return 0;
}
完全背包：
#include<bits/stdc++.h>
using namespace std;
int m,n;
int p[10005],t[10005];
int dp[100005];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>p[i]>>t[i];
for(int i=1;i<=n;i++){
for(int j=t[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-t[i]]+p[i]);
}
cout<<dp[m]<<endl;
return 0;
}
多重背包（二进制优化）：
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int w[100005],v[100005];
int dp[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
if(c==0)c=1000000;
for(int j=1;j<=c;j*=2){
w[++cnt]=a*j;
v[cnt]=b*j;
c=c-j;
}
if(c>0){
w[++cnt]=a*c;
v[cnt]=b*c;
}
}
for(int i=1;i<=cnt;i++){
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
cout<<dp[m]<<endl;
return 0;
}
线性dp:
最长上升子序列（优化）：
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
int flag[1000005];
int b[1000005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
flag[x]=i;
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i]=flag[x];
}
for(int i=1;i<=n;i++){
if(a[i]>b[k]){
b[++k]=a[i];
continue;
}
int low=1,high=k,mid,ans=0;
while(low<=high){
mid=(low+high)/2;
if(a[i]>b[mid]){
ans=mid;
low=mid+1;
}
else high=mid-1;
}
b[ans+1]=a[i];
}
cout<<k;
return 0;
}
最长公共子序列：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
char a[1005],b[1005];
int dp[1005][1005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=m;j++)
cin>>b[j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
cout<<dp[n][m];
return 0;
}
区间dp:
#include<iostream>
using namespace std;
long long n,ansi=1e9,ansa;
long long a[1005],sum[1005];
long long fmin[1005][1005],fmax[1005][1005];
void read(long long &x){
int f=1;x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int main(){
read(n);
for(register int i=1;i<=n;i++){
read(a[i]);
a[i+n]=a[i];
}
for(register int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+a[i];
fmin[i][i]=0;
fmax[i][i]=0;
}
for(register int len=2;len<=n;len++){
for(register int i=1;i<=2*n-len+1;i++){
int last=i+len-1;
fmin[i][last]=1e9;
fmax[i][last]=0;
for(register int k=i;k<last;k++){
fmin[i][last]=min(fmin[i][k]+fmin[k+1][last]+sum[last]-sum[i-1],fmin[i][last]);
fmax[i][last]=max(fmax[i][last],fmax[i][k]+fmax[k+1][last]+sum[last]-sum[i-1]);
}
}
}
for(register int i=1;i<=n;i++){
ansi=min(ansi,fmin[i][i+n-1]);
ansa=max(ansa,fmax[i][i+n-1]);
}
cout<<ansi<<"\n"<<ansa;
return 0;
}
树形dp:
#include<bits/stdc++.h>
using namespace std;
int n,root;
int into[6005];
int a[6005];
int dp[6005][2];
vector<int>p[6005];
void dfs(int x){
dp[x][1]=a[x];
for(int i=0;i<p[x].size();i++){
int y=p[x][i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][1],dp[y][0]);
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
p[b].push_back(a);
into[a]++;
}
for(int i=1;i<=n;i++){
if(into[i]==0){
root=i;
break;
}
}
dfs(root);
cout<<max(dp[root][0],dp[root][1]);
return 0;
}
高精度：
高精乘：
#include<bits/stdc++.h>
using namespace std;
int n,m,len;
char s1[4005],s2[4005];
int a[4005],b[4005];
int ans[4005];
int main (){
cin>>s1>>s2;
n=strlen(s1);
m=strlen(s2);
for(int i=1;i<=n;i++)
a[i]=s1[n-i]-'0';
for(int i=1;i<=m;i++)
b[i]=s2[m-i]-'0';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ans[i+j-1]+=a[i]*b[j];
}
len=n+m;
for(int i=1;i<len;i++)
if(ans[i]>=10){
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
while(ans[len]==0&&len>1)len--;
for(int i=len;i>=1;i--)
cout<<ans[i];
return 0;
}
高精除单精：
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int a[100005],ans[100005];
long long n,k,cnt=1,m;
bool flag;
void transmit(){
n=strlen(s);
for(int i=1;i<=n;i++)
a[i]=s[i-1]-'0';
return;
}
void init(){
k=a[cnt];
while(cnt<=n){
if(k<m){
ans[cnt++]=0;
k=k*10+a[cnt];
continue;
}
ans[cnt++]=k/m;k=k%m;
if(cnt>n)continue;
k=k*10+a[cnt];
}
for(int i=1;i<=n;i++){
if(ans[i]!=0)flag=true;
if(ans[i]==0&&!flag)continue;
cout<<ans[i];
}
}
int main(){
cin>>s>>m;
if(strlen(s)==1&&s[0]=='0'){
cout<<0;
return 0;
}
transmit();
init();
return 0;
}
数学：
快速幂：
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long ans=1;
int main(){
cin>>a>>b>>p;
long long s=b,h=a;
while(b){
if(b%2==1)ans=ans*a%p;
a=a*a%p;
b=b/2;
}
ans=ans%p;
printf("%lld^%lld mod %lld=%lld",h,s,p,ans);
}
线性筛素数：
#include<bits/stdc++.h>
using namespace std;
int n,sum,q;
int ans[100000005];
bool pd[100000005];
int main(){
cin>>n>>q;
pd[1]=true;
for(int i=2;i<=n;i++){
if(!pd[i])ans[++sum]=i;
for(int j=1;j<=sum&&i*ans[j]<=n;j++){
pd[ans[j]*i]=1;
if(i%ans[j]==0)break;
}
}
for(int i=1;i<=q;i++){
int h;
cin>>h;
cout<<ans[h]<<"\n";
}
return 0;
}
乘法逆元
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000005;
int a[N];
inline int read()
{
int w = 1,q = 0;
char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
return w * q;
}
void write(int x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
signed main()
{
int n, p;
n = read();
p = read();
a[1] = 1;
for (int i = 2; i <= n; i++)
a[i] = (p - p / i) * a[p % i] % p;
for (int i = 1; i <= n; i++)
{
write(a[i]);
printf("\n");
}
return 0;
}
矩阵相关
矩阵乘法
void multiply (int c[N][N], int a[N][N], int b[N][N]) {
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
c[i][j] += a[i][k] * b[k][j];
}
矩阵快速幂：
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, k;
const int N = 105;
const int Mod = 1e9 + 7;
struct node{
int a[N][N];
}A;
node operator*(const node &x, const node &y)
{
node ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans.a[i][j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % Mod;
return ans;
}
node qpow(node x, int m)
{
node ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans.a[i][j] = i == j ? 1 : 0;
while (m != 0)
{
if (m & 1) ans = ans * x;
x = x * x;
m = m >> 1;
}
return ans;
}
signed main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> A.a[i][j];
A = qpow(A, k);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << A.a[i][j] << (j == n ? "\n":" ");
}
return 0;
}
字符串
字符串哈希
#include<bits/stdc++.h>
using namespace std;
const int mod=999983;
const int base=261;
int n,ans;
vector<string>p[mod+5];
void insert(string s){
int hash=1,n=s.size();
for(int i=0;i<n;i++)
hash=(hash*base+s[i])%mod;
for(int i=0;i<p[hash].size();i++){
if(p[hash][i]==s)return;
}
p[hash].push_back(s);
ans++;
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
string x;
cin>>x;
insert(x);
}
cout<<ans;
return 0;
}
字典树
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
int tot, a[N][70], ans[N];
inline int cal(char x)
{
if (!(x < 'a' || x > 'z')) return x - 'a';
if (!(x < 'A' || x > 'Z')) return x - 'A' + 26;
return x - '0' + 52;
}
inline void insert(string x)
{
int len = x.size(), lst = 0;
for (register int i = 0; i < len; i++)
{
int t = cal(x[i]);
if (a[lst][t] == 0) a[lst][t] = ++tot;
lst = a[lst][t];
ans[lst]++;
}
}
inline int query(string x)
{
int len = x.size(), lst = 0, res = 0;
for (register int i = 0; i < len; i++)
{
int t = cal(x[i]);
if (a[lst][t] == 0) return 0;
lst = a[lst][t];
}
return ans[lst];
}
int main()
{
int T, lst = 0;
T = read();
while (T--)
{
int n, q;
n = read(), q = read();
for (register int i = 0; i <= tot; i++)
for (register int j = 0; j <= 62; j++)
a[i][j] = 0;
lst = 0;
for (register int i = 1; i <= tot; i++)
ans[i] = 0;
tot = 0;
while (n--)
{
string x;
cin >> x;
lst = max(lst, (int)x.size());
insert(x);
}
while (q--)
{
string x;
cin >> x;
write(query(x));
puts("");
}
}
return 0;
}
KMP 算法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int p[N];
char a[N], b[N];
int main() {
cin >> a + 1 >> b + 1;
int n = strlen(a + 1), m = strlen(b + 1), j = 0;
for (int i = 2; i <= m; i++) {
j = p[i - 1];
while (j && b[j + 1] != b[i]) j = p[j];
if (b[i] == b[j + 1]) j++;
p[i] = j;
}
int cnt = 0; j = 0;
for (int i = 1; i <= n; i++) {
while (j && b[j + 1] != a[i]) j = p[j];
if (b[j + 1] == a[i]) j++;
if (j == m) cout << i - m + 1 << "\n", j = p[j];
}
for (int i = 1; i <= m; i++)
cout << p[i] << " ";
return 0;
}