模板题

· · 算法·理论

luogu 云剪切板太丑了，来整文章了。

一. \boxed{\color{#F39C11}{普及-}} 难度

1. P1177【模板】排序

<1> 冒泡排序（TLE）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++)
        for (int j=1;j<n;j++)
            if (a[j]>a[j+1])
                swap(a[j],a[j+1]);
    for (int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    return 0;
}

<2> 快速排序（TLE）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
inline void QSort(int l,int r){
    if (l>r) return ;
    int i=l,j=r,temp;
    temp=a[l];
    for (;i!=j;){
        for (;a[j]>=temp&&i<j;j--);
        for (;a[i]<=temp&&i<j;i++);
        if (i<j) swap(a[i],a[j]);
    }
    a[l]=a[i];
    a[i]=temp;
    QSort(l,i-1);
    QSort(i+1,r);
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    QSort(1,n);
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

<3> 归并排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N];
inline void QSort(int l,int r){
    if (l>=r) return ;
    int mid=(l+r)>>1;
    QSort(l,mid);
    QSort(mid+1,r);
    int i=l,j=mid+1,top=0;
    for (;i<=mid&&j<=r;)
        if (a[i]<=a[j]) b[++top]=a[i++];
        else b[++top]=a[j++];
    for (;i<=mid;) b[++top]=a[i++];
    for (;j<=r;) b[++top]=a[j++];
    for (int k=l;k<=r;k++)
        a[k]=b[k-l+1]; 
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    QSort(1,n);
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

2. P1226【模板】快速幂

#include <bits/stdc++.h>
using namespace std;
long long a,b,m;
inline long long power(long long a,long long b,long long m){
    long long res=1;
    for (long long k=a;b;b>>=1,k=(k*k)%m)
        if (b&1) res=(ans*k)%m;
    return res;
}
int main(){
    cin>>a>>b>>m;
    printf("%lld^%lld mod %lld=%lld",a,b,m,power(a,b,m));
    return 0;
}

3. P3370【模板】字符串哈希

<1> 手写字符串哈希

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=1505;
const int bas=131;
typedef unsigned long long ull;
struct Hash{
    ull hsh[M],p[M]={1};
    inline ull insert(string &s){
        int n=s.size();
        for (int i=0;i<n;i++){
            hsh[i]=hsh[i-1]*bas+s[i];
            p[i]=p[i-1]*bas;
        }
        return hsh[n-1];
    }
    inline ull get(int l,int r){
        return hsh[r]-hsh[l-1]*p[r-l+1];
    }
}st;
int n,ans;
ull a[N];
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        string s;cin>>s;
        a[i]=st.insert(s);
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++)
        if (a[i]!=a[i-1])
            ++ans;
    cout<<ans;
    return 0;
}

<2> pbds 哈希表

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int N=10005,M=1505;
typedef unsigned long long ull;
int n,ans;
gp_hash_table<string,bool> mp;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        string s;cin>>s;
        mp[s]=true;
    }
    cout<<mp.size();
    return 0;
}

4. P3383【模板】线性筛质数

<1> 埃氏筛（bitset 优化）

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int n,q;
int top=0,prime[N];
bitset<N> isprime;
inline void init(){
    isprime[0]=isprime[1]=1;
    for (int i=2;i<=N-5;i++)
        if (!isprime[i]){
            prime[++top]=i;
            for (int j=i+i;j<=n;j+=i)
                isprime[j]=1;
        }
}
int main(){
    cin>>n>>q; 
    init();
    for (int i=1,x;i<=q;i++){
        cin>>x;
        cout<<prime[x]<<'\n';
    }
    return 0;
}

<2> 欧拉筛（bitset 优化）

#include <bits/stdc++.h>
using namespace std;
const int N=1e8+5;
int n,q;
int top,prime[N];
bitset<N> isprime;
inline void init(){
    isprime[0]=isprime[1]=1;
    for (int i=2;i<=N-5;i++){
        if (!isprime[i])
            prime[++top]=i;
        for (int j=1;j<=top&&prime[j]*i<=n;j++){
            isprime[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}
int main(){
    cin>>n>>q;
    init();
    while (q--){
        int x;cin>>x;
        cout<<prime[x]<<'\n';
    }
    return 0;
}

5. B3614【模板】栈

<1> 手写栈

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+5;
int T,n,top;
ull st[N];
int main(){
    cin>>T;
    while(T--){
        cin>>n;top=0;
        while(n--){
            string op;cin>>op;
            if(op[2]=='s'){
                ull x;cin>>x;
                st[++top]=x;
            }else if(op[2]=='p'){
                if(!top) puts("Empty");
                else --top;
            }else if(op[2]=='e'){
                if(!top) puts("Anguei!");
                else cout<<st[top]<<'\n';
            }else cout<<top<<'\n';
        }
    }
    return 0;
}

<2> STL stack<T> st;

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int T,n;
stack<ull> st;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        while (!st.empty()) st.pop();
        while(n--){
            string op;cin>>op;
            if(op[2]=='s'){
                ull x;cin>>x;
                st.push(x);
            }else if(op[2]=='p'){
                if(st.empty()) puts("Empty");
                else st.pop();
            }else if(op[2]=='e'){
                if(st.empty()) puts("Anguei!");
                else cout<<st.top()<<'\n';
            }else cout<<st.size()<<'\n';
        }
    }
    return 0;
}

6. B3616【模板】队列

<1> 手写队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,q[N],l=1,r=0;
int main(){
    cin>>n;
    while(n--){
        int op;cin>>op;
        if(op==1){
            int x;cin>>x;
            q[++r]=x;
        }else if(op==2){
            if(l>r) puts("ERR_CANNOT_POP");
            else ++l;
        }else if(op==3){
            if(l>r) puts("ERR_CANNOT_QUERY");
            else cout<<q[l]<<'\n';
        }else cout<<r-l+1<<'\n';
    }
    return 0;
}

<2> STL queue<T> q;

#include<bits/stdc++.h>
using namespace std;
int n;
queue<int> q;
int main(){
    cin>>n;
    while(n--){
        int op;cin>>op;
        if(op==1){
            int x;cin>>x;
            q.push(x);
        }else if(op==2){
            if(q.empty()) puts("ERR_CANNOT_POP");
            else q.pop();
        }else if(op==3){
            if(q.empty()) puts("ERR_CANNOT_QUERY");
            else cout<<q.front()<<'\n';
        }else cout<<q.size()<<'\n';
    }
    return 0;
}

7. U635560【模板】双端队列

<1> 手写双端队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q[N<<1],l=N+1,r=N;
int main(){
    cin>>n;
    while (n--){
        string op;cin>>op;
        if (op[1]=='i') cout<<r-l+1<<'\n';
        else if (op[1]=='r'){
            if (l<=r) cout<<q[l]<<'\n';
        }else if (op[1]=='a'){
            if (l<=r) cout<<q[r]<<'\n';
        }else if (op[1]=='u'){
            int x;cin>>x;
            if (op[5]=='f') q[--l]=x;
            else q[++r]=x;
        }else{
            if (l>r) continue;
            if (op[4]=='f') ++l;
            else --r;
        }
    }
    return 0;
}

<2> STL deque<T> q;

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n;deque<int> q;
int main(){
    cin>>n;
    while (n--){
        string op;cin>>op;
        if (op[1]=='i') cout<<q.size()<<'\n';
        else if (op[1]=='r'){
            if (!q.empty()) cout<<q.front()<<'\n';
        }else if (op[1]=='a'){
            if (!q.empty()) cout<<q.back()<<'\n';
        }else if (op[1]=='u'){
            int x;cin>>x;
            if (op[5]=='f') q.push_front(x);
            else q.push_back(x);
        }else{
            if (q.empty()) continue;
            if (op[4]=='f') q.pop_front();
            else q.pop_back();
        }
    }
    return 0;
}

8. P10815【模板】快速读入

<1> 普通快读（TLE）

#include<bits/stdc++.h>
using namespace std;
typename<typename T>inline void rd(T &x){
    x=0;char ch;bool f=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if (ch=='-') f=true;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
typename<typename T>inline void wr(T x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
int n;
long long x,ans;
int main(){
    rd(n);
    while (n--){rd(x);ans+=x;}
    wr(ans);
    return 0;
}

<2> getchar_unlocked() 优化快读

#include<bits/stdc++.h>
using namespace std;
typename<typename T>inline void rd(T &x){
    x=0;char ch;bool f=false;
    for(ch=getchar_unlocked()();ch<'0'||ch>'9';ch=getchar_unlocked()())
        if (ch=='-') f=true;
    for(;ch>='0'&&ch<='9';ch=getchar_unlocked()())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
typename<typename T>inline void wr(T x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
int n;
long long x,ans;
int main(){
    rd(n);
    while (n--){rd(x);ans+=x;}
    wr(ans);
    return 0;
}

<3> fread 实现快读

#include<bits/stdc++.h>
using namespace std;
static char buf[100000],*pa(buf),*pb(buf);
template<typename T>inline void rd(T &x) {
    x=0;register bool f=false;register char c;
    for (c=pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++;c<'0'||c>'9';c=pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++) f|=(c=='-');
    for (;c>='0'&&c<='9';c=pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++) x=(x<<3)+(x<<1)+(c&15);
    x=(f?-x:x);
}
template<typename T>inline void wr(T x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
int n;
long long x,ans;
int main(){
    rd(n);
    while (n--){rd(x);ans+=x;}
    wr(ans);
    return 0;
}

<4> 火车头式快读

namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar_unlocked();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar_unlocked();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar_unlocked();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar_unlocked();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar_unlocked();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar_unlocked();if(c=='.')c=getchar_unlocked();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar_unlocked();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar_unlocked();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar_unlocked();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar_unlocked();if(c=='.')c=getchar_unlocked();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar_unlocked();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar_unlocked();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar_unlocked();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar_unlocked();if(c=='.')c=getchar_unlocked();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar_unlocked();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar_unlocked();while(c==' '||c=='\n'||c=='\r')c=getchar_unlocked();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar_unlocked();while(c==' '||c=='\n'||c=='\r')c=getchar_unlocked();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar_unlocked();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar_unlocked();while(c==' '||c=='\n'||c=='\r')c=getchar_unlocked();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar_unlocked();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define file(x) {freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);}

二. \boxed{\color{#FFC116}{普及/提高-}} 难度

1. P1883【模板】三分 / 函数

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const double eps=1e-9;
int T,n;
double a[N],b[N],c[N];
inline double f(double x){
    double ans=-1e18;
    for (int i=1;i<=n;i++)
        ans=max(ans,x*x*a[i]+x*b[i]+c[i]);
    return ans;
}
int main(){
    cin>>T;
    while (T--){
        cin>>n;
        for (int i=1;i<=n;i++)
            cin>>a[i]>>b[i]>>c[i];
        double l=0,r=1e3,lm,rm;
        while (r-l>eps){
            double mid=(r-l)/3.0;
            lm=l+mid;
            rm=r-mid;
            if (f(lm)<f(rm)) r=rm;
            else l=lm;
        }
        printf("%.4lf\n",f(r));
    }
    return 0;
}

2. P1886【模板】单调队列 / 滑动窗口

<1> 手写单调队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N],q[N<<1],l=0,r=-1;
int mi[N],ma[N];
inline void init1(){
    for (int i=1;i<=n;i++){
        while (l<=r&&i-q[l]+1>m) ++l;
        while (l<=r&&a[q[r]]>a[i]) --r;
        q[++r]=i;
        mi[i]=a[q[l]];
    }
}
inline void init2(){
    l=0;r=-1;
    for (int i=1;i<=n;i++){
        while (l<=r&&i-q[l]+1>m) ++l;
        while (l<=r&&a[q[r]]<a[i]) --r;
        q[++r]=i;
        ma[i]=a[q[l]];
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    init1();init2();
    for (int i=m;i<=n;i++) cout<<mi[i]<<' ';puts("");
    for (int i=m;i<=n;i++) cout<<ma[i]<<' ';puts("");
    return 0;
}

<2> STL deque<T> q; 实现单调队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
int mi[N],ma[N];
deque<int> q;
inline void init1(){
    while (!q.empty()) q.pop_back();
    for (int i=1;i<=n;i++){
        while (!q.empty()&&i-q.front()+1>m) q.pop_front();
        while (!q.empty()&&a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        mi[i]=a[q.front()];
    }
}
inline void init2(){
    while (!q.empty()) q.pop_back();
    for (int i=1;i<=n;i++){
        while (!q.empty()&&i-q.front()+1>m) q.pop_front();
        while (!q.empty()&&a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        ma[i]=a[q.front()];
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    init1();init2();
    for (int i=m;i<=n;i++) cout<<mi[i]<<' ';puts("");
    for (int i=m;i<=n;i++) cout<<ma[i]<<' ';puts("");
    return 0;
}

2. P3366【模板】最小生成树

<1> Prim 算法

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
struct Edge{
    int y,v;
    inline bool operator<(const Edge &e) const{
        return v>e.v;
    }
};
int n,m,dis[N];
bool vis[N]={};
vector<Edge> e[N];
inline void Prim(){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<Edge> q;
    q.push({1,dis[1]=0});
    int cnt=0,ans=0;
    while (!q.empty()){
        Edge t=q.top();q.pop();
        if (vis[t.y]) continue;
        vis[t.y]=true;
        ++cnt;ans+=t.v;
        for (auto [y,v]:e[t.y])
            if (dis[y]>v){
                dis[y]=v;
                if (!vis[y]) q.push({y,v});
            }
    }
    if (cnt==n) cout<<ans;
    else puts("orz");
}
int main(){
    cin>>n>>m;
    while (m--){
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    Prim();
    return 0;
}

<2> Kruskul 算法

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=2e5+5;
struct node{
    int x,y,v;
    bool operator<(const node &A)const{
        return v <A.v;
    }
}a[M];
int n,m,f[N];
inline int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
inline int Kruskal(){
    for (int i=1;i<=n;i++) f[i]=i;
    sort(a+1,a+m+1);
    int ans=0,cnt=0;
    for (int i=1;i<=m;i++){
        int x=find(a[i].x),y=find(a[i].y);
        if (cnt==n-1) return ans; 
        if (x!=y){
            f[x]=y;
            ans+=a[i].v;
            ++cnt;
        }
    }
    return (cnt==n-1?ans:-1);
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[i].x=x;a[i].y=y;a[i].v=z;
    }
    int k=Kruskal();
    if (k==-1) puts("orz");
    else cout<<k;
    return 0;
}

三. \boxed{\color{#52C41A}{普及+/提高}} 难度

1. P1177【模板】排序

四. \boxed{\color{#3498DB}{提高+/省选-}} 难度

1. P1177【模板】排序

五. \boxed{\color{#8A3EB3}{省选/NOI-}} 难度

1. P1177【模板】排序

六. \boxed{\color{#151F56}{NOI/NOI+/CTSC}} 难度

1. P1177【模板】排序