light5QAQ
light5QAQ
文章13
标签10
分类6
回到首页
文章归档
文件下载
我的私密库
给我赞助
关于博主

文章分类

一言

文章归档

最新文章

© 2026 light5QAQ Powered by Hexo & Nexmoe
本站总访问量次

鄂ICP备2020018486号
OI算法复(学)习笔记

OI算法复(学)习笔记

2026年04月06日 Tech 约20.7k字 预计需要93分钟
双端队列 双端队列是指一个可以在队首/队尾插入或删除元素的队列

构造使用deque<int> d即可

用法如下：

  • q.front() 返回队首元素

  • q.back() 返回队尾元素

  • q.push_back() 在队尾插入元素

  • q.pop_back() 弹出队尾元素

  • q.push_front() 在队首插入元素

  • q.pop_front() 弹出队首元素

  • q.insert() 在指定位置前插入元素

  • q.erase() 删除指定位置的元素

  • q.empty() 队列是否为空

  • q.size() 返回队列中元素的数量

例题：双向动态列车

题目描述

想象一下一列动态列车，这种列车特别之处在于它的首节和末节车厢都可以进行装载和卸载操作。这意味着乘客可以从列车的前端或后端上车，也可以从任何一端下车。

你将获得一系列关于乘客上车和下车的操作，你的任务是在所有操作完成后报告列车最终的乘客状态。

操作指令格式：

  • LIN X — 将乘客X从列车的前端上车；

  • RIN X — 将乘客X从列车的后端上车；

  • LOUT — 从列车的前端让一位乘客下车；

  • ROUT — 从列车的后端让一位乘客下车。

输入格式

第一行包含一个整数M(M≤10,000M)表示操作的数量。

接下来的M行，每行包含一个操作指令。

输出格式

输出的第一行应描述在进行了M次操作之后列车的状态。从列车的前端到后端输出乘客编号，每两个乘客编号之间用一个空格隔开。

如果存在任何非法的操作(如尝试让乘客从一个空列车的端下车)，这些操作的错误应在输出中得到相应的指示。每个非法操作的格式为“X ERROR”，其中X是该操作的序号（从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
#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
    deque<int> d;
    int m;
    cin>>m;
    int cmp=0;
    for(int i=1;i<=m;i++){
        string s;
        int n;
        cin>>s;
        if(s=="LIN"){
            cin>>n;
            d.push_front(n);
        }else if(s=="RIN"){
            cin>>n;
            d.push_back(n);
        }else if(s=="LOUT"){
            if(d.size()==0){
                cmp++;
                a[cmp]=i;
            }else d.pop_front();
            
        }else if(s=="ROUT"){
            if(d.size()==0){
                cmp++;
                a[cmp]=i;
            }else d.pop_back();
        }
    }
    for(int i=0;i<d.size();i++){
        cout<<d[i]<<" ";
    }
    cout<<endl;
    if(cmp>0) for(int i=1;i<=cmp;i++) cout<<a[i]<<" ERROR"<<endl;
    return 0;
}
字符串相关用法

string s.substr(int a, int l)可以从s的a(从0开始)截取一个长度为l的字符串

string s.erase(int p,int n) 删除s从p开始的n个字符

string s.insert(int p,string ss) 在s的p位置插入字符串s s

sprintf(char数组s,"%d",int n) 将n转换放置到char数组s中

sscanf(char数组s,"%d",int &n) 将char数组s转换放置到n中

reverse(v.begin(),v.end())或reverse(a+begin,a+end) 反转范围

并查集

引入

有时，你需要知道多个东西之间有没有关系，而时间和空间限制不允许你大手大脚，并查集便应运而生

简介

并查集是一个树形结构，支持合并和查询，通过储存每个点的父亲实现各种操作。而又因为只需要知道各个点之间有没有关系，所以可以随意选取一个根节点，并且判断操作只需要判断各个点是否在同一棵树内就可以完成，而我们只要比较各点所在树的根节点是否相同就可以，所以只需要存储各点的父亲即可递归查询到根节点进行判断了。

初始化

每个点开始时应当各自为树，各无关系。为了方便我们将父亲为自己的点定义为根节点，因此此处将各个点的父亲定义为自己。

1
2
int p[n+1]; // 第i个点的父亲是p[i]
for(int i=1;i<=n;i++) p[i]=i;

查询

查询是为了找到根节点，很显然可以通过递归查询父亲进行解决。

1
2
3
4
int find(int x){
    if(p[x]=x) return x; //自己就是根节点直接返回
    return find(p[x]); //如果不是再查询自己父亲的父亲
}

路径压缩

递归还是太浪费时间了，仔细一想我们似乎不需要建立一个常规的树形结构，既然只需要知道每个点的根节点，我们可以直接把每个点连接到根节点上，而这个操作可以边查询边进行。

1
2
3
4
int find(int x){
    if(p[x]=x) return x; //自己就是根节点直接返回
    return p[x]=find(p[x]); //如果不是再查询自己父亲的父亲，并且将当前节点直接并到父亲的父亲下
}

合并

将一棵树的根节点连到另一棵树的根节点就好了，当然，由于这个合并操作过于简单，很多情况下也不会将其写成函数。

1
2
3
void unite(int x,int y){
    pa[find(x)]=find(y);
}

以上就是并查集的基础要点了，做一道模板题试试水吧。

例题1：P3367 【模板】并查集

P3367 【模板】并查集

题目背景

本题数据范围已经更新到 1≤N≤2×1051\le N\le 2\times 10^5，1≤M≤1061\le M\le 10^6。

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。

接下来 MM 行，每行包含三个整数 Zi,Xi,YiZ_i,X_i,Y_i 。

当 Zi=1Z_i=1 时，将 XiX_i 与 YiY_i 所在的集合合并。

当 Zi=2Z_i=2 时，输出 XiX_i 与 YiY_i 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 Zi=2Z_i=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

1
2
3
4
5
N
Y
N
Y

说明/提示

对于 15%15\% 的数据，N≤10N \le 10，M≤20M \le 20。

对于 35%35\% 的数据，N≤100N \le 100，M≤103M \le 10^3。

对于 50%50\% 的数据，1≤N≤1041\le N \le 10^4，1≤M≤2×1051\le M \le 2\times 10^5。

对于 100%100\% 的数据，1≤N≤2×1051\le N\le 2\times 10^5，1≤M≤1061\le M\le 10^6，1≤Xi,Yi≤N1 \le X_i, Y_i \le N，Zi∈{1,2}Z_i \in \{ 1, 2 \}。

解答

分析

模板题，照搬以上讲解内容即可。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int p[N];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void unite(int x,int y){
    p[find(x)]=find(y);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++){
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1){
            if(find(x)==find(y)) continue;
            unite(find(x),find(y));
        }else{
            if(find(x)==find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        } 
    }
    return 0;
}

当然，单独的并查集确实简单，但是要注意识别和与其他知识点的合用。

例题2：U149298 搭配购买

U149298 搭配购买

题目背景

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，……，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限，所以他希望尽量买的价值越多越好。

题目描述

无

输入格式

第1行nn，mm，ww，表示nn朵云，mm个搭配，Joe有ww的钱第2∼n+12 \sim n+1行，每行cic_i，did_i表示ii朵云的价钱和价值第n+2∼n+1+mn+2 \sim n+1+m行，每行uiu_i，viv_i，表示买uiu_i就必须买viv_i，同理，如果买viv_i就必须买uiu_i。

输出格式

一行，表示可以获得的最大价值

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出 #1

1
1

说明/提示

30%30\%的数据保证：n≤100n \le 100

50%50\%的数据保证：n≤1,000n \le 1,000；m≤100m \le 100；w≤1,000w \le 1,000

100%100\%的数据保证：n≤10,000n \le 10,000；0≤m≤50000 \le m \le 5000；w≤10,000w \le 10,000

解答

分析

因为云朵需要搭配来买，所以可以用并查集将代价和价值捆绑到一起，接下来就转换成了一个01背包问题。

标程

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,w;
int p[N],c[N],d[N];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void unite(int x,int y){
    int a=find(x),b=find(y);
    if(a!=b){p[a]=b;c[b]+=c[a];d[b]+=d[a];} 
}
int f[N];
int main() {
	cin>>n>>m>>w;
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=n;i++) cin>>c[i]>>d[i];
	int u,v;
	for(int i=1;i<=m;i++){
	    cin>>u>>v;
	    unite(u,v);
	}
    for(int i=1;i<=n;i++){
        if(p[i]!=i) continue;
        for(int j=w;j>=c[i];j--){
            f[j]=max(f[j],f[j-c[i]]+d[i]);
        }
    }
    cout<<f[w]<<endl;
}

拓展并查集

有时，我们不只需要储存朋友关系，还需要储存敌人关系。我们知道并查集只能储存朋友，而不能储存敌人，所以我们可以用拓展并查集将敌人放进并查集中。

如何将敌人用朋友的方式标识出来呢？我们知道敌人的敌人就是朋友，所以不妨设一共有n个人，我们定义第a+n个点是第a个点的敌人，如果a与b是敌人，我们只需要让a和b+n成为朋友，a+n和b成为朋友，问题便迎刃而解。

接下来做一道模板题试一试吧！

例题3：盟友与宿敌

描述

在某个奇妙的魔法世界里，许多魔法师聚集在一起进行一场大型魔法竞技。他们之间有着复杂的关系：有些是盟友，有些则是宿敌。

规则如下：

1.我的盟友的盟友，也是我的盟友；

  1. 我的宿敌的宿敌，是我的盟友；

  2. 两个人只要是盟友，就认为他们属于同一魔法团队。

现在，给你若干魔法师之间的关系，请问：最多可以有多少个独立的魔法团队？

输入描述

第一行是一个整数N(2≤N≤1000)N(2\le N\le 1000)，表示参赛的魔法师人数（从1编号到N）。

第二行是一个整数M(1≤M≤5000)M(1\le M\le5000)，表示关于魔法师的关系信息的条数。

以下M行，每行可能是F p q或E p q(1≤p,q≤N)(1\le p,q\le N)，

  • F 表示p和q是盟友，

  • E 表示p和q是宿敌。

输入数据保证不会产生信息的矛盾。

输出描述

输出文件只有一行，表示最大可能的魔法团队数。

解答

分析

使用拓展并查集进行模拟即可，因为要求找到魔法团队数，所以可以使用自动去重的set进行遍历根节点。

###标程

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
#include <bits/stdc++.h>
using namespace std;
int n,m;
int p[2010];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void unite(int x,int y){
    p[find(x)]=find(y);
}
set<int> s;
int main() {
    cin>>n>>m;
    for(int i=1;i<=2*n;i++) p[i]=i;
    char r;
    int p,q;
    while(m--){
        cin>>r>>p>>q;
        if(r=='F') unite(p,q);
        else{unite(p,q+n);unite(p+n,q);}
    }
    for(int i=1;i<=n;i++) s.insert(find(i));
    cout<<s.size();

}

接下来我们做两道比较难的拓展并查集题目。

例题4：P2024 [NOI2001] 食物链

P2024 [NOI2001] 食物链

题目描述

动物王国中有三类动物 A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。AA 吃 BB，BB 吃 CC，CC 吃 AA。

现有 NN 个动物，以 1∼N1 \sim N 编号。每个动物都是 A,B,CA,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 NN 个动物所构成的食物链关系进行描述：

  • 第一种说法是 1 X Y，表示X和Y是同类。

  • 第二种说法是 2 X Y，表示X吃Y。

此人对 NN 个动物，用上述两种说法，一句接一句地说出 KK 句话，这 KK 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

  • 当前的话与前面的某些真的话冲突，就是假话；

  • 当前的话中X或Y比N大，就是假话；

  • 当前的话表示X吃X，就是假话。

你的任务是根据给定的 NN 和 KK 句话，输出假话的总数。

输入格式

第一行两个整数，N,KN,K，表示有 NN 个动物，KK 句话。

第二行开始每行一句话。格式见题目描述与样例。

输出格式

一行，一个整数，表示假话的总数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出 #1

1
2
3

说明/提示

对于全部数据，1≤N≤5×1041\le N\le 5 \times 10^4，1≤K≤1051\le K \le 10^5。

解答

分析

显然，由于有三种动物，所以拓展并查集需要开三倍大小，具体动物种类对问题没有影响。

对于判断假话环节，x或y比n大和x吃x很好解决，难点在于判断是否和前面冲突。

我们有这样一个关系图：

1
a->a+n->a+2n->a

如果他告诉我们x和y是同一种动物。但是实际上，x和y+n是一家的或者x和y+2n是一家的，这样两者是冲突的。

如果不冲突，直接合并x和y，x+n和y+n，x+2n和y+2n就可以了。

如果他告诉我们x能吃y，即x和吃y的人是一家的，即x和y+2n是一家的。但是若x和y是一家的，x和y+n(y的食物)是一家的，两者冲突。

如果不冲突，直接合并x和y+2n，x+n和y，x+2n和y+n就可以了。

标程

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;
const int N=5e4+5;
int n,k;
int p[3*N];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void unite(int x,int y){
    p[find(x)]=find(y);
}
int main() {
    cin>>n>>k;
    int a,x,y;
    int cnt=0;
    for(int i=1;i<=3*n;i++) p[i]=i;
    while(k--){
        cin>>a>>x>>y;
        if(x>n||y>n){cnt++;continue;} 
        if(x==y&&a==2){cnt++;continue;} 
        if(a==1){
            if(find(x)==find(y+n)||find(x)==find(y+2*n)){cnt++;continue;}
            unite(x,y);
            unite(x+n,y+n);
            unite(x+n*2,y+n*2);
        }else if(a==2){
            if(find(x)==find(y)||find(x)==find(y+n)){cnt++;continue;}
            unite(x+n,y);
            unite(x+2*n,y+n);
            unite(x,y+n*2);
        }
    }
    cout<<cnt<<endl;
}
例题5：P1525 [NOIP 2010 提高组] 关押罪犯

P1525 [NOIP 2010 提高组] 关押罪犯

题目背景

NOIP2010 提高组 T3

题目描述

S 城现有两座监狱，一共关押着 NN 名罪犯，编号分别为 1∼N1\sim N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 cc 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 cc 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 NN 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 N,MN,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 MM 行每行为三个正整数 aj,bj,cja_j,b_j,c_j，表示 aja_j 号和 bjb_j 号罪犯之间存在仇恨，其怨气值为 cjc_j。数据保证 1≤aj<bj≤N,0<cj≤1091\le a_j< b_j\leq N, 0 < c_j\leq 10^9，且每对罪犯组合只出现一次。

输出格式

共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出 #1

1
3512

说明/提示

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 35123512(由 22 号和 33 号罪犯引发)。其他任何分法都不会比这个分法更优。

数据范围

对于 30%30\% 的数据有 N≤15N\leq 15。

对于 70%70\% 的数据有 N≤2000,M≤50000N\leq 2000,M\leq 50000。

对于 100%100\% 的数据有 N≤20000,M≤100000N\leq 20000,M\leq 100000。

解答

分析

先将所有可能的冲突从大到小进行排序，依次解决，用并查集记录，知道有一个无法解决的就是答案。

标程

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[40005];
struct node{
    int a,b,c;
}x[100005];
bool cmp(node x,node y){
    return x.c>y.c;
}
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void unite(int x,int y){
    p[find(x)]=find(y);
}
int main(){
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=n*2;i++) p[i]=i;
    for(int i=1;i<=m;i++){
        cin>>x[i].a>>x[i].b>>x[i].c;
    }
    sort(x+1,x+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(find(x[i].a)==find(x[i].b)){cout<<x[i].c<<endl;return 0;}
        unite(x[i].a,x[i].b+n);
        unite(x[i].a+n,x[i].b);
    }
    cout<<0<<endl;
}
最小生成树

最小生成树就是无向连通图中边权和最小的一棵树。

Kruskal 算法

Kruskal算法是一种非常简单的贪心算法，原理是为了让总边权最小，从小到大连接各边，同时使用并查集保证是一棵树。

具体实现需要先将各边排序，然后检测边是否能构成一颗树，如果可以就连接。

核心代码如下：

1
2
3
4
5
6
7
8
9
10
void zuixiao(){
    sort(a+1,a+m+1,cmp); //排序各边
    for(int i=1;i<=m;i++){
        int p=find(a[i].x),q=find(a[i].y); 
        if(p==q) continue; //如果父亲相同，证明不连接这条边就已经是一棵树了
        ans+=a[i].z,cnt++; //总边权加上当前边权 边数+1
        fa[p]=q;
        if(cnt==n-1) break; //连成一棵树了直接跳出
    }
}

来做一道模板题吧！

例题1：P3366 【模板】最小生成树

P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_i，表示有一条长度为 ZiZ_i 的无向边连接结点 Xi,YiX_i,Y_i。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

1
7

说明/提示

数据规模：

对于 20%20\% 的数据，N≤5N\le 5，M≤20M\le 20。

对于 40%40\% 的数据，N≤50N\le 50，M≤2500M\le 2500。

对于 70%70\% 的数据，N≤500N\le 500，M≤104M\le 10^4。

对于 100%100\% 的数据：1≤N≤50001\le N\le 5000，1≤M≤2×1051\le M\le 2\times 10^5，1≤Zi≤1041\le Z_i \le 10^4，1≤Xi,Yi≤N1\le X_i,Y_i\le N。

样例解释：

所以最小生成树的总边权为 2+2+3=72+2+3=7。

解答

分析

模板，没什么好说的。

标程

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;
const int N=5005,M=2e5+5;
int n,m;
int fa[N];
struct node{
  int x,y,z;  
}a[M];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
    return x.z<y.z;
} 
int ans=0,cnt=0;
void zuixiao(){
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int p=find(a[i].x),q=find(a[i].y);
        if(p==q) continue;
        ans+=a[i].z,cnt++;
        fa[p]=q;
        if(cnt==n-1) break; 
    }
    
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].z;
    zuixiao();
    if(cnt<n-1) cout<<"orz"<<endl;
    else cout<<ans<<endl;
}

当然，最小生成树经过略微变形，同样可以解决最小生成森林问题。

例题2：星际纺织工

描述

小光坐在飞船的舱室中，凝望通过舷窗看到的繁星点点的宇宙。

星际间流淌着五彩的星尘，就如同梦幻场景，小光想通过这些美丽的星尘编织几个星球间的星尘丝带。

宇宙中有N个星球，小光手上有M份星际地图，每份地图描绘了哪些星球之间可以用星尘编织。

现在小光要将所有星球通过星尘编织成K个星尘丝带，一个星尘丝带至少要连接一个星球，小光想知道他怎样编织，星尘的消耗最少。

输入描述

第一行有三个数字N,M,K

接下来M行，每行包含三个数值X,Y,L，表示星球X和星球Y可以用消耗L的星尘数量编织连接。

输出描述

对每组数据输出一行，仅包含一个整数 —— 最小的消耗代价。

如果无论如何都不能编织出K个星尘丝带，请输出 No Answer。

解答

分析

显然，题意等价于要求我们生成k个最小生成树。

而我们知道因为N个点，有N−K条边即可保证形成K个连通块，所以用N-K作为结束条件即可。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,k;
int p[1005];
struct node{
    int x,y,l;  
}a[N];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
bool cmp(node x,node y){
    return x.l<y.l;
}
int cnt=0,ans=0;
void zuixiao(){
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int b=find(a[i].x),c=find(a[i].y);
        if(b==c) continue;
        cnt++;
        ans+=a[i].l;
        p[b]=c;
        if(cnt==n-k) break;
    }
    if(cnt<n-k) ans=-1;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].l;
    zuixiao();
    if(ans==-1) cout<<"No Answer";
    else cout<<ans;
    return 0;
}
快速幂

极为基础的知识点，将取幂的任务按照指数的二进制表示来分割成更小的任务

标程如下：

1
2
3
4
5
6
long long binpow(long long a,long long b,long long p) {
    if(b==0) return 1; //指数为0等于1
    long long res=binpow(a,b/2,p);
    if(b%2) return res*res%p*a%p; //奇数就再乘一个a
    return res*res%p;
}
最大公约数

常用的求最大公约数的方法有两种：

1
2
//第一种：直接使用STL，但是可能(概率不大)有bug
int x=__gcd(a,b);
1
2
3
4
5
6
//第二种：欧几里得算法，又名辗转相除法
//原理是$gcd(a,b)=gcd(b,a mod b)$
int gcd(int a,int b) {
    if(b==0) return a;
    return gcd(b,a%b);
}

如果要求最小公倍数也不难：

1
2
//第一种：直接使用STL，但是可能(概率不大)有bug
int x=__lcm(a,b);
1
2
3
4
5
//第二种：利用最大公约数进行求解
//原理是$lcm(a,b)=a*b/gcd(a,b)$
int lcm(int a,int b) {
    return a*b/gcd(a,b);
}
质数

检验质数

1
2
3
4
5
6
7
bool isprime(int x){
    if(n==1) return 0;
    for(int i=2;i<=sqrt(x);i++){ //因数肯定在sqrt(x)范围内
        if(x%i==0) return 0; //能整除就不是
    }
    return 1;
}

对于找质数，常用的不是检验的方法，而是筛法，将合数筛掉，但值得一提的是检验法是在线算法，给它一个检验一个，而筛法是离线算法，一下把范围内的质数都找出来。

找质数：埃拉托斯特尼筛法

质数的倍数一定不是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> prime;
bool isprime[N];
void findprime(int n) {
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=n;i++) isprime[i]=true;
    for(int i=2;i<=n;i++){
    if(isprime[i]){
      prime.push_back(i);
      if(i*i>n) continue; 
      for(int j=i*i;j<=n;j+=i) //2到i-1的倍数筛过了
        isprime[j]=false; //i的倍数不是质数
      }
    }
}

找质数：欧拉筛法

不难发现，埃氏筛法中很多数会被重复筛掉，例如6会被2和3都筛一次，很浪费时间，欧拉筛法(又名线性筛法)便应运而生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> prime;
bool notprime[N];
void euler(int n) {
    for(int i=2;i<=n;i++){
      if(notprime[i]==0) prime.push_back(i);
      for(int pri:prime){
        if(i*pri>n) break; // 超出范围直接搞掉
        notprime[i*pri]=true;
        if(i%pri==0) break;
        // i之前被pri筛过了
        // prime里面质数是从小到大的
	// 所以 i 乘上其他的质数一定会被pri的倍数筛掉
	// 可以break
      }
    }
}

做一道线性筛模板练手吧！

例题1：素数个数

描述

求1,2,…,N中素数的个数

输入描述

一行一个整数N

输出描述

一行一个整数，表示素数的个数。

解答

分析

欧拉筛得出范围内所有质数，然后用size得出prime大小即可。

标程

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;
const int N=1e8+5;
int n;
vector<int> prime;
bool notprime[N];
void euler() {
    for(int i=2;i<=n;i++){
      if(notprime[i]==0) prime.push_back(i);
      for(int pri:prime){
        if(i*pri>n) break;
        notprime[i*pri]=true;
        if(i%pri==0) break;
      }
    }
}
int main(){
    cin>>n;
    euler();
    cout<<prime.size();    
    return 0;
}

经过思考，我们不难发现，由于线性筛不会重复筛除，所以求质数的同时也得到了每个数的最小质因子。

例题2：B4272 [蓝桥杯青少年组省赛 2023] 质因数的个数

B4272 [蓝桥杯青少年组省赛 2023] 质因数的个数

题目背景

  • 因数：又称为约数，如果整数 aa 除以整数 b(b≠0)b(b\neq 0) 的商正好是整数而没有余数，我们就说 bb 是 aa 的因数。

  • 质数：又称为素数，一个大于 11 的自然数，除了 11 和它自身外，不能被其他自然数整除的数叫做质数。22 是最小的质数。

  • 质因数：如果一个数 aa 的因数 bb 同时也是质数，那么 bb 就是 aa 的一个质因数，例如：8=2×2×28=2\times 2\times2，22 就是 88 的质因数；12=2×2×312=2\times 2\times 3，22 和 33 就是 1212 的质因数。

题目描述

给定两个正整数 NN 和 M(1≤N≤M≤107)M(1\leq N\leq M\leq 10^7)，统计 NN 到 MM 之间（含 NN 和 MM）每个数所包含的质因数的个数，输出其中最大的个数。

例如：当 N=6,M=10N=6,M=10，66 到 1010 之间：

  • 66 的质因数是 2,32,3，共有 22 个；

  • 77 的质因数是 77，共有 11 个；

  • 88 的质因数是 2,2,22,2,2，共有 33 个；

  • 99 的质因数是 3,33,3，共有 22 个；

  • 1010 的质因数是 2,52,5，共有 22 个；

66 到 1010 之间的数中质因数最多的是 88，质因数有 33 个，故输出 33。

输入格式

输入两个正整数 NN 和 M(1≤N≤M≤107)M(1\leq N\leq M\leq 10^7)，两个正整数之间用一个空格隔开。

输出格式

输出一个整数，表示质因数个数中的最大值。

输入输出样例 #1

输入 #1

1
6 10

输出 #1

1
3
解答

分析

首先很显然可以通过线性筛筛出每个数的最小质因数，又很显然，假设i的最小质因数是p，那么i的总质因数个数等于i/p的质因数个数+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
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
vector<int> prime;
bool notprime[N];
int minprime[N];
int n,m;
int cnt[N];
void eular(){
    cnt[0] = cnt[1] = 0;
    for(int i=2;i<=m;++i){
        if(!notprime[i]) prime.push_back(i),minprime[i]=i,cnt[i]=1;
        else cnt[i]=cnt[i/minprime[i]]+1;
        for(int p:prime){
            if(i*p>m) break;
            notprime[i*p]=true;
            minprime[i*p]=p;
            if(i%p==0){break;}
        }
    }
}
int main(){
    cin>>n>>m;
    eular();
    int maxx=-1;
    for(int i=n;i<=m;i++){
        maxx=max(maxx,cnt[i]);
    }
    cout<<maxx;
    return 0;
}
裴蜀定理

裴蜀定理

很好理解，若有一个方程ax+by=d，有且只有当d为gcd(a,b)时方程才有整数解，而且可以推导出a与b互质当且仅当存在x,y满足ax+by=1.

很有趣的，裴蜀定理可以进行推广，存在整数 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_n，使得 gcd⁡(a1,a2,⋯ ,an)=a1x1+a2x2+⋯+anxn\gcd(a_1,a_2,\cdots,a_n)=a_1x_1+a_2x_2+\cdots+a_nx_n 成立。

现在来做一道简单的题吧！

例题1：裴蜀定理

描述

给定一个包含n个元素的整数序列A，记作A1,A2,A3,...,AnA_1,A_2,A_3,...,A_n 。

求另一个包含n个元素的待定整数序列X，记 S=∑i=1nAi×XiS=\sum_{i=1}^{n} A_i \times X_i，使得 S>0S>0 且 SS 尽可能的小。

输入描述

第一行一个整数n，表示序列元素个数。

第二行n个整数，表示序列A。

输出描述

一行一个整数，表示
S>0 的前提下S的最小值。

解答

分析

就是推广裴蜀定理，求出总的gcd即可。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    int ans=0;
    while(n--){
        int a;
        cin>>a;
        a=abs(a);
        ans=__gcd(a,ans);
    }
    cout<<ans;
    return 0;
}

拓展欧几里得

那么面对ax+by=gcd(a,b)时我们怎么求x和y呢？

此时我们可以使用拓展欧几里得算法！

ax1+by1=gcd⁡(a,b)ax_1+by_1=\gcd(a,b)

bx2+(a mod b)y2=gcd⁡(b,a mod b)bx_2+(a \bmod b)y_2=\gcd(b,a \bmod b)

由欧几里得定理可知：gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a \bmod b)

所以 ax1+by1=bx2+(a mod b)y2ax_1+by_1=bx_2+(a \bmod b)y_2

又因为 a mod b=a−(⌊ab⌋×b)a \bmod b=a-(\lfloor\frac{a}{b}\rfloor \times b)

所以 ax1+by1=bx2+(a−(⌊ab⌋×b))y2ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor \times b))y_2

ax1+by1=ay2+bx2−⌊ab⌋×by2=ay2+b(x2−⌊ab⌋y2)ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor \times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)

因为 a=a,b=ba=a,b=b，所以 x1=y2,y1=x2−⌊ab⌋y2x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2

将x2,y2x_2,y_2不断代入递归求解直至gcd=0,递归x=1,y=0 回去求解．

具体实现如下：

1
2
3
4
5
6
7
8
9
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
       x=1,y=1; //其实这里y可以是任意值，一般使用1或者0
       return a;
    }
    int d=exgcd(b,a%b,x,y),t=x;
    x=y,y=t-(a/b)*y; //also equals to y-=(a/b)*x;
    return d;
}

当然，既然叫exgcd，返回的d也是a和b的gcd。

还有一个问题，事实上，由于d一定是gcd(a,b)的倍数，所以我们求得的x和y其实是被等比缩小的结果，故而如果要使用时有必要进行扩倍。

线性同余方程

求解线性同余方程是裴蜀定理常见的应用。

线性同余方程就是形如𝑎𝑥≡𝑏(mod𝑛)的方程，它可以转换成ax+𝑛𝑦=𝑏.所以可以使用拓展欧几里得进行求解。

当然，只有当b是gcd(a,n)的整数倍时方程才有解。

接下来尝试写一下吧！

例题1：线性同余方程

描述

给定n组数据ai,bi,mia_i,b_i,m_i，对于每组数求出一个xix_i，使其满足ai×xi≡bi(modmi)a_i×x_i≡b_i(mod m_i)，如果无解则输出 impossible。

输入描述

第一行包含整数n。接下来n行，每行包含一组数据 ai,bi,mia_i,b_i,m_i 。

输出描述

输出共n行，每组数据输出一个整数表示一个满足条件的xix_i ，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

解答

分析

题意很好理解，写的时候注意将x扩倍即可。

标程

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a,b,m,x,y;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
signed main(){
    cin>>n;
    while(n--){
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y); //求出的是当b=gcd(a,m)时的d
        if(b%d!=0) cout<<"impossible"<<endl;
        //如果这一步判断难以理解，可以等价于if(b%__gcd(a,m)==0)
        else{ 
            cout<<(x*(b/d)%m+m)%m<<endl; 
           //由于d是a和m的gcd，所以b是gcd的若干倍，那么x当然也需要扩大同样的倍数了
        }
    }
    return 0;
}

逆元

对于非零整数a,m，如果存在b使得ab≡1(modm)ab\equiv 1\pmod m，就称b是a在模𝑚意义下的逆元。

显然，仅当gcd(a,m)=1时(即两数互质)，存在逆元，而b/d就等于1，所以逆元就是x自己，不必扩倍。

标程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a,b,x,y;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}
signed main(){
    cin>>n;
    while(n--){
        cin>>a>>b;
        int d=exgcd(a,b,x,y);
        if(d!=1) cout<<"impossible"<<endl;
        else cout<<(x%b+b)%b<<endl;
    }
    return 0;
}
RMQ问题(ST表)

RMQ问题

RMQ问题说白了就是要求快速求解区间最大值或最小值的问题，很显然，问题难度在于时间复杂度。

ST表

ST表又名稀疏表，基于倍增思想，用于求解区间性问题。如果你不知道什么是倍增，只要记住和2的幂有关，将复杂度降成log的。

在这里，我们定义一个二维数组st[N][M]，st[i][j]表示从i开始向后2j2^j个数字的最大/小值。

接下来我将讲解实现过程。

###初始化

根据定义，st表使用动态规划的初始化方式。

很显然，st[i][0]就是这个数本身，而且只有知道这个初始值才能进行之后的初始化。那么ST表的初始化就要使用双层循环，外层是j，内层是i，具体的初始化则是st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1])这样的简单方式。

计算

在进行计算从l到r的极值时可能会出现问题，那就是l和r不是2的整数次幂，这时我们可以将其分成两部分，最终答案就是两部分的最大值的最大值。

这两部分应当如何划分呢？

很显然，l和r中间总共能分到的2的次幂就是log2(r-l+1)，不妨将其定义为k。

当然，第一部分就可以是st[l][k]。

而第二部分则出现了问题，应当是从第一部分向后推还是从r向前推呢？

我们思考一下，由于C++函数下取整的缘故，st[l][k]的查询范围定然小于等于lr的范围，但是st[l][2*k]的范围又一定会超过lr的范围，这很可能会导致我们的查询出现错误，万一范围内有一个更大的数字怎么办呢对吧。所以max(st[l][k],st[l+(1<<k)+1][k])是行不通的。

那么我们考虑一下从r向前推，不难证明，r向前k个数和l向后k个数是一定能够覆盖整个范围的，且不会超过范围。虽然两者的范围可能会有重叠，但是宁多勿少嘛！

那么最终的公式就是max(st[l][k],st[r-(1<<k)+1][k])了！

接下来不妨做一道模板题吧！

例题1：P3865 【模板】ST 表 & RMQ 问题

P3865 【模板】ST 表 & RMQ 问题

题目背景

这是一道 ST 表经典题——静态区间最大值

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)O(1)。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

1
2
3
4
5
6
7
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*10+ch-48;ch=getchar();}
	return x*f;
}

函数返回值为读入的第一个整数。

快速读入作用仅为加快读入，并非强制使用。

题目描述

给定一个长度为 NN 的数列，和 M M 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 N,MN,M，分别表示数列的长度和询问的个数。

第二行包含 NN 个整数（记为 aia_i），依次表示数列的第 ii 项。

接下来 MM 行，每行包含两个整数 li,ril_i,r_i，表示查询的区间为 [li,ri][l_i,r_i]。

输出格式

输出包含 MM 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出 #1

1
2
3
4
5
6
7
8
9
9
7
7
9
8
7
9

说明/提示

对于 30%30\% 的数据，满足 1≤N,M≤101\le N,M\le 10。

对于 70%70\% 的数据，满足 1≤N,M≤1051\le N,M\le {10}^5。

对于 100%100\% 的数据，满足 1≤N≤1051\le N\le {10}^5，1≤M≤2×1061\le M\le 2\times{10}^6，ai∈[0,109]a_i\in[0,{10}^9]，1≤li≤ri≤N1\le l_i\le r_i\le N。

解答 ### 分析

模板，按照讲解做即可。

标程

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;
const int N=1e5+5;
int n,m;
int a[N],st[N][17];
void init(){
    for(int j=0;j<17;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(j==0) st[i][j]=a[i];
            else st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
void query(int l,int r){
    int k=log2(r-l+1);
    int ans=max(st[l][k],st[r-(1<<k)+1][k]);
    cout<<ans<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        query(l,r);
    }
    return 0;
}

接下来做一道实战吧！

例题2：P2880 [USACO07JAN] Balanced Lineup G

P2880 [USACO07JAN] Balanced Lineup G

题目描述

每天，农夫 John 的 n (1≤n≤5×104)n\ (1\le n\le 5\times 10^4) 头牛总是按同一序列排队。

有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 q (1≤q≤1.8×105)q\ (1\le q\le 1.8\times10^5) 个可能的牛的选择和所有牛的身高 hi (1≤hi≤106,1≤i≤n)h_i\ (1\le h_i\le 10^6,1\le i\le n)。他想知道每一组里面最高和最低的牛的身高差。

输入格式

第一行两个数 n,qn,q。

接下来 nn 行，每行一个数 hih_i。

再接下来 qq 行，每行两个整数 aa 和 bb，表示询问第 aa 头牛到第 bb 头牛里的最高和最低的牛的身高差。

输出格式

输出共 qq 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出 #1

1
2
3
6
3
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=5e4+5;
int n,q;
int h[N];
int stmax[N][17],stmin[N][17];
void init(){
    for(int j=0;j<17;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(j==0) stmax[i][j]=h[i],stmin[i][j]=h[i];
            else stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]),stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
        }
    }
}
void search(int a,int b){
    int k=log2(b-a+1);
    int maxx=max(stmax[a][k],stmax[b-(1<<k)+1][k]);
    int minn=min(stmin[a][k],stmin[b-(1<<k)+1][k]);
    cout<<maxx-minn<<endl;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>h[i];
    init();
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        search(a,b);
    }
    return 0;
}

LCA(倍增法)

LCA

LCA就是树上两点的最近公共祖先。

实现

当然，求解这个问题我们首先想到的就是朴素算法，即从两个点一个一个往上找，相交的点就是LCA。很显然，这个算法的时间复杂度直接爆炸。

我们知道一个性质，所有的自然数都可以通过若干个2的次幂相加得到，这样我们可以使用贪心算法，一次不一个一个找，而是直接向上走2的尽量多次幂。

实现时可以定义一个数组，存储第i个点向上找2j2^j的父亲点编号，利用dfs预处理解决。

详细步骤参见标程，还是挺好理解的。

标程如下：

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=5e5+5;
int n,m,s; //n是点数 m是查询数 s是根节点
vector<int> p[N]; //邻接表存树
int depth[N],fa[N][20]; //depth是各个点的深度
void dfs(int u,int parent){
    fa[u][0]=parent;
    for(int i=1;i<20;i++){ //从小到大就没有什么问题
        fa[u][i]=fa[fa[u][i-1]][i-1]; 
	//拆分成两部分，u的$2^i$的父亲就是u$2^{i-1}$这个点的$2^{i-1}$的父亲 
    }
    for(int v:p[u]){ //遍历每个子节点
        if(v!=parent){
            depth[v]=depth[u]+1; //搞定深度
            dfs(v,u); //处理子节点
        }
    }
}
int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y); //让x深于y(约定俗成的习惯)
    for(int i=19;i>=0;i--){
        if(depth[fa[x][i]]>=depth[y]){
            x=fa[x][i]; //不断让x往上走直到x和y追平
        }
    }
    if(x==y) return x; //如果平了之后是重合的那就已经到达lca
    for(int i=19;i>=0;i--){ //继续往上走
        if(fa[x][i]!=fa[y][i]){ //如果下一步不能重合
            x=fa[x][i],y=fa[y][i]; //就继续往上走
        }
    }
    //注意由于判断条件的原因结束的时候离lca还差一个点
    return fa[x][0]; //返回下一个点 即lca
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        p[a].push_back(b);
        p[b].push_back(a);
    }
    depth[s]=1; 
    dfs(s,0); //从根开始预处理
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}
树状数组

引入

有时，我们需要求解范围内的区间问题，例如我要求解1~n的任意两个数之间的前缀和，如果我将其依次相加，时间复杂度就是O(n)，但是如果我将它拆成若干个区间再合并，它的时间复杂度至少可以是O(logn)！这就是树状数组！（有点类似之前的RMQ）

使用

但是请注意，使用时一个大的结果等于若干个小的部分合并的结果，所以要求的数据必须满足结合律并且可以差分。

区间

具体区间怎么拆呢？

可以看一下OIwiki上的这个图：

事实上，c[x]的管辖区间就是x向左lowbit(x)个单位，而lowbit(x)就是x二进制最低位1以及后面的0组成的数为lowbit，例如1010100的lowbit就是100，实现如下。

1
2
3
int lowbit(int x){ //lowbit实现
    return x&-x;
}

建树

很显然，如果进行n次单点修改未免太慢了，那么正难则反，我们可以想到倒着考虑贡献，实现O(n)方案！

每次确定完儿子的值后，用自己的值更新自己的直接父亲就好了。

1
2
3
4
5
6
7
8
//数组a就是每个数，数组t是树状数组
void init(){ //建树
    for(int i=1;i<=n;i++){ //每个点依次遍历
        t[i]+=a[i]; //先加上直接点的大小
        int j=i+lowbit(i); //父亲的位置
        if(j<=n) t[j]+=t[i]; //父亲加上儿子大小
    }
}

区间查询

因为树状数组是区间储存，所以要查询lr可以将1r-1~l就可以得到要求值了。

但是怎么查询1~x呢？

其实t[x]储存的是x-lowbit(x)+1~x，那么我们可以一点点往前回溯，最后把得到的值都加起来就好了。

1
2
3
4
5
6
7
8
int getsum(int x){ //区间查询(1~x)
    int ans=0; //结果
    while(x>0){ //只要没有回到头
        ans+=t[x]; //就加上该范围的值
        x-=lowbit(x); //跳到下一个范围
    }
    return ans;
}

单点修改

显然，我们只需要不断修改父亲节点就好了，注意不要越界。

1
2
3
4
5
6
void add(int b,int c){ //单点修改
    while(b<=n){ //只要没有越界
	t[b]+=c; //该点先加上修改值
	b+=lowbit(b); //再走到父亲节点
    }
}

做一道模板题试试吧！

例题1：模板

描述

如题，已知一个数列，你需要进行下面两种操作：

  • 将某一个数加上x

  • 求出某区间每一个数的和

输入描述

第一行包含两个正整数n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来m行每行包含3个整数，表示一个操作，具体如下：

  • 1 x k含义：将第x个数加上k

  • 2 x y含义：输出区间[x,y]内每个数的和

输出描述

输出包含若干行整数，即为所有操作2的结果。

解答

分析

模板

标程

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=5e5+5;
int n,m;
int a[N],t[N];
int lowbit(int x){ //lowbit实现
    return x&-x;
}
void init(){ //建树
    for(int i=1;i<=n;i++){
        t[i]+=a[i];
        int j=i+lowbit(i);
        if(j<=n) t[j]+=t[i];
    }
}
void add(int b,int c){ //单点修改
    while(b<=n){t[b]+=c;b+=lowbit(b);}
}
int getsum(int x){ //区间查询(1~x)
    int ans=0;
    while(x>0){
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==1) add(b,c);
        else 
	cout<<getsum(c)-getsum(b-1)<<endl;
    }
    return 0;
}

区间加和

如果我们要区间加和怎么办呢？很显然依次加很慢，我们就想到了使用差分。

很显然，储存时应当直接进行差分操作。

对于区间修改：我们只需修改头与尾，即l节点+k，r+1节点-k

对于区间查询：差分的逆运算是前缀和，所以我们需要把各个点加在一起（其实没有什么区别）。

这就是区间树状数组啦！

例题2：模板

描述

如题，已知一个数列，你需要进行下面两种操作：

  • 将某区间每一个数加上x

  • 求出某一个数的值

输入描述

第一行包含两个正整数n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来m行每行包含2或4个整数，表示一个操作，具体如下：

  • 1 x y k含义：将区间[x,y]内每x个数加上k

  • 2 x 含义：输出第x个数的和

输出描述

输出包含若干行整数，即为所有操作2的结果。

解答

分析

模板

标程

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;
const int N=5e5+5;
int n,m;
int a[N]; //原始数组
int t[N]; //树状数组（存差分）
int lowbit(int x){
    return x&-x;
}
//单点修改（对差分数组）
void add(int pos,int val){
    while(pos<=n){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}
//前缀和查询（得到原数组的值）
int getsum(int pos){
    int res=0;
    while(pos>0){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    //初始化差分数组
    //差分数组d[i]=a[i]-a[i-1]
    //这里直接在树状数组中构建差分
    for(int i=1;i<=n;i++){
        add(i, a[i]-a[i-1]);
    }
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){ //区间[l,r]加k
            int l,r,k;
            cin>>l>>r>>k;
            add(l, k); //差分：l位置加k
            add(r+1, -k); //差分：r+1位置减k
        }else{ //查询第x个数的值
            int x;
            cin>>x;
            cout<<getsum(x)<<endl; //单点查询=差分数组的前缀和
        }
    }
    return 0;
}

做一道比较难的提升题吧！

例题3：P1908 逆序对

P1908 逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aja_i>a_j 且 i<ji<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update：数据已加强。

输入格式

第一行，一个数 nn，表示序列中有 nn 个数。

第二行 nn 个数，表示给定的序列。序列中每个数字不超过 10910^9。

输出格式

输出序列中逆序对的数目。

输入输出样例 #1

输入 #1

1
2
3
6
5 4 2 6 3 1

输出 #1

1
11

说明/提示

对于 25%25\% 的数据，n≤2500n \leq 2500。

对于 50%50\% 的数据，n≤4×104n \leq 4 \times 10^4。

对于所有数据，1≤n≤5×1051 \leq n \leq 5 \times 10^5。

应该不会有人 O(n2)O(n^2) 过 50 万吧 —— 2018.8 chen_zhe。

解答

分析

正难则反，从左往右找逆序对很难，可以从右往左找右边比左边小的点的个数.

使用树状数组储存每个元素的出现次数，而比某个元素小，且在它之后的元素的总数量就是该元素逆序对个数。

标程

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
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int a[N],b[N],c[N];
int lowbit(int x){
	return x&-x;
}
void add(int x,int y){
	for(int i=x;i<=m;i+=lowbit(i)){
		c[i]+=y;
	}
}
int sum(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i)){
		res+=c[i];
	}
	return res;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1); //排序
	m=unique(b+1,b+n+1)-b-1; //去除，m就是剩余的元素个数
	//以上两步共同完成离散化
	long long ans=0;
	for(int i=n;i;i--){ //遍历a数组
		int k=lower_bound(b+1,b+m+1,a[i])-b; 
		//k是a[i]在已离散化数组中的排名
		ans+=sum(k-1);
		//ans加上目前比a[i]小的元素的个数，即逆序对个数
		//因为从a的右侧开始遍历，所以目前能够查询到的点都在a[i]右侧
		add(k,1);
		//把目前点也算上
	}
	cout<<ans<<endl;
	return 0;
}
堆

引入

什么是堆？堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。说白了就是能够把其中的值自动排序，从小到大的叫小根堆，从大到小的叫大根堆。

实现

实现堆的方法有很多，我们从不常见到常见一一叙述。

STL建堆

顾名思义，使用STL的make_heap建堆，不多赘述。

手动建堆

插入：可以将要插入的点放在最后，不断向上交换直到满足权值大小要求。

删除：通常指删除根结点，将根节点与最后一个点交换，删除根节点（目前最后一个点），将目前的根节点不断向下交换直到满足权值大小要求。

以下是向上/下交换的代码，默认小根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void up(int x) {
  while(x>1&&h[x]>h[x/2]){
    swap(h[x],h[x/2]);
    x/=2;
  }
}

void down(int x) {
  while(x*2<=n){
    t=x*2;
    if(t+1<=n&&h[t+1]>h[t]) t++;
    if(h[t]<=h[x]) break;
    swap(h[x],h[t]);
    x=t;
  }
}

建堆：将每个点依次上调或者下调。

1
2
3
4
5
6
7
8
//way 1
void build1(){
  for(int i=1;i<=n;i++) up(i);
}
//way 2
void build2(){
  for(int i=n;i>=1;i--) down(i);
}

优先队列

1
2
priority_queue<int> p1; //这就是大根堆
priority_queue<int,vector<int>,greater<int>> p2; //这就是小根堆

那就来做一道简单的题吧。

例题1：P1090 [NOIP 2004 提高组] 合并果子 G

P1090 [NOIP 2004 提高组] 合并果子

题目背景

P6033 为本题加强版。

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1n-1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 11，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 33 种果子，数目依次为 11，22，99。可以先将 11、22 堆合并，新堆数目为 33，耗费体力为 33 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 1212，耗费体力为 1212。所以多多总共耗费体力 =3+12=15=3+12=15。可以证明 1515 为最小的体力耗费值。

输入格式

共两行。

第一行是一个整数 n(1≤n≤104)n(1\leq n\leq 10^4)，表示果子的种类数。

第二行包含 nn 个整数，用空格分隔，第 ii 个整数 ai(1≤ai≤2×104)a_i(1\leq a_i\leq 2\times 10^4) 是第 ii 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2312^{31}。

输入输出样例 #1

输入 #1

1
2
3
3 
1 2 9

输出 #1

1
2
15

说明/提示

对于 30%30\% 的数据，保证有 n≤103n \le 10^3；

对于 50%50\% 的数据，保证有 n≤5×103n \le 5\times10^3；

对于全部的数据，保证有 n≤104n \le 10^4。

解答

分析

用小根堆模拟即可。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int,vector<int>,greater<int> >pq;
	int n,x,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		pq.push(x);
	}
	while(pq.size()>1){
		int t=pq.top();
		pq.pop();
		t+=pq.top();
		ans+=t;
		pq.pop();
		pq.push(t);
	}
	cout<<ans<<endl;
	return 0;
}
负环

引入

在一个含有负边权的图中，如果我们要查找两点间最短路的话，可能会出现一种问题，假如图中有一个负环（就是总边权为负的环），那么因为能够不断减少总边权，通常的最短路算法就会不断地在其中绕圈，这肯定是不行的，于是就有了SPFA算法，它不仅能够判断图中是否存在负环，同时也可以求出含有负边但不含负环的图中的最短路。

值得注意的是SPFA时间复杂度高于Dijkstra算法，所以不含负边时还是应该使用Dijkstra算法。

实现

可以记录到达某一个点经过边的个数，如果多于总共边的个数说明绕圈了，也可以记录一个点入队次数，入队n次则有负环。

注意，有时给的不是一个图而是多个不相连的图，这样应该用一个循环将每个点都入队，而非只将一个点入队。

说实话，SPFA特别好卡，故有SPFA已死的说法，所以写的时候请确定必须使用SPFA。

做一道模板吧！

例题1：P3385 【模板】负环

P3385 【模板】负环

题目描述

给定一个 nn 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 TT，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 nn 和接下来给出边信息的条数 mm。

接下来 mm 行，每行三个整数 u,v,wu, v, w。

  • 若 w≥0w \geq 0，则表示存在一条从 uu 至 vv 边权为 ww 的边，还存在一条从 vv 至 uu 边权为 ww 的边。

  • 若 w<0w < 0，则只表示存在一条从 uu 至 vv 边权为 ww 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出 #1

1
2
3
NO
YES

说明/提示

数据规模与约定

对于全部的测试点，保证：

  • 1≤n≤2×1031 \leq n \leq 2 \times 10^3，1≤m≤3×1031 \leq m \leq 3 \times 10^3。

  • 1≤u,v≤n1 \leq u, v \leq n，−104≤w≤104-10^4 \leq w \leq 10^4。

  • 1≤T≤101 \leq T \leq 10。

提示

请注意，mm 不是图的边数。

解答

分析

模板，但注意本题不能将所有点先行入队。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=3e3;
int t,n,m;
struct edge{
    int v,w;
};
vector<edge> e[N];
int dis[N],cnt[N],vis[N];
//dis是到达当前点的距离，可用来求最短路
//cnt是到达该点经过的边数
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1]=1,dis[1]=0;
    while(q.empty()==0){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(edge ee:e[u]){
            int v=ee.v,w=ee.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n) return false;
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++) e[i].clear();
        cin>>n>>m;
	for(int i=1;i<=n;i++)  e[0].push_back({i,0});
        int u,v,w;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            if(w>=0) e[u].push_back({v,w}),e[v].push_back({u,w});
            else e[u].push_back({v,w});
        }
        if(spfa()) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

再实战一下吧！

例题2：P2850 [USACO06DEC] Wormholes G

P2850 [USACO06DEC] Wormholes G

题目背景

英文题面见此链接

题目描述

Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道，能将你传送到它的目的地，而且时间还会回溯到过去！FJ 的每个农场包含 N(1≤N≤500)N (1 \le N \le 500) 块编号为 1∼N1 \sim N 的田地、M(1≤M≤2500)M (1 \le M \le 2500) 条双向路径和 W(1≤W≤200)W (1 \le W \le 200) 个虫洞。

作为狂热的时间旅行爱好者，FJ 希望实现：从某块田地出发，经过若干路径和虫洞后，在初始离开时间之前回到起点。这样或许他能遇见自己 😃

为了判断可行性，FJ 将提供 F(1≤F≤5)F (1 \le F \le 5) 个农场的完整地图。所有路径通行耗时不超过 10,00010,000 秒，虫洞最多能将 FJ 带回 10,00010,000 秒前。

输入格式

第 11 行：一个整数 FF，表示农场数。后续为 FF 个农场的数据。

每个农场：

  • 第 11 行：三个空格分隔的整数 NN（田地数）, MM（双向路径数）, WW（虫洞数）。

  • 第 2∼M+12 \sim M+1 行：每行三个空格分隔的整数 (S,E,T)(S, E, T)，表示 SS 和 EE 间有一条耗时 TT 秒的双向路径。两块田地间可能存在多条路径。

  • 第 M+2∼M+W+1M+2 \sim M+W+1 行：每行三个空格分隔的整数 (S,E,T)(S, E, T)，表示一条从 SS 到 EE 的单向虫洞，可将 FJ 带回 TT 秒前。

输出格式

输出 FF 行：对每个农场，若 FJ 能达成目标输出YES，否则输出NO。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

输出 #1

1
2
NO
YES

说明/提示

  • 农场 11：FJ 无法实现时间回溯。

  • 农场 22：FJ 可通过环 1→2→3→11 \to 2 \to 3 \to 1 回到起点 11 秒前（可从环上任意点出发实现）。

翻译：DeepSeek-R1

解答

分析

注意道路是双向的，虫洞是单向的，并将所有点先行入队。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int t,n,m,w;
struct edge{
    int v,w;
};
vector<edge> e[N];
int dis[N],cnt[N],vis[N];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push_back(1);
    vis[1]=1,dis[1]=0;
    while(q.empty()==0){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(edge ee:e[u]){
            int v=ee.v,w=ee.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n){return 1;}
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return 0;
}
int main(){
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++) e[i].clear();
        cin>>n>>m>>w;
	for(int i=1;i<=n;i++)  e[0].push_back({i,0});
        int u,v,p;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>p;
            e[u].push_back({v,p});
            e[v].push_back({u,p});
        }
        for(int i=1;i<=w;i++){
            cin>>u>>v>>p;
            p-=2*p; //in fact its just p=-p;
            e[u].push_back({v,p});
        }
        if(spfa()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
差分约束

引入

差分约束就是要求你求解由若干个形如xi−xj≤ckx_i-x_j\leq c_k组成的不等式组。

解决

xi−xj≤ckx_i-x_j\leq c_k可以变形成xi≤xj+ckx_i\leq x_j+c_k,这与单源最短路中的dis[v]≤dis[u]+zdis[v]\leq dis[u]+z有相同的形式，所以我们可以把问题转化成一个图论问题，从j向i连一条边权是k的边，而xix_i的答案之一就是在这个图中从某个点到它的最短路长度。

但是在具体实现中要注意，很多时候并不是每两个未知数之间都给予了条件，所以需要使用超级源点。

注意到这样的不等式组一定能简化成形如xi≤xi+mx_i\leq x_i+m的形式，而m必须大于等于零，形式化地，图里没有负环，那么用SPFA（详见负环条目）就好了，并且SPFA里的dis数组就是结果。

这里给个标程：

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
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,m;
struct edge{
    int v,w;
};
vector<edge> e[N];
int dis[N],cnt[N],vis[N];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(0);
    vis[0]=1,dis[0]=0;
    while(q.empty()==0){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(edge ee:e[u]){
            int v=ee.v,w=ee.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n+1) return false; 
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[0].push_back({i,0});
    int uu,vv,ww;
    for(int i=1;i<=m;i++){
        cin>>uu>>vv>>ww;
        e[vv].push_back({uu,ww});
    }
    if(spfa()==false) cout<<"NO"<<endl;
    else for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}

接下来做一道简单的例题吧。

例题1：P1993 小 K 的农场

P1993 小 K 的农场

题目描述

小 K 在 MC 里面建立很多很多的农场，总共 nn 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 mm 个），以下列三种形式描述：

  • 农场 aa 比农场 bb 至少多种植了 cc 个单位的作物；

  • 农场 aa 比农场 bb 至多多种植了 cc 个单位的作物；

  • 农场 aa 与农场 bb 种植的作物数一样多。

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 nn 和 mm，分别表示农场数目和小 K 记忆中的信息数目。

接下来 mm 行：

  • 如果每行的第一个数是 11，接下来有三个整数 a,b,ca,b,c，表示农场 aa 比农场 bb 至少多种植了 cc 个单位的作物；

  • 如果每行的第一个数是 22，接下来有三个整数 a,b,ca,b,c，表示农场 aa 比农场 bb 至多多种植了 cc 个单位的作物;

  • 如果每行的第一个数是 33，接下来有两个整数 a,ba,b，表示农场 aa 种植的的数量和 bb 一样多。

输出格式

如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

1
2
3
4
5
3 3
3 1 2
1 1 3 1
2 2 3 2

输出 #1

1
2
Yes

说明/提示

对于 100%100\% 的数据，保证 1≤n,m,a,b,c≤5×1031 \le n,m,a,b,c \le 5 \times 10^3。

解答

分析

根据差分约束基本原理推理一下三种情况的建边方法即可。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,m;
struct edge{
    int v,w;
};
vector<edge> e[N];
int dis[N],cnt[N],vis[N];
bool spfa(){
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(0);
    vis[0]=1,dis[0]=0;
    while(q.empty()==0){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(edge ee:e[u]){
            int v=ee.v,w=ee.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n+1) return false;
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[0].push_back({i,0});
    int num,uu,vv,ww;
    for(int i=1;i<=m;i++){
        cin>>num;
        if(num==1){
            cin>>uu>>vv>>ww;
            e[uu].push_back({vv,-ww});
        }else if(num==2){
            cin>>uu>>vv>>ww;
            e[vv].push_back({uu,ww});
        }else if(num==3){
            cin>>uu>>vv;
            e[vv].push_back({uu,0});
            e[uu].push_back({vv,0});
        }
    }
    if(spfa()==false) cout<<"No"<<endl;
    else cout<<"Yes";
    return 0;
}
图的存储

图的存储通常来说是要存储边的起点，终点和边权，而我们有很多不同的方法实现，各有各的用途与快慢，接下来我将按照从慢到快进行介绍。

直接存边

1
2
3
4
5
6
struct edge{
  int u,v,w; //存储起点，终点和边权
};
vector<edge> e; //数组下标是边的编号
//存边：
cin>>e[i].u>>e[i].v>>e[i].w;

由于最小生成树需要记录并查集所以会使用这个算法。

邻接矩阵

1
2
3
4
vector<vector<int>> e; //e[u][v]存储从u到v的边权
//存边：
cin>>u>>v>>w;
e[u][v]=w;

可以很快地查询一条边是否存在，不能用于有重边的情况。

邻接表

1
2
3
4
5
6
7
struct edge{
  int v,w; //存储终点和边权
};
vector<edge> e[N]; //数组下标从某个点出去的第i条边
//存边：
cin>>u>>v>>w;
e[u].push_back({v,w});

几近于万能

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//建边函数
vector<int> head,nxt,to,wgt; 
//head：i的第一条边的下标，初始化为-1
//nxt：第i条边的下一条边的下标
//to：第i条边的终点
//wgt：第i条边的权值
int cnt=-1; //边数
void add(int u,int v,int w){
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    wgt[cnt]=w;
    head[u]=cnt;
}
//建边
cin>>u>>v>>w;
add(u,v,w);
//遍历u的出边
for(int i=head[u];i!=-1;i=nxt[i]){
    int v=to[i];
    .....
}

本质就是用手写的链表模拟了邻接表，非常快，也非常难写。

拓扑排序（Kahn算法）

引入

拓扑排序就是一种给有向无环图节点排序的方法，使得前面的节点不依赖后面的节点。

Kahn算法实现

维护一个入度为0的顶点的队列，将这些顶点连接的其它点的入度减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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> s[N];
int cnt[N]; //储存入度
queue<int> q; //入度为0的节点存放处
vector<int> ans;
void tuopu(){
    for(int i=1;i<=n;i++){
        if(cnt[i]==0) q.push(i); //本来入度就是0的直接存放
    }
    while(q.empty()==0){
        int p=q.front();
        q.pop(); //删去p点
        ans.push_back(p);
        for(int po:s[p]){ //p点能到达的点入度-1
            cnt[po]--;
            if(cnt[po]==0) q.push(po); 
        }
    } 
    if(ans.size()<n) cout<<-1; //存在环
    else for(int i=0;i<n;i++) cout<<ans[i]<<" ";
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        s[x].push_back(y);
        cnt[y]++;
    }
    tuopu();
    return 0;
}

做两道例题吧！

例题1：P1113 [USACO02FEB] 杂务

P1113 [USACO02FEB] 杂务

题目描述

John 的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。

当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务 11。

John 有需要完成的 nn 个杂务的清单，并且这份清单是有一定顺序的，杂务 k (k>1)k\ (k>1) 的准备工作只可能在杂务 11 至 k−1k-1 中。

写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。

输入格式

第 11 行，一个整数 n (3≤n≤10,000)n\ (3 \le n \le 10{,}000)，必须完成的杂务的数目；

第 22 至 n+1n+1 行，每行有一些用空格隔开的整数，分别表示：

  • 工作序号（保证在输入文件中是从 11 到 nn 有序递增的）；

  • 完成工作所需要的时间 len (1≤len≤100)len\ (1 \le len \le 100)；

  • 一些必须完成的准备工作，总数不超过 100100 个，由一个数字 00 结束。有些杂务没有需要准备的工作只描述一个单独的 00。

保证整个输入文件中不会出现多余的空格。

输出格式

一个整数，表示完成所有杂务所需的最短时间。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

输出 #1

1
2
23

解答

分析

由于拓扑排序性质，我们处理节点顺序就已经是最优顺序了，但是确保处理节点时将时间继承到了它的儿子上。

标程

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
vector<int> s[N];
int timee[N];
int tim[N]; //每个杂务要完成的时间
int cnt[N];
queue<int> q;
int ans=0;
void tuopu(){
    for(int i=1;i<=n;i++){
        if(cnt[i]==0) q.push(i);
    }
    while(q.empty()==0){
        int p=q.front();
        q.pop();
        for(int po:s[p]){
            cnt[po]--;
            timee[po]=max(timee[p]+tim[po],timee[po]);
            //需要将前置内容都做完，max保证此时前面该做的都做完了
            ans=max(ans,timee[po]);
            //因难以确定哪个是终点，答案就是最大值，即都做完花的时间
            if(cnt[po]==0) q.push(po); 
        }
    } 
    cout<<ans<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        cin>>tim[i];
        timee[i]=tim[i];
        while(cin>>x){
            if(x!=0){
                s[x].push_back(i);
                cnt[i]++;
            }else break;
        }
    }
    tuopu();
    return 0;
}

例题2：P4017 最大食物链计数

P4017 最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 11 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 8011200280112002 的结果。

输入格式

第一行，两个正整数 nn、mm，表示生物种类 nn 和吃与被吃的关系数 mm。

接下来 mm 行，每行两个正整数，表示被吃的生物 A 和吃 A 的生物 B。

输出格式

一行一个整数，为最大食物链数量模上 8011200280112002 的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

输出 #1

1
5

说明/提示

各测试点满足以下约定：

测试点编号 nn mm
1,21,2 ≤40\le 40 ≤400\le 400
3,43,4 ≤100\le 100 ≤2×103\le 2\times 10^3
5,65,6 ≤103\le 10^3 ≤6×104\le 6\times 10^4
7,87,8 ≤2×103\le 2\times 10^3 ≤2×105\le 2\times 10^5
9,109,10 ≤5×103\le 5\times 10^3 ≤5×105\le 5\times 10^5

对于 100%100\% 的数据，1≤n≤5×103,1≤m≤5×1051 \le n \le 5\times 10^3,1\le m \le 5\times 10^5

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE）

解答

分析

生产者入度为0，顶级消费者出度为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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=80112002,N=500005;
int n,m;
vector<int> s[N];
int cnt[N];
queue<int> q;
int ans=0;
int num[N];
void tuopu(){
    for(int i=1;i<=n;i++){
        if(cnt[i]==0){
            q.push(i);
            num[i]=1; //开始时只有1个点，食物链也为1
        } 
    }
    while(q.empty()==0){ 
        int p=q.front();
        q.pop();
        if(s[p].empty()==1){ //即出度为0
            ans+=num[p]; //答案加上到这个最高捕食者的食物链数
            ans%=MOD;
        }else
        for(int po:s[p]){
            cnt[po]--;
            num[po]+=num[p]; //食物链相加
            num[po]%=MOD;
            if(cnt[po]==0) q.push(po); 
        }
    } 
    cout<<ans%MOD;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        s[x].push_back(y);
        cnt[y]++;
    }
    tuopu();
    return 0;
}

本文作者：light5QAQ
本文链接：https://light5qaq.github.io/2026/04/06/OI%E7%AE%97%E6%B3%95%E5%A4%8D-%E5%AD%A6-%E4%B9%A0%E7%AC%94%E8%AE%B0/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
请在你的配置文件中设置 slotComment
×