C++模板

NOI109_bjh

202人浏览 · 2025-10-25 17:56:03

NOI109_bjh · 2025-10-25 17:56:03 发布

Cpp&Cmd Template

From BJHAK

基础模板

OI

#include<bits/stdc++.h>
#define int long long
#define inf (int)0x3f3f3f3f3f3f3f3f
#define sup (int)0xc0c0c0c0c0c0c0c0
// #define pro (string)"template"

using namespace std;

void read_file();

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cout<<fixed<<setprecision(0);

	read_file();

    return 0;
}

void read_file(){
    #ifdef pro
		freopen((pro+".in").c_str(),"r",stdin);
		freopen((pro+".out").c_str(),"w",stdout);
    #endif
	
	return;
}

IOI

#include<bits/stdc++.h>
#define int long long
#define inf (int)0x3f3f3f3f3f3f3f3f
#define sup (int)0xc0c0c0c0c0c0c0c0

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cout<<fixed<<setprecision(0);

    return 0;
}

随机数据

#include<bits/stdc++.h>
#define mod (int)1e9+7

using namespace std;

signed main(){
    srand(time(0)+clock());

    cout<<(rand()%mod+1)<<'\n';

    return 0;
}

Killer

taskkill /f /im StudentMain.exe

对拍他测

#include<bits/stdc++.h>
#define data (string)"string"
#define std_ (string)"std"
#define e (int)10

using namespace std;

bool edisonba(const string num){
	system((std_+".exe < "+data+num+".in > "+std_+".out").c_str());
	
	return !system(("fc "+std_+".out "+data+num+".out").c_str());
}

signed main(){
	for(int i=1;i<=e;i++)
		if(!edisonba(to_string(i))){
			cout<<i<<'\n';
			
			break;;
		}
	
	return 0;
}
/*
std.exe < data+num.in > std.out
fc data+num.out std.out
*/

对拍自测

#include<bits/stdc++.h>
#define std_ (string)"std"
#define data (string)"data"
#define force (string)"force"
#define n (int)50

using namespace std;

bool edisonba(){
	system((data+".exe > "+std_+".in").c_str());
	system((force+".exe < "+std_+".in > "+std_+".ans").c_str());
	system((std_+".exe < "+std_+".in > "+std_+".out").c_str());
	
	return !system(("fc "+std_+".out "+std_+".ans").c_str());
}

signed main(){
	for(int i=1;i<=n;i++)
		if(edisonba()==0){
			cout<<i<<'\n';
			break;
		}
	
	return 0;
}
/*
data.exe > std.in
force.exe < std.in > std.ans
std.exe < std.in > std.out
fc std.out std.ans
*/

数据结构

并查集

const int e=1e3+10;

int n;

class unitefind_set{
    private:
        vector<int>d;
    public:
        unitefind_set(){
            d.resize(e,0);

            for(int i=1;i<e;i++)
                d[i]=i;
        }

        int find(int h){
            return d[h]==h?h:d[h]=find(d[h]);
        }

        void unite(int u,int v){
            int fu=find(u),fv=find(v);
          
            if(!same(u,v))
                d[fu]=fv;
          
            return;
        }

        bool same(int u,int v){
            int fu=find(u),fv=find(v);
          
            return fu==fv;
        }
};

堆

const int e=1e3+10;

int n;

class heap{// max_root
    private:
        vector<int>a;
        int top;
    public:
        heap(){
            a.resize(e,0);
            top=0;
        }

        void push_up(int h){
            int root=h;

            while(root>1&&a[root]>a[root/2]){
                swap(a[root],a[root/2]);
                root/=2;
            }

            return;
        }

        void push_down(int h){
            int root=h;

            while(root*2<=top){
                root*=2;

                if(root+1<=top&&a[root+1]>a[root])
                    root++;
                
                if(a[root]<=a[h])break;

                swap(a[root],a[h]);
                h=root;
            }

            return;
        }

        void insert(int x){
            a[++top]=x;
            push_up(top);

            return;
        }

        bool del(){
            if(top==0)return 0;
            
            swap(a[1],a[top]);
            top--;
            push_down(1);

            return 1;
        }
};

树状数组

差分数组初始化

const int e=1e6+10;

int n;

class tree_arr{
	private:
		vector<int>sum1,sum2;
	public:
		tree_arr(){
			sum1.resize(e,0);
			sum2.resize(e,0);
		}
		
		int f(int x){return x&-x;}
		
		void add(int h,int w){
			int nw=w*h;
			
			while(h<=n)
				sum1[h]+=w,
				sum2[h]+=nw,
				h+=f(h);
				
			return ;
		}
		
		int getsum(int h){
			int cnt1=0,cnt2=0,nh=h;
			
			while(h>=1)
				cnt1+=sum1[h],
				cnt2+=sum2[h],
				h-=f(h);
			
			return cnt1*(nh+1)-cnt2;
		}
		
		int query(int l,int r){return getsum(r)-getsum(l-1);}
};

哈希表

#define mod (int)1e5+7//自定义

using namespace std;
const int e=1e5+10;

int n;

struct node{
	int w,nxt;
};

class hash{
	private:
		int top=0;
		vector<node>a;
		vector<int>b;
	public:
		hash(){
			a.resize(e,{0,0});
			b.resize(e,0);
		}
		
		int f(int x){return x%mod+1;}
		
		void add(int w){
			int h=f(w);
      
			top++,
			a[top]={w,b[h]},
			b[h]=top;
			
			return;
		}
		
		bool find(int w){
			int h=f(w),i=b[h];

			while(i!=0){
				if(a[i].w==w)return 1;
				i=a[i].nxt;
			}
			
			return 0;
		}
};

比较运算符重载及优先队列

struct node{
	int w;
	
	bool operator < (const node &y)const{return w<y.w;}
	bool operator > (const node &y)const{return w>y.w;}
};
priority_queue<node,vector<node>,less<node> >max_root_q;
priority_queue<node,vector<node>,greater<node> >min_root_q;

数论

欧拉筛

const int e=1e3+10;

int n;
int isprime[e],prime[e],top;

void init(){
    for(int i=1;i<=n;i++)
        isprime[i]=1;
    
    return;
}

void find_prime(){
    init();

    for(int i=2;i<=n;i++){
        if(isprime[i]==1)
            prime[++top]=i;
        
        for(int j=1;j<=top&&i*prime[j]<=n;j++){
            isprime[i*prime[j]]=0;
            
            if(i%prime[j]==0)
                break;
        }
    }

    return;
}

快速幂

#define mod (int)1e9+7

int fast_pow(int x,int y){
	int res=1;
	
	while(y){
		if(y%2)
			res=res*x%mod;
		x=x*x%mod,
		y/=2;
	}
	
	return res;
}

组合数

const int e=5e3+10;

int n,m;
int dp[e][e];

int dfs(int x, int y){
	if(x<0||y<0||x<y)
        return 0;
    if(dp[x][y]!=0)
        return dp[x][y];
	if(y==0||x==y)
        return dp[x][y]=1;
    return dp[x][y]=dfs(x-1,y)+dfs(x-1,y-1);
}

二分

#define inf (int)0x3f3f3f3f

bool check(int h){//自定义
    if(h==114514)return 1;

    return 0;
}

int binary_search(){//自定义max/min返回值
    int l=1,r=inf,res=-1;

    while(l<=r){
        int mid=(l+r)/2;

        if(check(mid))
            res=mid,l=mid+1;
        else r=mid-1;
    }

    return res;
}

最大公约数

int x,y;

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

图论

多源最短路Floyd

const int e=1e3+10;

int n,m,mp[e][e];

void read(){
	memset(mp,0x3f,sizeof(mp));

	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		
		mp[u][v]=mp[v][u]=w;
	}

	return;
}

void init(){ 
    for(int i=1;i<=n;i++)
        mp[i][i]=0;
    
    return;
}

void floyd(){
	read();
	init();

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);

    return;
}

单源最短路Dijkstra

const int e=1e3+10;

int n,m;
int dis[e];
bool vis[e];

struct edge{
    int v,w;
};vector<edge>mp[e];

struct node{
    int h,w;

    bool operator < (const node &y)const{return w<y.w;}
    bool operator > (const node &y)const{return w>y.w;}
};

void init(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;

    return;
}

void dijkstra(){
    init();

    priority_queue<node,vector<node>,greater<node> >q;
    q.push({1,0});

    while(!q.empty()){
        node p=q.top();q.pop();

        if(vis[p.h])continue;
        vis[p.h]=1;

        for(edge i:mp[p.h])
            if(i.w+p.w<dis[i.v]){
                dis[i.v]=i.w+p.w;
                q.push({i.v,dis[i.v]});
            }
    }

    return;
}

最小生成树Kruskal

const int e=1e3+10;

int n,m,ans;

class uf_set{
    private:
        vector<int>d;
    public:
        uf_set(){
            d.resize(e);

            for(int i=1;i<=n;i++)
                d[i]=i;
        }

        int find(int h){
            return d[h]==h?h:d[h]=find(d[h]);
        }

        void unite(int u,int v){
            int fu=find(u),fv=find(v);
            d[fu]=fv;
            return;
        }

        bool same(int u,int v){
            int fu=find(u),fv=find(v);
            return fu==fv;
        }
};

struct edge{
    int u,v,w;

    bool operator < (const edge &y)const{return w<y.w;}
    bool operator > (const edge &y)const{return w>y.w;}
}b[e];

void kruskal(){
    uf_set a(n);
    sort(b+1,b+m+1,less<edge>());

    int cnt=0;

    for(int i=1;i<=m;i++){
        int u=b[i].u,v=b[i].v;

        if(a.same(u,v))continue;

        a.unite(u,v);
        ans+=b[i].w,cnt++;

        if(cnt==n-1)break;
    }

    if(cnt!=n-1)
        ans=-1;

    return;
}

最小生成树Prim

const int e=1e3+10;

int n,m,ans;
int dis[e];
bool vis[e];

struct edge{
    int v,w;
};vector<edge>mp[e];

struct node{
    int h,w;

    bool operator < (const node &y)const{return w<y.w;}
    bool operator > (const node &y)const{return w>y.w;}
};

void init(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;

    return;
}

void prim(){
    init();

    priority_queue<node,vector<node>,greater<node> >q;
    q.push({1,0});

    int cnt=0;

    while(!q.empty()){
        node p=q.top();q.pop();

        if(vis[p.h])continue;

        vis[p.h]=1,ans+=dis[p.h],cnt++;

        for(edge i:mp[p.h])
            if(i.w<dis[i.v]){
                dis[i.v]=i.w;
                q.push({i.v,dis[i.v]});
            }
    }

    if(cnt!=n)
        ans=-1;

    return;
}

二分图判定

const int e=1e5+10;

int n,m;
bool col[e],vis[e],flag=1;
vector<int>mp[e];

void bfs(int h){
	queue<int>q;
	q.push(h);
	
	while(!q.empty()){
		int p=q.front();q.pop();
		
		if(vis[p])continue;
		vis[p]=1;
		
		for(int i:mp[p]){
			if(vis[i]==0){
				q.push(i);
				col[i]=!col[p];
			}
			else
				if(col[i]==col[p]){
					flag=0;
					return;
				}
		}
	}
	
	return;
}

void solve(){
	for(int i=1;i<=n;i++)
		if(!vis[i])bfs(i);
	
	return;
}

拓扑排序

const int e=1e3+10;

int n,dg[e],a[e],top;
vector<int>mp[e];

void init(){
    for(int i=1;i<=n;i++)
        for(auto j:mp[i])
            dg[j]++;
    
    return;
}

void topo(){
    init();
    
    queue<int>q;

    for(int i=1;i<=n;i++)
        if(dg[i]==0)
            q.push(i);

    while(q.size()){
        int p=q.front();q.pop();

        a[++top]=p;

        for(auto i:mp[p]){
            dg[i]--;
            if(dg[i]==0)
                q.push(i);
        }
    }
    
    return;
}

树的深度

const int e=1e5+10;

int n,root,t;
int dg[e];
bool vis[e];
vector<int>mp[e];

struct node{
	int h,d,w;
};

void bfs(){
	queue<node>q;
	q.push({root,0,1});
	vis[root]=1;
	
	while(!q.empty()){
		node p=q.front();q.pop();
		
		dg[p.h]=p.w;
		
		for(int i:mp[p.h]){
			if(i==p.d||vis[i])continue;
			
			vis[i]=1;
			q.push({i,p.h,p.w+1});
		}
	}
	
	return;
}

树的重心及其最大子树

const int e=1e5+10;

int n,maxn;
int d[e],s[e],ms[e];
vector<int>mp[e];
priority_queue<int,vector<int>,greater<int> >q;

void dfs(int h,int f){
	d[h]=f,s[h]=1,ms[h]=0;
	
	for(int i:mp[h]){
		if(i==f)continue;
		dfs(i,h);
		s[h]+=s[i],ms[h]=max(ms[h],s[i]);
	}
	ms[h]=max(ms[h],n-s[h]);
	
	if(ms[h]<=n/2){
		q.push(h);
		maxn=max(maxn,ms[h]);
	}
	
	return;
}

树的直径

const int e=1e5+10;

int n,maxn,ans;
int dis[e];
vector<int>mp[e];

void dfs(int h,int d){
	for(int i:mp[h]){
		if(i==d)continue;
		
		dis[i]=dis[h]+1;
		if(dis[i]>dis[ans])
			ans=i;
		dfs(i,h);
	}
	
	return;
}

void solve(){
	dfs(1,0);
	dis[ans]=0;
	dfs(ans,0);
//	cout<<dis[ans]<<'\n';
	
	return;
}

背包

01背包

const int e=1e3+10;

int n,m,ans;
int dp[e];

struct node{
	int v,w;
}a[e];

void solve(){
	for(int i=1;i<=n;i++)
		for(int j=m;j>=a[i].v;j--)
			dp[j]=max(dp[j],dp[j-a[i].v]+a[i].w),
			ans=max(ans,dp[j]);
	
	return;
}

完全背包

const int e=1e3+10;

int n,m,ans;
int dp[e];

struct node{
	int v,w;
}a[e];

void solve(){
	for(int i=1;i<=n;i++)
		for(int j=a[i].v;j<=m;j++)
			dp[j]=max(dp[j],dp[j-a[i].v]+a[i].w),
			ans=max(ans,dp[j]);
	
	return;
}

多重背包

const int e=1e3+10;

int n,m,dp[e],top;

struct node{
    int p,w,v;
}a[e],q[e*30];

void init(){
    for(int i=1;i<=n;i++){
	    for(int j=1;j<=a[i].p;j*=2)
		    q[++top]={a[i].p,a[i].w*j,a[i].v*j},
		    a[i].p-=j;
	    if(a[i].p>0)
		    q[++top]={a[i].p,a[i].w*a[i].p,a[i].v*a[i].p};
    }
    
    return;
}

void solve(){
    init();
    
    for(int i=1;i<=top;i++)
	    for(int j=m;j>=q[i].w;j--)
	    	dp[j]=max(dp[j],dp[j-q[i].w]+q[i].v);

    return;
}