【小结】简单的板子

持续更新中~

索引

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;
} 

热门相关:流鱼无恙   锦庭娇   上神来了   万古至尊   锦庭娇