专栏文章

【模板】汇总

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mincd5ng
此快照首次捕获于
2025/12/02 00:06
3 个月前
此快照最后确认于
2025/12/02 00:06
3 个月前
查看原文

普及−\color{#F39C11}{普及-}

P1177 【模板】排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
void change(int l,int r){
	if(l>=r) return;
	int i=l,j=r,mid=a[(l+r)/2];
	while(i<j){
		while(a[i]<mid) i++;
		while(a[j]>mid) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	change(l,j);
	change(i,r);
} 
int main(){
	int n;
	cin>>n;
	for(int s=1;s<=n;s++) cin>>a[s];
	change(1,n);
	for(int s=1;s<=n;s++) cout<<a[s]<<' ';
	return 0;
}

P1226 【模板】快速幂

CPP
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long f(){
	long long ans=1;
	while(b){
		if(b&1) ans*=a;
		ans%=p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return ans;
}
int main(){
	cin>>a>>b>>p;
	cout<<a<<'^'<<b<<" mod "<<p<<'=';
	cout<<f();
	return 0;
}

P3370 【模板】字符串哈希

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int nm=1e8+30,b1=11111,b2=13131,p1=1e8+29,p2=1e8+17;
int n,ans;
bool vis[nm];
string s;
signed main(){
	st();
	cin>>n;
	while(n--){
		cin>>s;
		int a=0,b=0;
		for(int i=0;i<s.length();i++){
			a=(a*b1+s[i])%p1;
			b=(b*b2+s[i])%p2;
		}
		if(!vis[a]||!vis[b]){
			vis[a]=vis[b]=1;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

P3383 【模板】线性筛素数

CPP
#include<bits/stdc++.h>
using namespace std;
int a[10000005],n,m[100000005],top,q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		if(m[i]==0) a[++top]=i;
		for(int k=1;k*i<=n&&a[k]*i<=n;k++){
			m[a[k]*i]=1;
			if(i%a[k]==0) break;
		}
	}
	for(int i=1;i<=q;i++) cin>>m[i];
	for(int i=1;i<=q;i++) cout<<a[m[i]]<<"\n";
	return 0;
}

B3614 【模板】栈

CPP
#include<bits/stdc++.h>
using namespace std;
unsigned long long T,n,x,a[100000005],top;
string cinn;
int main(){
	cin>>T;
	for(int i=1;i<=T;i++){
		a[100000005]={};
		top=0;
		cin>>n;
		for(int j=1;j<=n;j++){
			cin>>cinn;
			if(cinn=="push"){
				cin>>x;
				a[++top]=x;
			}
			if(cinn=="pop"){
				if(top>0) top--;
				else cout<<"Empty\n";
			}
			if(cinn=="query"){
				if(top>0) cout<<a[top]<<endl;
				else cout<<"Anguei!\n";
			}
			if(cinn=="size") cout<<top<<endl;
		}
	}
	return 0;
}

B3616 【模板】队列

CPP
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,x,a[100000005],head,tail;
string cinn;
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>m;
		if(m==1) {
			cin>>x;
			a[++tail]=x;
		}
		if(m==2) {
			if(head<tail) head++;
			else cout<<"ERR_CANNOT_POP\n";
		}
		if(m==3) {
			if(head<tail) cout<<a[head+1]<<endl;
			else cout<<"ERR_CANNOT_QUERY\n";
		}
		if(m==4) cout<<tail-head<<endl;
	}
	return 0;
}

B3656 【模板】双端队列 1

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,a,x;
list<int> q[nm];
string s;
signed main(){
    st();
    cin>>n;
    while(n--){
        cin>>s>>a;
        if(s=="push_back"){
            cin>>x;
            q[a].push_back(x);
        }
        if(s=="pop_back"&&q[a].size()) q[a].pop_back();
        if(s=="push_front"){
            cin>>x;
            q[a].push_front(x);
        }
        if(s=="pop_front"&&q[a].size()) q[a].pop_front();
        if(s=="size") cout<<q[a].size()<<'\n';
        if(s=="front"&&q[a].size()) cout<<q[a].front()<<'\n';
        if(s=="back"&&q[a].size()) cout<<q[a].back()<<'\n';
    }
    return 0;
}

P10815【模板】快速读入

CPP
#include<bits/stdc++.h>
using namespace std;
int f(){
    int sum=0,flag=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') flag=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
    	sum=sum*10+c-'0';
		c=getchar_unlocked();
	}
    return sum*flag;
}
void out(int x){
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x<10) putchar(x+'0');
    else{
    	out(x/10);
		putchar(x%10+'0');
	}
}
int main(){
    int n=f(),sum=0;
    while(n--) sum+=f();
    out(sum);
    return 0;
}

普及/提高−\color{#FFC116}{普及/提高−}

P1883 【模板】三分 | 函数

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a[10005],b[10005],d[10005],T;
double g(double x){
	double m=-1e9;
	for(int i=1;i<=n;i++){
		m=max(m,a[i]*x*x+b[i]*x+d[i]);
	}
	return m;
}
double f() {
	double l=0,r=1000;
	while(r-l>=1e-9) {
		double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		if(g(mid1)<g(mid2)) r=mid2;
		else l=mid1;
	}
	return g(l);
}
int main() {
	cin>>T;
	while(T--) {
		cin>>n;
		for(int i=1; i<=n; i++) scanf("%d%d%d",&a[i],&b[i],&d[i]);
		printf("%.4lf\n",f());
	}
	return 0;
}

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

CPP
#include<bits/stdc++.h>
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e6+10;
int n,m,ans,cnt,k;
int a[nm],pos[nm],head=1,tail;
int main(){
    st();
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        while(a[i]<a[pos[tail]]&&tail>=head) tail--;
        pos[++tail]=i;
        if(pos[head]<=i-k) head++;
        if(i>=k) cout<<a[pos[head]]<<' ';
    }
    head=1,tail=0;
    cout<<'\n';
    for(int i=1;i<=n;i++){
        while(a[i]>a[pos[tail]]&&tail>=head) tail--;
        pos[++tail]=i;
        if(pos[head]<=i-k) head++;
        if(i>=k) cout<<a[pos[head]]<<' ';
    }
    return 0;
}

P3811 【模板】模意义下的乘法逆元

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int nm=3e6+10;
int n,p;
int inv[nm];
signed main(){
    cin>>n>>p;
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;i++) cout<<inv[i]<<"\n";
    return "MOD",0;
}

P4549 【模板】裴蜀定理

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int n,ans,k;
signed main(){
    st();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        if(i==1) ans=abs(k);
        else ans=__gcd(ans,abs(k));
    }
    cout<<ans;
    return 0;
}

P5788 【模板】单调栈

CPP
#include<bits/stdc++.h>
using namespace std;
const int nm=10000005;
int n,m,top;
int a[nm],b[nm],ans[nm],pos[nm];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	b[++top]=a[1];
	pos[top]=1;
	for(int i=2;i<=n;i++){
		while(a[i]>b[top]&&top){
			ans[pos[top]]=i;
			top--;
		}
		b[++top]=a[i];
		pos[top]=i;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}

P3366 【模板】最小生成树

1.prim O(n2)O(n^2)
CPP
#include<bits/stdc++.h>
using namespace std;
void st(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int nm=5005;
int n,m,ans,cnt,u,v,w;
int dis[nm],val[nm][nm],vis[nm];
signed main(){
	st();
	cin>>n>>m;
	for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) val[i][j]=INT_MAX;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		val[u][v]=val[v][u]=min(val[u][v],w);
	}
	dis[1]=0;
	for(int j=1;j<=n;j++){
		u=0;
		for(int i=1;i<=n;i++) if(!vis[i]&&(u==0||dis[i]<dis[u])) u=i;
		vis[u]=1;
		if(dis[u]==INT_MAX){
			cout<<"orz";
			return 0;
		}
		ans+=dis[u];
		for(int i=1;i<=n;i++) dis[i]=min(dis[i],val[i][u]);
	}
	cout<<ans;
	return 0;
}
2.堆优化prim
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,head[400005],to[400005],nxt[400005],val[400005],vis[400005];
int cnt;
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q;
void add(int u,int v,int w){
	cnt++;
	to[cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void tree(int x){
	q.push(P(0,1));
	while(n&&q.size()){
		int x=q.top().second,va=q.top().first;
		q.pop();
		if(vis[x]==1) continue;
		vis[x]=1;
		ans+=va;
		n--;
		for(int i=head[x];i;i=nxt[i]){
			int v=to[i];
			if(vis[v]==1) continue;
			q.push(P(val[i],v));
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,val;
		cin>>x>>y>>val;
		add(x,y,val);
		add(y,x,val);
	}
	tree(1);
	if(n!=0) cout<<"orz";
	else cout<<ans;
	return 0;
}
3.kruskal
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005],ans;
int gen(int x){
	if(fa[x]==x) return x;
	return fa[x]=gen(fa[x]);
}
bool bing(int x,int y){
	int fx=gen(x),fy=gen(y);
	if(fx==fy) return 0;
	fa[fx]=fy;
	return 1;
}
struct tree{
	int val,x,y;
}t[200005];
bool cmp(tree a,tree b){
	return a.val<b.val;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) cin>>t[i].x>>t[i].y>>t[i].val;
	sort(t+1,t+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(bing(t[i].x,t[i].y)){
			n--;
			ans+=t[i].val;
			//cout<<t[i].x<<' '<<t[i].y<<endl;
		}
		if(n==1){
			cout<<ans;
			return 0;
		}
	}
	cout<<"orz";
	return 0;
}

P3367 【模板】并查集

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005];
int gen(int x){
	if(fa[x]==x) return x;
	return fa[x]=gen(fa[x]);
}
void bing(int x,int y){
	int fx=gen(x);
	int fy=gen(y);
	if(fx==fy) return;
	fa[fx]=fy;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int z,x,y;
		cin>>z>>x>>y;
		if(z==1) bing(x,y);
		else{
			int fx=gen(x);
			int fy=gen(y);
			if(fx==fy) cout<<"Y\n";
			else cout<<"N\n";
		}
	}
	return 0;
}

P3371 【模板】单源最短路径（弱化版）

1.SPFA（Bellman–Ford的优化版本）
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,s,val[500004],dis[500004];
int vis[500004],head[500004],to[500004],nxt[500004];
void add(int u,int v,int w){
	cnt++;
	val[cnt]=w;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
typedef pair<int,int> p;
priority_queue<p,vector<p>,greater<p> > q;
void spfa(int s){
    dis[s]=0;
    q.push(p(0,s));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>val[i]+dis[u]){
                dis[v]=val[i]+dis[u];
                if(!vis[v]){
                    vis[v]=1;
                    q.push(p(dis[v],v));
                }
            }
        }
    }
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=0;i<=500003;i++) dis[i]=INT_MAX;
	spfa(s);
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}
2.Dijkstra
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt,dis[500005];
int head[500005],val[500005],to[500005],nxt[500005],vis[500005];
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q;
void add(int u,int v,int w){
	cnt++;
	to[cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void f(int x){
	dis[x]=0;
	q.push(P(0,x));
	while(q.size()){
		int u=q.top().second,w=q.top().first;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(val[i]+w>=dis[v]) continue;
			dis[v]=val[i]+w;
			q.push(P(dis[v],v));
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=0;i<=500004;i++) dis[i]=INT_MAX;
	f(s);
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}
3.Floyd 详见 B3647 【模板】Floyd
4.Johnson 详见 P5905 【模板】全源最短路（Johnson）
5.区别
最短路算法FloydBellman–Ford（SPFA）DijkstraJohnson
最短路类型全源最短路单源最短路单源最短路全源最短路
作用于任意图任意图非负权图任意图
能否检测负环能能不能能
时间复杂度O(N3)O(N^3)O(NM)O(NM)O(Mlog⁡M)O(M\log M)O(NMlog⁡M)O(NM\log M)

P3378 【模板】堆

CPP
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,p,x;
int main(){
	cin>>n;
	while(n--){
		cin>>p;
		if(p==1){
			cin>>x;
			q.push(x);
		}
		else if(p==2) cout<<q.top()<<"\n";
		else q.pop();
	}
	return 0;
}

P3379 【模板】最近公共祖先（LCA）

CPP
#include<bits/stdc++.h>
using namespace std;
const int nm=1e6+5;
int n,m,s,cnt,x,y,k;
int to[nm],head[nm],nxt[nm],d[nm],f[nm][30];
void add(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(int u,int fa){
	d[u]=d[fa]+1;
	f[u][0]=fa;
	for(int i=head[u];i;i=nxt[i]) if(!d[to[i]]) dfs(to[i],u);
}
int lca(int x,int y){
	if(d[x]<d[y]) swap(x,y);
	for(int i=k;i>=0;i--){
		if(d[f[x][i]]>=d[y]) x=f[x][i];
		if(d[x]==d[y]) break;
	}
	if(x==y) return x;
	for(int i=k;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	k=log2(n)+1;
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	f[s][0]=s;
	dfs(s,0);
	for(int i=1;i<=k;i++) for(int j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<"\n";
	}
	return 0;
}

P3385 【模板】负环

CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,m,cnt,s,val[3005],dis[3005],tot[3005];
int vis[3005],head[3005],to[3005],nxt[3005];
queue<int> q;
void add(int u,int v,int w) {
	cnt++;
	val[cnt]=w;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
bool bfs() {
	dis[1]=0;
	q.push(1);
	vis[1]=1;
	while(q.size()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u]; i; i=nxt[i]) {
			int v=to[i];
			if(val[i]+dis[u]>=dis[v]) continue;
			dis[v]=val[i]+dis[u];
			tot[v]=tot[u]+1;
			if(vis[v]==0) q.push(v);
			if(tot[v]>=n) return 0;
		}
	}
	return 1;
}
signed main() {
	cin>>T;
	while(T--) {
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(to,0,sizeof(to));
		memset(nxt,0,sizeof(nxt));
		memset(val,0,sizeof(val));
		memset(head,0,sizeof(head));
		memset(tot,0,sizeof(tot));
		cin>>n>>m;
		for(int i=1; i<=m; i++) {
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
			if(w>=0) add(v,u,w);
		}
		if(bfs()) cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

B3611 【模板】传递闭包

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
int dis[205][205];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>dis[i][j];
	for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]|=dis[i][k]&&dis[k][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cout<<dis[i][j]<<' ';
		cout<<"\n";
	}
	return 0;
}

B3644 【模板】拓扑排序 / 家谱树

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m=1,cnt;
int val[10005],to[10005],nxt[10005],head[105],du[105];
void add(int id,int nx){
	cnt++;
	to[cnt]=nx;
	nxt[cnt]=head[id];
	head[id]=cnt;
}
queue<int> q;
void tops(){
	for(int i=1;i<=n;i++) if(du[i]==0) q.push(i);
	while(q.size()){
		int x=q.front();
		cout<<x<<' ';
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int v=to[i];
			du[v]--;
			if(du[v]==0) q.push(v);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		while(m){
			add(i,m);
			du[m]++;
			cin>>m;
		}
	}
	tops();
	return 0;
}

B3647 【模板】Floyd

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=105;
int n,m,k,cnt,ans,u,v,w;
int val[nm][nm],f[nm][nm];
int main(){
    st();
    cin>>n>>m;
    memset(val,0x3f,sizeof(val));
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        val[u][v]=val[v][u]=min(val[u][v],w);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) f[i][j]=val[i][j];
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<f[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}

P3865 【模板】ST 表 & RMQ 问题

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],f[100005][25],l,r;
void g(int x,int y){
	int k=log2(n);
	for(int j=1;j<=k;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	g(1,n);
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		int k=log2(r-l+1);
		cout<<max(f[l][k],f[r-(1<<k)+1][k])<<"\n";
	}
	return 0;
}

B4324 【模板】双向链表

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,op,x,y;
int nxt[nm],lst[nm],val[nm],vis[nm];
signed main(){
    st();
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        if(i<n) nxt[i]=i+1;
        lst[i]=i-1;
    }
    nxt[0]=1;
    while(m--){
        cin>>op>>x;
        if(vis[x]) continue;
        nxt[lst[x]]=nxt[x];
        lst[nxt[x]]=lst[x];
        if(op==1){
            cin>>y;
            if(x!=y){
                lst[x]=lst[y];
                nxt[x]=y;
                nxt[lst[y]]=x;
                lst[y]=x;
            }
        }
        else if(op==2){
            cin>>y;
            if(x!=y){
                lst[x]=y;
                nxt[x]=nxt[y];
                lst[nxt[y]]=x;
                nxt[y]=x;
            }
        }
        else{
            vis[x]=1;
            n--;
        }
    }
    if(n==0) cout<<"Empty!";
    else for(int i=nxt[0];i;i=nxt[i]) cout<<i<<' ';
    return 0;
}

P4779 【模板】单源最短路径（标准版）

详见 P3371 【模板】单源最短路径（弱化版）

P8306 【模板】字典树

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void st(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int nm=3e6+10;
int t,n,cnt=1,q;
int a[nm][70],sum[nm];
string s;
int getnum(int id){
	if(s[id]-'a'>=0&&s[id]-'a'<26) return s[id]-'a';
	if(s[id]-'A'>=0&&s[id]-'A'<26) return s[id]-'A'+26;
	return s[id]-'0'+52;
}
void add(){
	int now=1;
	for(int i=0;i<s.length();i++){
		int num=getnum(i);
		if(!a[now][num]) a[now][num]=++cnt;
		now=a[now][num];
		sum[now]++;
	}
}
int query(){
	int now=1;
	for(int i=0;i<s.length();i++){
		int num=getnum(i);
		if(!a[now][num]) return 0;
		now=a[now][num];
	}
	return sum[now];
}
void solve(){
	for(int i=1;i<=cnt;i++){
		sum[i]=0;
		for(int j=0;j<=61;j++) a[i][j]=0;
	}
	cnt=1;
	cin>>n>>q;
	while(n--){
		cin>>s;
		add();
	}
	while(q--){
		cin>>s;
		cout<<query()<<'\n';
	}
}
signed main(){
	st();
	cin>>t;
	while(t--) solve();
	return 0;
}

P11615 【模板】哈希表

CPP
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
namespace fastIO
{
	char *p1,*p2,buf[100000];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
	inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
	inline void read(string&s){char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
	inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
	inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
	inline void write(const string&s){for(register int i=0;i<(int)s.size();i++){putchar(s[i]);}}
	inline void write(const char&c){putchar(c);}
}using namespace fastIO;
const int MAXN=1e7+7;
const int mod=18556744073709551616;
int base=13;
const int m=5e6;
int n;
int a[MAXN];
int vis[MAXN];
int b[MAXN];
int sum;
inline void Hash(int k,int v)
{
	int pos=k%MAXN;
	while(vis[pos]&&b[pos]!=k)
	{
		pos=(pos+1)%MAXN;
	}
	b[pos]=k;
	a[pos]=v;
	vis[pos]=1;
	
}
inline int find(int k)
{
	int pos=k%MAXN;
	while(vis[pos])
	{
		if(b[pos]==k)
		{
			return a[pos];
		}
		pos=(pos+1)%MAXN;
	}
	return 0;
}
signed main()
{
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		read(x);
		read(y);
		int ans=find(x);
		Hash(x,y);
		sum+=i*ans;
	}
	write(sum);
	
	
	return 0;
}

普及+/提高\color{#52C41A}{普及+/提高}

P2197 【模板】Nim 游戏

CPP
#include<bits/stdc++.h>
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int t,n,k,ans;
int main(){
    st();
    cin>>t;
    while(t--){
        cin>>n;
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>k;
            ans^=k;
        }
        if(ans) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

P2613 【模板】有理数取余

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nm=1e5+10;
int n,m,p=19260817;
string s1,s2;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
signed main(){
	cin>>s1>>s2;
	for(int i=0;i<s1.length();i++) n=(n*10+s1[i]-'0')%p;
	for(int i=0;i<s2.length();i++) m=(m*10+s2[i]-'0')%p;
	cout<<n*qp(m,p-2)%p;
	return 0;
}

P3368 【模板】树状数组 2

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],k,l,r,mm,b[500005];
int lowbit(int x){
    return x&(-x);
}
void update(int pos,int val){
    while(pos<=n){
        a[pos]+=val;
        pos+=lowbit(pos);
    }
}
int query(int pos){
    int sum=0;
    while(pos>0){
        sum+=a[pos];
        pos-=lowbit(pos);
    }
    return sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		update(i,b[i]-b[i-1]);
	}
	for(int i=1;i<=m;i++){
		cin>>k>>l;
		if(k==1){
			cin>>r>>mm;
			update(l,mm);
			update(r+1,-mm);
		}
		else cout<<query(l)<<endl;
	}
	return 0;
}

P3372 【模板】线段树 1

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nm=1e6+10;
int n,m,x,y,k,ans,cnt,op;
int a[nm],lazy[nm],sum[nm],l[nm],r[nm];
void pushup(int id){
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
void biuld(int id,int l,int r){
    if(l==r){
        sum[id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    biuld(id<<1,l,mid);
    biuld(id<<1|1,mid+1,r);
    pushup(id);
}
void pushdown(int id,int l,int r){
    int mid=(l+r)>>1;
    lazy[id<<1]+=lazy[id];
    lazy[id<<1|1]+=lazy[id];
    sum[id<<1]+=(mid-l+1)*lazy[id];
    sum[id<<1|1]+=(r-mid)*lazy[id];
    lazy[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
    if(tl>=l&&tr<=r){
        sum[id]+=val*(tr-tl+1);
        lazy[id]+=val;
        return;
    }
    int mid=(tl+tr)>>1;
    if(lazy[id]) pushdown(id,tl,tr);
    if(l<=mid) update(id<<1,tl,mid,l,r,val);
    if(r>mid) update(id<<1|1,mid+1,tr,l,r,val);
    pushup(id);
}
int query(int id,int tl,int tr,int l,int r){
    if(tl>=l&&tr<=r) return sum[id];
    int mid=(tl+tr)>>1,ans=0;
    if(lazy[id]) pushdown(id,tl,tr);
    if(l<=mid) ans+=query(id<<1,tl,mid,l,r);
    if(r>mid) ans+=query(id<<1|1,mid+1,tr,l,r);
    return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	biuld(1,1,n);
	while(m--){
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			update(1,1,n,x,y,k);
		}
		else cout<<query(1,1,n,x,y)<<"\n";
	}
	return 0;
}

P3373 【模板】线段树 2

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mod;
const int MAXN = 1e5+5;
int a[MAXN];
int sum[MAXN<<2],lazy[MAXN<<2],mul[MAXN<<2]; void pushup(int id){
sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
}
void pushdown(int id,int l,int r){ 
    int mid=(l+r)>>1; 
                                   sum[id<<1]=(sum[id<<1]*mul[id])%mod; 
                                   lazy[id<<1]=(lazy[id<<1]*mul[id])%mod; 
                                   mul[id<<1]=(mul[id<<1]*mul[id])%mod;

sum[id<<1|1] =(sum[id<<1|1] *mul[id])%mod;
lazy[id<<1|1]=(lazy[id<<1|1]*mul[id])%mod;
mul[id<<1|1] =(mul[id<<1|1] *mul[id])%mod;
mul[id] = 1;

sum[id<<1]=(sum[id<<1]+((mid-l+1)*lazy[id])%mod)%mod;
lazy[id<<1] = (lazy[id<<1]+lazy[id]) % mod;

sum[id<<1|1] = (sum[id<<1|1]+((r - mid)*lazy[id])%mod)% mod;
lazy[id<<1|1] = (lazy[id<<1|1]+lazy[id] ) % mod;
lazy[id]=0;
} 
void build(int id,int l,int r){ 
    mul[id]=1; 
    if(l==r){ 
        sum[id]=a[l]%mod;
        return; 
    }
    int mid=(l+r)>>1; 
    build(id<<1,l,mid); 
    build(id<<1|1,mid+1,r); 
    pushup(id); 
} 
void update(int id,int tl,int tr,int l,int r,int val){ 
    if(l<=tl&&r>=tr){ 
        sum[id]+=(tr-tl+1)*val; 
        sum[id]%=mod; 
        lazy[id]+=val; 
        lazy[id]%=mod; 
        return; 
    } 
    pushdown(id,tl,tr); 
    int mid=(tl+tr)>>1; 
    if(l<=mid) update(id<<1,tl,mid,l,r,val); 
    if(r>mid) update(id<<1|1,mid+1,tr,l,r,val); 
    pushup(id); 
} 
void update2(int id,int tl,int tr,int l,int r,int val){ 
    if(l<=tl&&r>=tr){ 
        sum[id]*=val; 
        sum[id]%=mod; 
        mul[id]*=val; 
        mul[id]%=mod; 
        lazy[id]*=val; 
        lazy[id]%=mod; 
        return;
    }
    pushdown(id,tl,tr);
    int mid=(tl+tr)>>1;
    if(l<=mid) update2(id<<1,tl,mid,l,r,val); 
    if(r>mid) update2(id<<1|1,mid+1,tr,l,r,val); 
    pushup(id); 
} 
int query(int id,int tl,int tr,int l,int r){ 
    int ans=0; 
    if(l<=tl&&r>=tr){ 
        return sum[id]; 
    } 
    pushdown(id,tl,tr); 
    int mid=(tl+tr)>>1;
    if(l<=mid) ans=(ans+query(id<<1,tl,mid,l,r))%mod; 
    if(r>mid) ans=(ans+query(id<<1|1,mid+1,tr,l,r))%mod; 
    return ans; 
} 
signed main(){

ios::sync_with_stdio(false);
cin.tie(0); 
cout.tie(0);

cin>>n>>m>>mod;
for(int i=1;i<=n;i++){
	cin>>a[i];
}
build(1,1,n);
while(m--){
	int p;
	cin>>p;
	if(p==1){
		int x,y,k;
		cin>>x>>y>>k;
		update2(1,1,n,x,y,k);
	} else if(p==2){
		int x,y,k;
		cin>>x>>y>>k;
		update(1,1,n,x,y,k);
	}
	else{
		int x,y;
		cin>>x>>y;
		cout<<query(1,1,n,x,y)%mod<<"\n";
	}
	
}
return 0;
}
//屎

P3374 【模板】树状数组 1

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],k,l,r;
int lowbit(int x){
	return x&(-x);
}
void add(int x,int y){
	while(x<=n){
		a[x]+=y;
		x+=lowbit(x);
	}
}
int q(int r){
	int ans=0;
	while(r>0){
		ans+=a[r];
		r-=lowbit(r);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>k;
		add(i,k);
	}
	for(int i=1;i<=m;i++){
		cin>>k>>l>>r;
		if(k==1) add(l,r);
		else cout<<q(r)-q(l-1)<<endl;
	}
	return 0;
}

P3375 【模板】KMP

CPP
#include<bits/stdc++.h>
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,cnt;
int nxt[nm];
string s,t;
int main(){
    st();
    cin>>s>>t;
    s=" "+s,t=" "+t;
    int slen=s.length(),tlen=t.length();
    int j=0;
    for(int i=2;i<tlen;i++){
        while(j&&t[j+1]!=t[i]) j=nxt[j];
        if(t[j+1]==t[i]) nxt[i]=++j;
    }
    j=0;
    for(int i=1;i<slen;i++){
        while(j&&t[j+1]!=s[i]) j=nxt[j];
        if(t[j+1]==s[i]) j++;
        if(j==tlen-1){
            cout<<i-tlen+2<<'\n';
            j=nxt[j];
        }
    }
    for(int i=1;i<tlen;i++) cout<<nxt[i]<<' ';
    return 0;
}

P3386 【模板】二分图最大匹配

提高+/省选−\color{#3498DB}{提高+/省选-}

省选/NOI−\color{#9D3DCF}{省选/NOI-}

NOI/NOI+/CTSC\color{#0E1D69}{NOI/NOI+/CTSC}

评论

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

正在加载评论...