板子汇总

Falling_Sakura
  2023-08-06 09:15:51 2023-08-06 09:15:51 Created   2025-09-25 11:02:44 2025-09-25 11:02:44 Updated    8k Words  47 Mins  

乱序，想到什么可以补充。

Tarjan 求强连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
stack<int> s;
vector<int> g[N];
vector<int> g_2[N];
//cscc代表强连通分量的数量，scc代表每个点所属的强连通分量的编号，ins代表是否在栈中
int dfsn[N],low[N],ins[N],scc[N],deep,cscc,n;
void tarjan(int p)
{
    low[p]=dfsn[p]=++deep;
    ins[p]=1;
    s.push(p);
    for(auto &q:g[p])//遍历出边
    {
        if(!dfsn[q])//未访问
        {
            tarjan(q);
            low[p]=min(low[p],low[q]);
        }//访问过且q可达p，因为栈中元素强连通
        else if(ins[q]) low[p]=min(low[p],dfsn[q]);//注意这里为什么是dfsn[q]而不是low[q]
    }
    if(low[p]==dfsn[p])
    {
        int top=0;
        cscc++;
        while(top!=p)
        {
            top=s.top();
            s.pop();
            ins[top]=0;
            scc[top]=cscc;
        }
        
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)//原图不一定是强连通图，因此每个节点都要看一遍
        if(!dfsn[i])//未访问过
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(auto j:g[i])//以i为起点的出边
            if(scc[i]!=scc[j])//如果不是一个强连通分量，那就可以把两个强连通分量当作两个点连接起来
                g_2[scc[i]].push_back(scc[j]);//j是i的出边，即j的强连通分量是i的强连通分量的出边
    return 0;
}

缩点

P3387 【模板】缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e4 + 7, M = 1e5 + 7;

int n, m, cscc, depth, ans;
int dfsn[N], low[N], scc[N], w[N], rd[N], dist[N], val[N];
bool ins[N];
stack<int> s;
vector<int> g[N];
vector<int> G[N];

void tarjan(int p)
{
    low[p] = dfsn[p] = ++depth;
    ins[p] = true;
    s.push(p);
    for (auto &q : g[p])
    {
        if (!dfsn[q])
        {
            tarjan(q);
            low[p] = min(low[p], low[q]);
        }
        else if (ins[q]) low[p] = min(low[p], dfsn[q]);
    }
    if (dfsn[p] == low[p])
    {
        int top = 0;
        cscc++;
        while (top != p)
        {
            top = s.top();
            s.pop();
            val[cscc] += w[top];
            scc[top] = cscc;
            ins[top] = false;
        }
    }
}
void topsort()
{
    queue<int> q;
    for (int i = 1; i <= cscc; i++)
        if (!rd[i])
        {
            q.push(i);
            dist[i] = val[i];
        }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto & v : G[u])
        {
            dist[v] = max(dist[v], dist[u] + val[v]);
            rd[v]--;
            if (!rd[v]) q.push(v);
        }
    }
    for (int i = 1; i <= cscc; i++)
        ans = max(ans, dist[i]);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].emplace_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfsn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        for (auto &j : g[i])
            if (scc[i] != scc[j])
            {
                G[scc[i]].emplace_back(scc[j]);
                rd[scc[j]]++;
            }
    topsort();
    printf("%d\n", ans);
    return 0;    
}

Tarjan 求割点/割边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
vector<int> e[N];
int dfsn[N],low[N],fa[N];
int cnt;
vector<int> point;
/*割点*/
void tarjan(int p,bool root=true)
{
    int tot=0;
    low[p]=dfsn[p]=++cnt;
    for(auto &q:e[p])//枚举p的出边
    {
        if(!dfsn[q])//这个点没访问过
        {
            tarjan(q,false);//递归，并且这个点不是根
            low[p]=min(low[p],low[q]);//更新父节点的low值
            tot+=(low[q]>=dfsn[p]);//子节点的low值比父节点的dfs序还要大，那就把需要p的子树个数加一
            //需要p的子树是指删去p后子树无法与外界联系
        }
        else//访问过，那就对low值取min
        {
            low[p]=min(low[p],dfsn[q]);
        }
    }
    if(tot>root)//是根那就要大于1，否则就要大于0
        point.push_back(p);
}
vector<pair<int,int> > bridges;
/*割边*/
void tarjan_0(int p)
{
    low[p]=dfsn[p]=++cnt;
    for(auto &q:e[p])
    {
        if(!dfsn[q])
        {
            fa[q]=p;
            tarjan_0(q);
            low[p]=min(low[p],low[q]);
            if(low[q]>dfsn[p]) bridges.emplace_back(p,q);
        }
        else if(fa[p]!=q) low[p]=min(low[p],dfsn[q]);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
}

Tarjan 求点双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;
const int M=2e6+100;
int n,m,edcnt,cnt,cdcc;
int fir[N],low[N],dfsn[N];
vector<int> dcc[N];
stack<int> s;
vector<int> point;
struct edge
{
    int to,nxt;
}e[M<<1];
void add(int u,int v)
{
    e[++edcnt].to=v;
    e[edcnt].nxt=fir[u];
    fir[u]=edcnt;
}
void tarjan(int p,bool root=true)
{
    int tot=0;
    dfsn[p]=low[p]=++cnt;
    s.push(p);
    if(root&&fir[p]==0)
    {
        dcc[++cdcc].push_back(p);//孤立点
        return;
    }
    for(int i=fir[p];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(!dfsn[v])
        {
            tarjan(v,false);
            low[p]=min(low[v],low[p]);
            if(low[v]>=dfsn[p])
            {
                tot++;
                if(tot>root) point.push_back(p);
                cdcc++;
                int top;
                do
                {
                    top=s.top();
                    s.pop();
                    dcc[cdcc].push_back(top);
                } while (top!=v);
                dcc[cdcc].push_back(p);
            }
        }
        else low[p]=min(low[p],dfsn[v]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v) continue;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfsn[i]) tarjan(i);
    printf("%d\n",cdcc);
    for(int i=1;i<=cdcc;i++)
    {
        printf("%d",(int)dcc[i].size());
        for(auto &j:dcc[i])
            printf(" %d",j);
        puts("");
    }
    return 0;
}

Tarjan 求边双连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int M=2e6+10;
int fir[N],low[N],dfsn[N];
int n,m,edcnt=1,cnt,cdcc;
bool bridge[M<<1];
vector<int> dcc[N];
stack<int> s;
struct edge
{
    int to,nxt;
}e[M<<1];
void add(int u,int v)
{
    e[++edcnt].to=v;
    e[edcnt].nxt=fir[u];
    fir[u]=edcnt;
}
void tarjan(int p,int f)
{
    low[p]=dfsn[p]=++cnt;
    s.push(p);
    for(int i=fir[p];i;i=e[i].nxt)
    {
        int q=e[i].to;
        if(!dfsn[q])
        {
            tarjan(q,i);
            low[p]=min(low[p],low[q]);
            if(dfsn[p]<low[q]) bridge[i]=bridge[i^1]=true;
        }
        else if(i!=(f^1)) low[p]=min(low[p],dfsn[q]);//不是反向边
    }
    if(dfsn[p]==low[p])
    {
        cdcc++;
        int top;
        do
        {
            top=s.top();
            s.pop();
            dcc[cdcc].push_back(top);
        } while (top!=p);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v) continue;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfsn[i]) tarjan(i,0);
    }
    printf("%d\n",cdcc);
    for(int i=1;i<=cdcc;i++)
    {
        printf("%d",(int)dcc[i].size());
        for(auto &j:dcc[i])
            printf(" %d",j);
        puts("");
    }
    return 0;
}

其中利用了异或的性质，偶数加一奇数减一，令初始cnt为1使得边的编号从2开始，这样就可以通过异或1轻松知道反向边的编号了。

最短路

Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000007
int n,dist[maxn],m,first[maxn];
int s[maxn],e[maxn],d[maxn];
int main()
{
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s[i],&e[i],&d[i]);//起点，终点，长度
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;//起点距离
    for(int i=1;i<n;i++)//最多n-1条边,最多松弛n-1次，因为如果倒着来的话，所有点的dist都未知，每次只能更新一个点（一点点往后推），因此每轮会至少松弛一个点
        for(int j=1;j<=m;j++)//枚举边
        {
            dist[e[j]]=min(dist[e[j]],dist[s[j]]+d[j]);
        }
    return 0;
}

SPFA

Bellman-Ford的队列优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int first[maxn],dist[maxn];
bool inque[maxn];
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
void spfa(int s)
{
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    inque[s]=true;//这里不写也可以，因为第一次取出的一定是首点
    queue<int> q;
    q.push(s);//一开始只知道s的最短路
    while(q.size())
    {
        int now=q.front();
        q.pop();
        inque[now]=false;//记录当前点在不在队列里
        for(int i=first[now];i;i=ed[i].next)
        {
            int e=ed[i].e;
            int d=dist[now]+ed[i].d;
            if(d<dist[e])
            {
                dist[e]=d;//如果e变短了，那么也可以用它去更新其他点的最短路
                if(!inque[e])
                {
                    inque[e]=true;
                    q.push(e);
                }
            }
        }
    }
}
int main()
{
    return 0;
}

判断负环

可以记录每个点到起点经过的边数，边数不超过n-1；也可以记录每个点的入队次数，这个次数不能超过n-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int first[maxn],dist[maxn],times[maxn];
bool inque[maxn];
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
int T,n,m;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
bool spfa(int s)
{
    memset(times,0,sizeof(times));
    memset(inque,0,sizeof(inque));
    memset(dist,0x3f,sizeof(dist));
    times[s]=1;
    dist[s]=0;
    queue<int> q;
    q.push(s);//一开始只知道s的最短路
    while(q.size())
    {
        int now=q.front();
        q.pop();
        inque[now]=false;//记录当前点在不在队列里
        for(int i=first[now];i;i=ed[i].next)
        {
            int e=ed[i].e;
            int d=dist[now]+ed[i].d;
            if(d<dist[e])
            {
                dist[e]=d;//如果e变短了，那么也可以用它去更新其他点的最短路
                if(!inque[e])
                {
                    inque[e]=true;
                    q.push(e);
                    times[e]++;//记录入队次数
                    if(times[e]>n)//因为有0号点
                        return true;//存在负环
                }
            }
        }
    }
    return false;
}
int main()
{
    
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        scanf("%d%d",&n,&m);
        for(int j=1;j<=m;j++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(c>=0)
            {
                add_edge(a,b,c);
                add_edge(b,a,c);
            }
            else add_edge(a,b,c);
            
        }
        if(spfa(1))
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        memset(first,0,sizeof(first));
    }
    return 0;
}

Dijkstra

P4779 【模板】单源最短路径（标准版）)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn];
int n,m,s;
bool righ[maxn];//这个点有没有放到右边去
struct point{
    int p,d;//原点到p的最短距离为d
    point(){}
    point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
{
    return a.d>b.d;//小根堆
}
priority_queue<point> heap;
//松弛操作
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
void dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));//全部都赋值为最大值
    dist[s]=0;//s到s
    heap.push(point(s,0));
    //可以无变量名
    while(!heap.empty())
    {
        point now=heap.top();
        heap.pop();
        if(righ[now.p]) continue;//判断要写在这里，不能直接判断堆顶，因为可能pop之后堆就空了导致RE
        int p=now.p;
        // int d=now.d;//未加堆优化版，找到目前dist最小的点
        // int p=-1;//代表还没选任何点
        // for(int j=1;j<=n;j++)//循环后就找到了在左边最短路最小的点
        // {
        //     if(!righ[j]&&(p==-1||dist[p]>dist[j]))//righ[]代表有没有放到右边去
        //         p=j;
        righ[p]=1;//放到右边，枚举出边
        for(int j=first[p];j; j=ed[j].next)//ed[j].e即为p的下一个点
        {
            int e=ed[j].e;
            int d=dist[p]+ed[j].d;
            if(dist[e]>d)
            {
                dist[e]=d;
                if(!righ[e]) heap.push(point(e,d));//没访问过并且松弛过的点
            }
        }
    }
}
signed main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==1061109567)
        {
            cout<<2147483647<<" ";
            continue;
        }
        printf("%d ",dist[i]);
    }
    return 0;
}

Floyed

1
2
3
4
for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dist[i][j]=max(dist[i][j],dist[i][k]+dist[k][j]);

Johnson

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 6e3 + 10;

int n, m, edcnt;
int h[N];
int s[N],t[N],d[N];
int fir[N];
int dist[N];
bool vis[N];

struct edge
{
    int to, val, nxt;
}e[(M << 1) + N];
struct point
{
    int id,len;
    point(){}
    point(int a,int b):id(a),len(b){}
    bool operator < (const point &x)const
    {
        return len > x.len;
    }
};

void Add(int u, int v, int w)
{
    e[++edcnt].nxt = fir[u];
    e[edcnt].to = v;
    e[edcnt].val = w;
    fir[u] = edcnt;
}
void Dijkstra(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    priority_queue<point> q;
    while(!q.empty()) q.pop();
    q.push(point(s,0));
    while(!q.empty())
    {
        point now = q.top();
        q.pop();
        if(vis[now.id]) continue;
        vis[now.id] = true;
        for(int i = fir[now.id]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            int d = dist[now.id] + e[i].val;
            if(d < dist[v])
            {
                dist[v] = d;
                if(!vis[v]) q.push(point(v,dist[v]));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d",&s[i],&t[i],&d[i]);
    int tot = m;
    for(int i = 1; i <= n; ++i)
    {
        s[++tot] = 0;
        t[tot] = i;
        d[tot] = 0;
    }
    for(int i = 1; i <= n; ++i) // 多加了一个源点，所以最多松弛 n 次
        for(int j = 1; j <= n + m; ++j) // n+m条边
            h[t[j]] = min(h[t[j]], h[s[j]] + d[j]);
    for(int j = 1; j <= n + m; ++j)
        if(h[t[j]] > h[s[j]] + d[j])
        {
            printf("-1");
            return 0;
        }
    for(int i = 1; i <= m; ++i)
        Add(s[i], t[i], d[i] + h[s[i]] - h[t[i]]);
    for(int i = 1; i <= n; ++i)
    {
        Dijkstra(i);
        ll ans = 0;
        for(int j = 1; j <= n; ++j)
            ans += j * (dist[j] == 0x3f3f3f3f ? 1e9 : dist[j] - h[i] + h[j]);
        printf("%lld\n", ans);
    }
    return 0;
}

倍增求 LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn],f[maxn][20],depth[maxn],g[maxn][20];
int n,m,s;
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
void dfs(int now)//从根节点开始dfs//预处理
{
    for(int i=first[now];i;i=ed[i].next)
        if(ed[i].e!=f[now][0])
        {
            int p=ed[i].e;
            depth[p]=depth[now]+1;
            f[p][0]=now;
            g[p][0]=ed[i].d;//代表从p向上走……步（这里指一步）所经过的最短距离为这条边的边权
            for(int x=1;x<=18;x++)
            {
                f[p][x]=f[f[p][x-1]][x-1];
                g[p][x]=min(g[p][x-1],g[f[p][x-1]][x-1]);
            }
            dfs(p);
        }
}
//1.调整深度2.一起跳
int get_lca(int p1,int p2)//魔改后是求边权最小值
{
	depth[0] = -1; // 防止跳到零号点
    if(depth[p1]<depth[p2]) swap(p1,p2);//保证p1较深
    for(int x=18;x>=0;x--)
    {
        int p=f[p1][x];
        if(depth[p]>=depth[p2])
        {
            p1=p;//完成后p1p2深度就一致了
        }
    }
    if(p1==p2) return p1;//防止p1，p2在同一点上
    for(int x=18;x>=0;x--)
    {
        if(f[p1][x]!=f[p2][x])
        {
            p1=f[p1][x],p2=f[p2][x];
        }
    }
    return f[p1][0];
}

DFS 序求 LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 8;

int idx, n, m, root, cnt;
int dfsn[N], st[25][N], fir[N];
int Log2[N];
struct Edge
{
    int to, nxt;
}e[N << 1];

void init()
{
    Log2[0] = -1;
    for (int i = 1; i <= n; i++)
        Log2[i] = Log2[i / 2] + 1;
}
int get(int x, int y)
{
    return dfsn[x] < dfsn[y] ? x : y;
}
void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    fir[u] = cnt;
}
void dfs(int u, int fa)
{
    dfsn[u] = ++idx;
    st[0][idx] = fa; // 以 idx 为起点长度为 (1 << i) 的区间内 dfsn 最小的点的父亲
    for (int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa) continue;
        dfs(v, u);
    }
}
int lca(int x, int y)
{
    if (x == y) return x;
    if (dfsn[x] > dfsn[y]) swap(x, y);
    int d = Log2[dfsn[y] - dfsn[x]]; // +1 -1
    return get(st[d][dfsn[x] + 1], st[d][dfsn[y] - (1 << d) + 1]); // [dfsn_u + 1, dfsn_v]
}
int main()
{
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 2, u, v; i <= n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    init();
    dfs(root, 0);
    for (int i = 1; i <= Log2[n]; i++) // Log2[i] 下取整
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = get(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int N=500;
struct dat{
    int val,id;
}olda[N];
int newa[N];
bool cmp(dat x,dat y)
{
    return x.val<y.val;
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&olda[i].val);
        olda[i].id=i;
    }
    sort(olda+1,olda+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        newa[olda[i].id]=i;
        if(olda[i].val==olda[i-1].val)
            newa[olda[i].id]=newa[olda[i-1].id];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",newa[i]);
    }
    return 0;
}

高精度

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int a[520],b[520],c[520];
int main()
{
    string A,B;
    cin>>A>>B;
    int len=max(A.length(),B.length());
    for(int i=A.length()-1,j=1;i>=0;i--,j++)
        a[j]=A[i]-'0';
    for(int i=B.length()-1,j=1;i>=0;i--,j++)
        b[j]=B[i]-'0';
    for(int i=1;i<=len;i++)
    {
        c[i]+=a[i]+b[i];
        c[i+1]=c[i]/10;
        c[i]%=10;
    }
    if(c[len+1])
        len++;
    for(int i=len;i>=1;i--)
        printf("%d",c[i]);
}

乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int a[10200],b[10200],c[10200];
int main()
{
    string A,B;
    cin>>A>>B;
    int lena=A.length(),lenb=B.length();
    for(int i=lena-1;i>=0;i--)
        a[lena-i]=A[i]-'0';
    for(int i=lenb-1;i>=0;i--)
        b[lenb-i]=B[i]-'0';
    for(int i=1;i<=lena;i++)
    {
        for(int j=1;j<=lenb;j++)
        {
            c[i+j-1]+=a[i]*b[j];
        }
    }
    int len=lena+lenb;
    for(int i=1;i<=len;i++)
    {
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(!c[len])
        len--;
    for(int i=max(1,len);i>=1;i--)
        printf("%d",c[i]);
}

排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
int s[200005];
void qsort(int a[],int l,int r)
{
    int i=l,j=r,flag=a[(l+r)/2],tmp;
    do{
        while(a[i]<flag) i++;
        while(a[j]>flag) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            // tmp=a[i];
            // a[i]=a[j];
            // a[j]=tmp;
            i++,j--;
        }
    }while(i<=j);
    if(l<j)
        qsort(a,l,j);
    if(i<r)
        qsort(a,i,r);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i]);
    qsort(s,1,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",s[i]);
    }
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
int h[N],e[N],nex[N],cnt;
int que[N],d[N];
void add(int a,int b)//他是从0~m-1
{
    e[++cnt]=b;//end
    nex[cnt]=h[a];
    h[a]=cnt;
}
bool topsort()
{
    int hh=1,tt=0;
    for(int l=1;l<=n;l++)
        if(!d[l])
            que[++tt]=l;
        while(hh<=tt)
        {
            int t=que[hh++];//取出队首
            for(int i=h[t];i!=-1;i=nex[i])
            {
                int j=e[i];
                d[j]--;
                if(d[j]==0)
                    que[++tt]=j;
            }
        }
    return tt==n;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(int i=1;i<=n;i++)
            printf("%d ",que[i]);
        puts("");
    }
    else
        cout<<-1<<endl;
    return 0;
}

最小生成树

Kruscal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int n,m;
int fa[N];
struct edge{
	int u,v,w;//u-----w------>v
}eg[1000005]; 
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int cnt,ans,tot;
void add(int u,int v,int w)
{
	eg[++cnt].u=u;
	eg[cnt].v=v;
	eg[cnt].w=w;
}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void Kruscal()
{
	sort(eg+1,eg+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int rootu=find(eg[i].u);
		int rootv=find(eg[i].v);
		if(rootu!=rootv)
		{
			ans+=eg[i].w;
			tot++;
			fa[rootu]=rootv;
		}
	}
	return;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
 	return 0;
}

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn];
int n,m,s;
bool righ[maxn];//这个点有没有放到右边去
struct point{
    int p,d;//原点到p的最短距离为d
    point(){}
    point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
{
    return a.d>b.d;
}
priority_queue<point> heap;
//松弛操作
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
void prim(int s)
{
    memset(dist,0x3f,sizeof(dist));//全部都赋值为最大值
    dist[s]=0;//s到s
    heap.push(point(s,0));
    while(!heap.empty())
    {
        point now=heap.top();
        heap.pop();
        int p=now.p;
        if(righ[p]) continue;
        righ[p]=1;//放到右边
        for(int j=first[p];j;j=ed[j].next)//ed[j].e即为p的下一个点
        {
            int e=ed[j].e;
            int d=ed[j].d;
            if(dist[e]>d)
            {
                dist[e]=d;
                if(!righ[e]) heap.push(point(e,d));
            }
        }
    }
}
signed main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    } 
    return 0;
}

莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
int q,a[N],cnt[N],l=1,r=0,now=0,belong[N];
struct query
{
    int l,r;
}e[N];
int cmp(query a, query b)
{
	return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
void add(int pos)
{
    if(!cnt[a[pos]]) ++now;
    ++cnt[a[pos]];
}
void del(int pos)
{
    --cnt[a[pos]];
    if(!cnt[a[pos]]) --now;
}
void work()
{
    for(int i=1;i<=q;i++)
    {

        int ql,qr;
        scanf("%d%d",&qr,&ql);
        while(l<ql) del(l++);
        while(l>ql) add(--l);
        while(r<qr) add(++r);
        while(r>qr) del(r--);
        printf("%d",now);
    }
}
int main()
{

    return 0;
}

快读

int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline int read()
{
	int x=0,y=1; 
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*y;
}

double

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inline double read()
{
	double x=0,y=1,w=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	if(c=='.')
	{
		c=getchar()
		while(c>='0'&&c<='9')
		{
			w=w/10.0;
			x+=(c-'0')*w;
			c=getchar();
		}
	}
	return x*y;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
ll a[N];
struct Node {
  int l, r;
  ll sum;
  ll add;
} tr[N << 2];
void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }
void pushdown(int u) {
  Node &root = tr[u], &left = tr[u << 1], &righ = tr[u << 1 | 1];
  if (root.add) {
    left.add += root.add, righ.add += root.add;
    left.sum += 1ll * (left.r - left.l + 1) * root.add;
    righ.sum += 1ll * (righ.r - righ.l + 1) * root.add;
    root.add = 0;
  }
}
void build(int u, int l, int r) {
  tr[u].l = l, tr[u].r = r;
  if (l == r) {
    tr[u].sum = a[r];
    tr[u].add = 0;
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
}
void modify(int u, int l, int r, ll x) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].sum += 1ll * (tr[u].r - tr[u].l + 1) * x;
    tr[u].add += x;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, x);
    if (r > mid) modify(u << 1 | 1, l, r, x);
    pushup(u);
  }
}
ll query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
  pushdown(u);
  int mid = (tr[u].l + tr[u].r) >> 1;
  ll ans = 0;
  if (l <= mid) ans += query(u << 1, l, r);
  if (r > mid) ans += query(u << 1 | 1, l, r);
  return ans;
}
int n, m;
signed main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  build(1, 1, n);
  while (m--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      ll k;
      scanf("%lld", &k);
      modify(1, x, y, k);
    } else {
      printf("%lld\n", query(1, x, y));
    }
  }
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;

int n, m, q;
int a[N];
struct Node
{
    int l, r;
    LL sum, add, mul;
}tr[N << 2];

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % q;
}
void eval(Node &t, LL add, LL mul)
{
    t.sum = (t.sum * mul % q + (t.r - t.l + 1) * add % q);
    t.add = (t.add * mul % q + add) % q;
    t.mul = t.mul * mul % q;
}
void pushdown(int u)
{
    eval(tr[u << 1], tr[u].add, tr[u].mul);
    eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0;
    tr[u].mul = 1;
}
void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r, tr[u].add = 0, tr[u].mul = 1;
    if(l == r)
    {
        tr[u].sum = a[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int l, int r, int add, int mul)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        eval(tr[u], add, mul);
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(u << 1, l, r, add, mul);
    if(r > mid) modify(u << 1 | 1, l, r, add, mul);
    pushup(u);
}
LL query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    LL sum = 0;
    if(l <= mid) sum = (sum + query(u << 1, l, r)) % q;
    if(r > mid) sum = (sum + query(u << 1 | 1, l, r)) % q;
    return sum;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while(m--)
    {
        int op, l, r, k;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1)
        {
            scanf("%d", &k);
            modify(1, l, r, 0, k);
        }
        else if(op == 2)
        {
            scanf("%d", &k);
            modify(1, l, r, k, 1);
        }
        else printf("%lld\n", query(1, l, r));
    }
    return 0;
}

可持久化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

int n, m, cnt;
int idx;
int a[N];
int root[N];
struct Node
{
    int l, r;
    int key;
}tr[23 * N];

void build(int &u, int l, int r)
{
    u = ++idx;
    if(l == r)
    {
        tr[u].key = a[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(tr[u].l, l, mid);
    build(tr[u].r, mid + 1, r);
}
void modify(int &u, int p, int l, int r, int x, int v)
{
    u = ++idx;
    tr[u] = tr[p];
    if(l == r)
    {
        tr[u].key = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(tr[u].l, tr[p].l, l, mid, x, v);
    else modify(tr[u].r, tr[p].r, mid + 1, r, x, v);
}
int query(int u, int l, int r, int x)
{
    if(!u) return 0;
    if(l == r) return tr[u].key;
    int mid = (l + r) >> 1;
    if(x <= mid) return query(tr[u].l, l, mid, x);
    if(x > mid) return query(tr[u].r, mid + 1, r, x);
    return 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(root[0], 1, n);
    while(m--)
    {
        int op, last, loc, val;
        scanf("%d%d", &last, &op);
        if(op == 1)
        {
            scanf("%d%d", &loc, &val);
            modify(root[++cnt], root[last], 1, n, loc, val);
        }
        else if(op == 2)
        {
            scanf("%d", &val);
            printf("%d\n", query(root[last], 1, n, val));
            root[++cnt] = root[last];
        }
    }
    return 0;
}

平衡树

Treap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int INF = 1e8;

int n, root, idx;
struct Node
{
    int l, r, key, val;
    int cnt, siz;
}tr[N];

int get_node(int key)
{
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].siz = 1;
    return idx;
}
void pushup(int p)
{
    tr[p].siz = tr[tr[p].l].siz + tr[tr[p].r].siz + tr[p].cnt;
}
void build()
{
    root = get_node(-INF);
    tr[root].r = get_node(INF);
    pushup(root);
}
void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r;
    tr[q].r = p;
    p = q;
    pushup(tr[p].r);
    pushup(p);
}
void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l;
    tr[q].l = p;
    p = q;
    pushup(tr[p].l);
    pushup(p);
}
void insert(int &p, int key)
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt++;
    else if(tr[p].key > key)
    {
        insert(tr[p].l, key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else 
    {
        insert(tr[p].r, key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}
void remove(int &p, int key)
{
    if(!p) return;
    if(tr[p].key == key)
    {
        if(tr[p].cnt > 1) tr[p].cnt--;
        else if(tr[p].l || tr[p].r)
        {
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if(tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);
    pushup(p);
}
int get_rank(int p, int key)
{
    if(!p) return 1;
    if(tr[p].key == key) return tr[tr[p].l].siz + 1;
    if(tr[p].key > key) return get_rank(tr[p].l, key);
    return tr[tr[p].l].siz + tr[p].cnt + get_rank(tr[p].r, key);
}
int get_key(int p, int rank)
{
    if(!p) return INF;
    if(tr[tr[p].l].siz >= rank) return get_key(tr[p].l, rank);
    if(tr[tr[p].l].siz + tr[p].cnt >= rank) return tr[p].key;
    return get_key(tr[p].r, rank - tr[tr[p].l].siz - tr[p].cnt);
}
int get_prev(int p, int key)
{
    if(!p) return -INF;
    if(tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key)
{
    if(!p) return INF;
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    scanf("%d", &n);
    while(n--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        switch(op)
        {
            case 1: 
                insert(root, x);
                break;
            case 2:
                remove(root, x);
                break;
            case 3: 
                printf("%d\n", get_rank(root, x) - 1);
                break;
            case 4:
                printf("%d\n", get_key(root, x + 1));
                break;
            case 5:
                printf("%d\n", get_prev(root, x));
                break;
            case 6:
                printf("%d\n", get_next(root, x));
                break;
        }
    }
    return 0;
}

字符串

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char a[N],b[N];
int nxt[N];
int la,lb;
void calc()
{
    for(int i=1,j=0;i<lb;i++)
    {
        while(j&&b[i]!=b[j]) j=nxt[j-1];
        if(b[i]==b[j]) j++;
        nxt[i]=j;
    }
}
void kmp()
{
    for(int i=0,j=0;i<la;i++)
    {
        while(j&&a[i]!=b[j]) j=nxt[j-1];
        if(a[i]==b[j]) j++;
        if(j==lb)
        {
            printf("%d\n",i-j+2);
            j=nxt[j-1];
        }
    }
}
int main()
{
    scanf("%s%s",a,b);
    la=strlen(a);
    lb=strlen(b);
    calc();
    kmp();
    for(int i=0;i<lb;i++)
        printf("%d ",nxt[i]);
    return 0;
}

Z

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int n;
int z[100005];
int main()
{
    n=strlen(s);
    z[0]=n;
    for(int i=1,l=0,r=0;i<n;i++)
    {
        if(z[i-l]<r-i+1)//当前已经相同的部分比已知lcp要大
            z[i]=z[i-l];
        else
        {
            z[i]=max(r-i+1,0);
            while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;
            l=i,r=i+z[i]-1;
        }
    }
    return 0;
}

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n;
int d[1000005];
char s[1000005];
int main()
{
    for(int i=0,l=0,r=-1;i<n;i++)
    {
        int j=l+r-i;//对称点
        int dj=j>=0?d[j]:0;//不能越界
        d[i]=max(min(dj,r-i+1),0);
        if(j-dj<l)//j-dj+1<=l
        {
            while(i-d[i]>=0&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]]) d[i]++;
            l=i-d[i]+1,r=i+d[i]-1;
        }
    }
    return 0;
}

Trie

数学

快速幂

非递归：

1
2
3
4
5
6
7
8
9
10
11
int ksm(int x, int y)
{
    int res = 1;
    while(y > 0)
    {
        if(y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

递归：

1
2
3
4
5
6
7
8
int ksm(int x, int y)
{
    if(y == 1) return x;
    int z = ksm(x, (y >> 1));
    z = z * z;
    if(y & 1) z = z * x;
    return z;
}

素性测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

int n;
ll Ksm(int x, int y, int p)
{
    ll res = 1;
    while(y > 0)
    {
        if(y & 1) res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res;
}
bool Miller_Rubbin(int n, int a)
{
    int d = n - 1, r = 0;
    while(!(d & 1))
    {
        d >>= 1;
        r++;
    }
    int x = Ksm(a, d, n);
    if(x == 1) return true;
    for(int i = 1; i <= r; ++i)
    {
        if(x == n - 1) return true;
        x = 1ll * x * x % n;
    }
    return false;
}
bool Check(int x)
{
    if(n < 2) return false;
    for(int i = 1; i <= 12; ++i)
    {
        if(!Miller_Rubbin(x, prime[i])) return false;
    }
    return true;
}
int main()
{
    int t;
    scanf("%d", &t);
    cout << Check(t) << endl;
    return 0;
}
  • Title: 板子汇总
  • Author: Falling_Sakura
  • Created at : 2023-08-06 09:15:51
  • Updated at : 2025-09-25 11:02:44
  • Link: https://vercel.fallingsakura.top/61811bf3.html
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
板子汇总
  1. 1. Tarjan 求强连通分量
    1. 1.1. 缩点
  2. 2. Tarjan 求割点/割边
    1. 2.1. Tarjan 求点双连通分量
    2. 2.2. Tarjan 求边双连通分量
  3. 3. 最短路
    1. 3.1. Bellman-Ford
    2. 3.2. SPFA
      1. 3.2.1. 判断负环
    3. 3.3. Dijkstra
    4. 3.4. Floyed
    5. 3.5. Johnson
  4. 4. 倍增求 LCA
  5. 5. DFS 序求 LCA
  6. 6. 离散化
  7. 7. 高精度
    1. 7.1. 加法
    2. 7.2. 乘法
  8. 8. 排序
    1. 8.1. 快速排序
  9. 9. 拓扑排序
  10. 10. 最小生成树
    1. 10.1. Kruscal
    2. 10.2. Prim
  11. 11. 莫队
  12. 12. 快读
    1. 12.1. int
    2. 12.2. double
  13. 13. 线段树
    1. 13.1. 可持久化
  14. 14. 平衡树
    1. 14.1. Treap
  15. 15. 字符串
    1. 15.1. KMP
    2. 15.2. Z
    3. 15.3. Manacher
    4. 15.4. Trie
  16. 16. 数学
    1. 16.1. 快速幂
    2. 16.2. 素性测试