【普及】算法入门学习
题单介绍
最后有几道难度较高的题目,可以选择性练习。
## 题目
- [P3371 【模板】单源最短路径(弱化版)](https://www.luogu.com.cn/problem/P3371)
- [P3367 【模板】并查集](https://www.luogu.com.cn/problem/P3367)
- [P1226 【模板】快速幂||取余运算](https://www.luogu.com.cn/problem/P1226)
- [P1177 【模板】快速排序](https://www.luogu.com.cn/problem/P1177)
- [P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370)
- [P3378 【模板】堆](https://www.luogu.com.cn/problem/P3378)
- [P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)
- [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
- [P4779 【模板】单源最短路径(标准版)](https://www.luogu.com.cn/problem/P4779)
- [P3390 【模板】矩阵快速幂](https://www.luogu.com.cn/problem/P3390)
- [P3375 【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375)
- [P1195 口袋的天空](https://www.luogu.com.cn/problem/P1195)
- [P2957 [USACO09OCT]Barn Echoes G](https://www.luogu.com.cn/problem/P2957)
- [P1359 租用游艇](https://www.luogu.com.cn/problem/P1359)
- [CF3A Shortest path of the king](https://www.luogu.com.cn/problem/CF3A)
- [P2105 K皇后](https://www.luogu.com.cn/problem/P2105)
- [P1111 修复公路](https://www.luogu.com.cn/problem/P1111)
- [P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)
- [P5651 基础最短路练习题](https://www.luogu.com.cn/problem/P5651)
- [P1396 营救](https://www.luogu.com.cn/problem/P1396)
- [P1122 最大子树和](https://www.luogu.com.cn/problem/P1122)
- [P4391 [BOI2009]Radio Transmission 无线传输](https://www.luogu.com.cn/problem/P4391)
- [P6599 「EZEC-2」异或](https://www.luogu.com.cn/problem/P6599)
- [P6615 草莓 Strawberry](https://www.luogu.com.cn/problem/P6615)
- [P6686 混凝土数学](https://www.luogu.com.cn/problem/P6686)
- [P6833 [Cnoi2020]雷雨](https://www.luogu.com.cn/problem/P6833)
- [P6160 [Cnoi2020]向量](https://www.luogu.com.cn/problem/P6160)
- [P6058 [加油武汉]体温调查](https://www.luogu.com.cn/problem/P6058)
- [P6051 [RC-02] 求和](https://www.luogu.com.cn/problem/P6051)
- [P5823 【L&K R-03】课表的排列](https://www.luogu.com.cn/problem/P5823)
- [P5635 【CSGRound1】天下第一](https://www.luogu.com.cn/problem/P5635)
- [P5535 【XR-3】小道消息](https://www.luogu.com.cn/problem/P5535)
- [P6858 深海少女与胖头鱼](https://www.luogu.com.cn/problem/P6858)
- [P6732 「Wdsr-2」方分](https://www.luogu.com.cn/problem/P6732)
- [P6733 「Wdsr-2」间歇泉](https://www.luogu.com.cn/problem/P6733)
- [P6786 「SWTR-6」GCDs & LCMs](https://www.luogu.com.cn/problem/P6786)
- [P6747 『MdOI R3』Teleport](https://www.luogu.com.cn/problem/P6747)
- [P6687 论如何玩转 Excel 表格](https://www.luogu.com.cn/problem/P6687)
- [P6523 「Wdoi-1」加密通信](https://www.luogu.com.cn/problem/P6523)
- [P6524 「Wdoi-1」托卡马克](https://www.luogu.com.cn/problem/P6524)
- [P6512 [QkOI#R1] Quark and Flying Pigs](https://www.luogu.com.cn/problem/P6512)
- [P6856 「EZEC-4.5」子序列](https://www.luogu.com.cn/problem/P6856)
- [P6835 [Cnoi2020]线形生物](https://www.luogu.com.cn/problem/P6835)
- [P6843 [BalticOI 2015]File Paths](https://www.luogu.com.cn/problem/P6843)
- [P6588 『JROI-1』 向量](https://www.luogu.com.cn/problem/P6588)
- [P6748 『MdOI R3』Fallen Lord](https://www.luogu.com.cn/problem/P6748)
- [P6830 [IOI2020]连接擎天树](https://www.luogu.com.cn/problem/P6830)
- [P6834 [Cnoi2020]梦原](https://www.luogu.com.cn/problem/P6834)
- [P6826 「EZEC-4」月下轻花舞](https://www.luogu.com.cn/problem/P6826)
- [P6749 『MdOI R3』Yoshino](https://www.luogu.com.cn/problem/P6749)
## 涉及范围
这个题单包括的算法较为丰富,其中的算法大多难度在橙到绿左右,其应用的难度更高。如果您能够将这些算法的模板反复熟记,认真尝试应用到题目中,那么你至少可以获得普及省一提高省二的成绩。
这套题单针对包括但不限于 NOIp 普及组/CSP 入门组可能涉及的算法,尝试将算法和实战结合。题目较为多元化,题目已经按照难度排序。建议大家先行学习模板,然后将尝试自行判断题目所需算法。
## 题目编排
题目的类型通过【模板】慢慢上升为较为复杂的应用,而【模板】的联系建议参照题解。
在这一份题单的陪伴下,你将会走入一个由普及上升至提高选手的路程,如果你能完全掌握这些算法,那么你的编程技能会得到很大的提升。每一道题都经过编者的精心(并没有)编选,保证能够获得还行的做题体验。
## 算法内容
涉及的算法包括:
- 并查集(路径压缩优化/按秩合并)
> 并查集,在一些有 $N$ 个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间( $1\sim 3$ 秒)内计算出试题需要的结果,只能用并查集来描述。
并查集是一种树型的数据结构,用于处理一些不相交集合($\rm Disjoint Sets$)的合并及查询问题。常常在使用中以森林来表示。
- 排序(快排/堆排/优先队列)
> 快速排序($\rm Quicksort$)是对冒泡排序的一种改进。快速排序由 $\rm C. A. R. Hoare$ 在 $1960$ 年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
```cpp
void qsort(int l,int r){
int mid=a[(l+r)/2],i=l,j=r;
do{while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){swap(a[i],a[j]);i++;j--;}
}while(i<=j);
if(l<j)qsort(l,j);
if(i<r)qsort(i,r);
}
```
- 单源/全源最短路径($\rm Dijkstra/SPFA/Floyd$)
> Dijkstra 用于求图中指定两点之间的最短路径,或者是指定一点到其它所有点之间的最短路径。实质上是贪心算法。将图上的初始点看作一个集合 $S$,其它点看作另一个集合,根据初始点,求出其它点到初始点的距离 `d[i]` (若相邻,则 `d[i]` 为边权值;若不相邻,则 `d[i]` 为无限大)选取最小的 `d[i]`(记为 `d[x]`),并将此`d[i]`边对应的点(记为x)加入集合S。再根据 $x$,更新跟 $x$ 相邻点 $y$ 的 `d[y]` 值:`d[y] = min{ d[y], d[x] + 边权值w[x][y] }` ,因为可能把距离调小,所以这个更新操作叫做松弛操作。重复3,4两步,即可。
https://www.luogu.com.cn/training/5312
```cpp
//已经离我们而去的 SPFA
#include<bits/stdc++.h>
#define N 2<<20
#define INF 0x7fffffff
using namespace std;
int d[N],u[N],v[N],w[N],n,m,s,c;
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
for(int i=1;i<=n;i++)d[i]=INF;
d[s]=0;
for(int k=1;k<=n-1;k++){
c=0;
for(int i=1;i<=m;i++)if(d[v[i]]>d[u[i]]+w[i]){
d[v[i]]=d[u[i]]+w[i];
c=1;
}if(!c)break;
}for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}
```
- 最小生成树($\rm Kruskal/Prim$)
> 一个有 $n$ 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 $n$ 个结点,并且有保持图连通的最少的边。最小生成树可以用 kruskal(克鲁斯卡尔)算法或 prim(普里姆)算法求出。
```cpp
//Prim 算法
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5005],n,m,e[5005][5005],s,sm;
bool v[5005];
void p(){
int x;
for(int j=1;j<n;++j){
int mn=INF;
for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
v[x]=1;sm+=d[x];
for(int i=1;i<=n;i++)if(!v[i]&&e[x][i]!=INF&&d[i]>e[x][i])d[i]=e[x][i];
}
}int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
for(int i=0;i<m;i++){
int x,y,l;
cin>>x>>y>>l;
if(l<e[x][y])e[x][y]=e[y][x]=l;
}
for(int i=1;i<=n;++i)d[i]=e[1][i];
v[1]=1;p();
cout<<sm<<endl;
return 0;
}
```
- 字符串哈希($\rm Hash$)
> $\rm Hash$,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射 $\rm pre-image$)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
- 快速幂
> 用递归或循环的方式将 $a^n$ 二分转化为 $a^{n\div 2}\times a^{n\div 2}$,从而将 $O(n)$ 优化为 $O(\log n)$。
```cpp
inline int quickpow(int a,int b){
int s=1;
while(b){if(b&1)s=(s*a)%mod;a=(a*a)%mod;b>>=1;}
return s%mod;
}
```
- 欧拉筛/埃氏筛
> 埃氏筛:从2开始,将每个质数的倍数都标记成合数,以达到筛选素数的目的。
> 欧拉筛法的基本思想 :在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
```cpp
int prime[maxn];
int visit[maxn];
void Prime(){
mem(visit,0);
mem(prime, 0);
for (int i = 2;i <= maxn; i++) {
cout<<" i = "<<i<<endl;
if (!visit[i]) {
prime[++prime[0]] = i; //纪录素数, 这个prime[0] 相当于 cnt,用来计数
}
for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
// cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
visit[i*prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
}
```
## 其他内容
附录-OI知识清单:
![](https://i.loli.net/2018/07/20/5b5189649344b.png)
附上一部分常用普及模板:
## 快速读入模板
```cpp
//普通版本
inline int read(){
register int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
```
## 快速输出模板
```cpp
//递归版本
inline void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+'0');
}
```
## 手写GCD
```cpp
inline int gcd(int x, int y){return y?gcd(y,x%y):x;}
```
## 手写LCM
```cpp
inline int lcm(int GCD,int n,int m){return n*m/GCD;}
```
## 快速幂
```cpp
#define int long long
inline int qp(){
int s=1;
while(p>0){
if(p&1)s=s*b%k;
p>>=1;
b=(b*b)%k;
}return s%k;
}
```
## 最长路模板
```cpp
#include<bits/stdc++.h>
using namespace std;
#define INF 100000001
int d[2<<23],w[2<<23],n,m,mn,f[2<<23][3];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){d[i]=w[i]=INF;f[i][1]=f[i][2]=0;}
for(int i=1;i<=m;i++){
int x,y,l;
cin>>x>>y>>l;
f[i][1]=x,f[i][2]=y,w[i]=-l;
}d[1]=0;
for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)d[f[j][2]]=min(d[f[j][2]],d[f[j][1]]+w[j]);
if(d[n])printf("%d",-d[n]);
else puts("-1");
return 0;
}
```
## SPFA 模板
```cpp
#include<bits/stdc++.h>
#define N 2<<20
#define INF 0x7fffffff
using namespace std;
int d[N],u[N],v[N],w[N],n,m,s,c;
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
for(int i=1;i<=n;i++)d[i]=INF;
d[s]=0;
for(int k=1;k<=n-1;k++){
c=0;
for(int i=1;i<=m;i++)if(d[v[i]]>d[u[i]]+w[i]){
d[v[i]]=d[u[i]]+w[i];
c=1;
}if(!c)break;
}for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}
```
## Prim 模板
```cpp
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5005],n,m,e[5005][5005],s,sm;
bool v[5005];
void p(){
int x;
for(int j=1;j<n;++j){
int mn=INF;
for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
v[x]=1;sm+=d[x];
for(int i=1;i<=n;i++)if(!v[i]&&e[x][i]!=INF&&d[i]>e[x][i])d[i]=e[x][i];
}
}int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
for(int i=0;i<m;i++){
int x,y,l;
cin>>x>>y>>l;
if(l<e[x][y])e[x][y]=e[y][x]=l;
}
for(int i=1;i<=n;++i)d[i]=e[1][i];
v[1]=1;p();
cout<<sm<<endl;
return 0;
}
```
## 单调队列模板
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,q1[2<<25],q2[2<<25],a[2<<25];
int minque(){
int h=1,t=0;
for(int i=1;i<=n;i++){
while(h<=t&&q1[h]+m<=i)++h;
while(h<=t&&a[i]<a[q1[t]])t--;
q1[++t]=i;
if(i>=m)printf("%d ",a[q1[h]]);
}cout<<endl;
}int maxque(){
int h=1,t=0;
for(int i=1;i<=n;i++){
while(h<=t&&q2[h]+m<=i)h++;
while(h<=t&&a[i]>a[q2[t]])t--;
q2[++t]=i;
if(i>=m)printf("%d ",a[q2[h]]);
}
}int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
minque();maxque();
return 0;
}
```
## 朴素Dijkstra模板
```cpp
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5001],n,m,edge[5001][5001],mn,x,s;
bool v[5001];
void dijkstra(){
for(int j=1;j<n;++j){
mn=INF;
for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
v[x]=1;
for(int i=1;i<=n;i++)if(e[x][i]!=INF){int t=e[x][i]+d[idx];if(d[i]>t)d[i]=t;}
}
}int main(){
cin>>n>>m>>s;
for(int i=1;i<=n;i++)for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
for(int i=0;i<m;i++){int x,y,l;cin>>x>>y>>l;e[x][y]=l;}
for(int i=1;i<=n;++i)d[i]=e[s][i];
v[s]=1;dijkstra();
for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}
```
## 并查集模板
```cpp
inline int fd(int k){
if(f[k]==k)return k;
return f[k]=fd(f[k]);
}inline void mr(int v,int u){
int t1=fd(v),t2=fd(u);
if(t1!=t2)f[t2]=t1;
}
```
## 手写快排模板
```cpp
void qsort(int l,int r){
int mid=a[(l+r)/2],i=l,j=r;
do{while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){swap(a[i],a[j]);i++;j--;}
}while(i<=j);
if(l<j)qsort(l,j);
if(i<r)qsort(i,r);
}
```
## 埃拉托色尼素数筛
```cpp
inline void Era(){
int m=sqrt(n+0.5);
for(register int i=2;i<=m;++i)if(!vis[i])for(register int j=i*i;j<=n;j+=i)vis[j]=1;
}
```
## 欧拉素数筛法
```cpp
bool n[2<<32];int p[2<<24],c;
void w(int n){
for(int i=2;i<=n;++i){
if(!n[i])p[++c]=i ;
for(int j=1;j<=c&&i*p[j]<=n;++j){
n[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
```
## 欧拉函数
```cpp
#define MAX 20005
int phi[MAX],prime[v],tot;
bool b[MAX];
void getphi(){
phi[1]=1;
for(int i=2;i<=MAX;i++){
if(!b[i]){
prime[++tot]=i;
phi[i]=i-1;
}for(int j=1;j<=tot;j++){
if(i*prime[j]>MAX)break;
b[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
```
## 线段树
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200002],n,m,T,d[1000005],b[1000005];
void build(int s,int t,int p){
if(s==t){
d[p]=a[s];
return;
}int m=(s+t)/2;
build(s,m,p*2);
build(m+1,t,p*2+1);
d[p]=d[p*2]+d[p*2+1];
}void update(int l,int r,int c,int s,int t,int p){
if(l<=s&&t<=r){
d[p]+=(t-s+1)*c;
b[p]+=c;
return;
}int m=(s+t)/2;
if(b[p]&&s!=t){
d[p*2]+=b[p]*(m-s+1);
d[p*2+1]+=b[p]*(t-m);
b[p*2]+=b[p];b[p*2+1]+=b[p];
b[p]=0;
}if(l<=m)update(l,r,c,s,m,p*2);
if(r>m)update(l,r,c,m+1,t,p*2+1);
d[p]=d[p*2]+d[p*2+1];
}int getsum(int l,int r,int s,int t,int p){
if(l<=s&&t<=r)return d[p];
int m=(s+t)/2;
if(b[p]){
d[p*2]+=b[p]*(m-s+1);
d[p*2+1]+=b[p]*(t-m);
b[p*2]+=b[p];
b[p*2+1]+=b[p];
b[p]=0;
}int sum=0;
if(l<=m)sum=getsum(l,r,s,m,p*2);
if(r>m)sum+=getsum(l,r,m+1,t,p*2+1);
return sum;
}signed main(){
cin>>n>>m;
int x,y,op,k;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,n,1);
for(int i=0;i<m;i++){
cin>>op;
if(op==1){
cin>>x>>y>>k;
update(x,y,k,1,n,1);
}if(op==2){
cin>>x>>y;
cout<<getsum(x,y,1,n,1)<<endl;
}
}return 0;
}
```
## ST表
```cpp
#include<bits/stdc++.h>
#define isdigit(x) ('0'<=x&&x<='9')
#define max(x,y) (x>y?x:y)
using namespace std;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}int n,m,a[2000001],f[2000001][21],x,y;
void pre() {
a[1]=0;a[2]=1;
for(register int i=3;i<200001;i++)a[i]=a[i>>1]+1;
}int main(){
n=rd();m=rd();
for(register int i=1;i<=n;i++)f[i][0]=rd();
pre();
for(register int j=1;j<=21;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
for(register int i=1;i<=m;i++){
x=rd();y=rd();
int s=a[y-x+1];
printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
}return 0;
}
```
## 树状数组基操
```cpp
int lowbit(int x){
return x&-x;
}void add(int x,int k){//单点修改
while(x<=n){//当在最大区间范围内时
c[x]=c[x]+k;//对当前节点进行修改
x=x+lowbit(x);//“跳跃”到下一个节点
}
}int getsum(int x){//求a1,a2,a3……ax的和
int ans=0;
while(x>=1){//当x在给定范围内
ans+=c[x];//求和
x-=lowbit(x);//跳跃到下一个节点
}return ans;
}inline void init(){//O(n)建树
for(int i=1;i<=n;++i){
t[i]+=a[i];
int j=i+lowbit(i);
if(j<=n)t[j]+=t[i];
}
}
```
最后,祝大家做题愉快!