专栏文章

模板题

mmengnn
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0yq9v
此快照首次捕获于
2025/12/01 18:47
3 个月前
此快照最后确认于
2025/12/01 18:47
3 个月前
查看原文
luogu 云剪切板太丑了，来整文章了。

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

1. P1177【模板】排序

<1> 冒泡排序（TLE）

CPP
#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）

CPP
#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> 归并排序

CPP
#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【模板】快速幂

CPP
#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> 手写字符串哈希

CPP
#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 哈希表

CPP
#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 优化）

CPP
#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 优化）

CPP
#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> 手写栈

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

CPP
#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> 手写队列

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

CPP
#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> 手写双端队列

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

CPP
#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）

CPP
#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() 优化快读

CPP
#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 实现快读

CPP
#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> 火车头式快读

CPP
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【模板】三分 / 函数

CPP
#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> 手写单调队列

CPP
#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; 实现单调队列

CPP
#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 算法

CPP
#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 算法

CPP
#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【模板】排序

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

1. P1177【模板】排序

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

1. P1177【模板】排序

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...