【普及】算法入门学习

最后有几道难度较高的题目，可以选择性练习。

题目

P3371 【模板】单源最短路径（弱化版）
P3367 【模板】并查集
P1226 【模板】快速幂||取余运算
P1177 【模板】快速排序
P3370 【模板】字符串哈希
P3378 【模板】堆
P3383 【模板】线性筛素数
P3366 【模板】最小生成树
P4779 【模板】单源最短路径（标准版）
P3390 【模板】矩阵快速幂
P3375 【模板】KMP字符串匹配
P1195 口袋的天空
P2957 [USACO09OCT]Barn Echoes G
P1359 租用游艇
CF3A Shortest path of the king
P2105 K皇后
P1111 修复公路
P1629 邮递员送信
P5651 基础最短路练习题
P1396 营救
P1122 最大子树和
P4391 [BOI2009]Radio Transmission 无线传输
P6599 「EZEC-2」异或
P6615 草莓 Strawberry
P6686 混凝土数学
P6833 [Cnoi2020]雷雨
P6160 [Cnoi2020]向量
P6058 [加油武汉]体温调查
P6051 [RC-02] 求和
P5823 【L&K R-03】课表的排列
P5635 【CSGRound1】天下第一
P5535 【XR-3】小道消息
P6858 深海少女与胖头鱼
P6732 「Wdsr-2」方分
P6733 「Wdsr-2」间歇泉
P6786 「SWTR-6」GCDs & LCMs
P6747 『MdOI R3』Teleport
P6687 论如何玩转 Excel 表格
P6523 「Wdoi-1」加密通信
P6524 「Wdoi-1」托卡马克
P6512 [QkOI#R1] Quark and Flying Pigs
P6856 「EZEC-4.5」子序列
P6835 [Cnoi2020]线形生物
P6843 [BalticOI 2015]File Paths
P6588 『JROI-1』向量
P6748 『MdOI R3』Fallen Lord
P6830 [IOI2020]连接擎天树
P6834 [Cnoi2020]梦原
P6826 「EZEC-4」月下轻花舞
P6749 『MdOI R3』Yoshino

涉及范围

这个题单包括的算法较为丰富，其中的算法大多难度在橙到绿左右，其应用的难度更高。如果您能够将这些算法的模板反复熟记，认真尝试应用到题目中，那么你至少可以获得普及省一提高省二的成绩。

这套题单针对包括但不限于 NOIp 普及组/CSP 入门组可能涉及的算法，尝试将算法和实战结合。题目较为多元化，题目已经按照难度排序。建议大家先行学习模板，然后将尝试自行判断题目所需算法。

题目编排

题目的类型通过【模板】慢慢上升为较为复杂的应用，而【模板】的联系建议参照题解。

在这一份题单的陪伴下，你将会走入一个由普及上升至提高选手的路程，如果你能完全掌握这些算法，那么你的编程技能会得到很大的提升。每一道题都经过编者的精心（并没有）编选，保证能够获得还行的做题体验。

算法内容

涉及的算法包括：

并查集（路径压缩优化/按秩合并）

并查集，在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（ 1\sim 3 秒）内计算出试题需要的结果，只能用并查集来描述。并查集是一种树型的数据结构，用于处理一些不相交集合（\rm Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

排序（快排/堆排/优先队列）

快速排序（\rm Quicksort）是对冒泡排序的一种改进。快速排序由 \rm C. A. R. Hoare 在 1960 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
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

//已经离我们而去的 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（普里姆）算法求出。

//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）

快速幂

用递归或循环的方式将 a^n 二分转化为 a^{n\div 2}\times a^{n\div 2}，从而将 O(n) 优化为 O(\log n)。
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开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

欧拉筛法的基本思想：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

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知识清单：

附上一部分常用普及模板：

快速读入模板

//普通版本
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;
}

快速输出模板

//递归版本
inline void print(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

手写GCD

inline int gcd(int x, int y){return y?gcd(y,x%y):x;}

手写LCM

inline int lcm(int GCD,int n,int m){return n*m/GCD;}

快速幂

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

最长路模板

#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 模板

#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 模板

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

单调队列模板

#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模板

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

并查集模板

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

手写快排模板

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

埃拉托色尼素数筛

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

欧拉素数筛法

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

欧拉函数

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

线段树

#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表

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

树状数组基操

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

最后，祝大家做题愉快！