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

文章分类

一言

文章归档

最新文章

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

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

OI算法复(学)习笔记

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

构造使用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.

很有趣的，裴蜀定理可以进行推广，存在整数 𝑥1,𝑥2,⋯,𝑥𝑛x1,x2,⋯ ,xn𝑥_1,𝑥_2,⋯,𝑥_𝑛 x_1,x_2,\cdots,x_n，使得 gcd(𝑎1,𝑎2,⋯,𝑎𝑛)=𝑎1𝑥1+𝑎2𝑥2+⋯+𝑎𝑛𝑥𝑛gcd⁡(a1,a2,⋯ ,an)=a1x1+a2x2+⋯+anxngcd(𝑎_1,𝑎_2,⋯,𝑎_𝑛) =𝑎1𝑥1 +𝑎2𝑥2 +⋯ +𝑎𝑛𝑥𝑛 \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=∑^n_{i=1} A_i×X_i，使得S>0且S尽可能的小。

输入描述

第一行一个整数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呢？

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

𝑎𝑥1+𝑏𝑦1=gcd(𝑎,𝑏)𝑎𝑥1 +𝑏𝑦1 =gcd(𝑎,𝑏)

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

由欧几里得定理可知：gcd(𝑎,𝑏)=gcd(𝑏,𝑎mod𝑏)gcd(𝑎,𝑏) =gcd(𝑏,𝑎mod𝑏)

所以 𝑎𝑥1+𝑏𝑦1=𝑏𝑥2+(𝑎mod𝑏)𝑦2𝑎𝑥1 +𝑏𝑦1 =𝑏𝑥2 +(𝑎mod𝑏)𝑦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;
       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;
}
??
??
??
??

本文作者：light5QAQ
本文链接：https://light5qaq.github.io/2026/03/07/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
×