c++基本全框架（基础）

userId_undefined
IOI的神
时间刺客时空双修者空间掌握者出道萌新秩序白银快乐小狗

2026-08-07 16:07:18

发布于：上海

9阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
using PII=pair<int,int>;
using PLL=pair<ll,ll>;
using PIPII=pair<int,PII>;
using PPIIPII=pair<PII,PII>;
using PLPLL=pair<ll,PLL>;
using PPLLPLL=pair<PLL,PLL>;

const int MOD=1e9+7;
const int MAXN=2e5+9;
const int MAXM=2e5+9;

int null;
ll Null;
PII NonE;
PLL NOne;
string NUll;
char NULl;
bool nULl;
vector<int> nULL;
map<int,int> nuLL;
set<int> nulL;
stack<int> nUlL;
queue<int> NuLl;
deque<int> NuLL;
priority_queue<int> NulL;
multiset<int> NUlL;

//快速幂
ll Quick_Power(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
//快速幂

struct node{
    
};

bool operator<(const node &x,const node &y){
    
    return 0;
}

//树状数组
int TA_lowbit(int x){return x&-x;}

int TA_a[MAXN],TA_n;

void TA_add(int x,int b){
    for(int i=x;i<=TA_n;i+=TA_lowbit(i))TA_a[i]+=b;
}

int TA_query(int x){
    int res=0;
    for(int i=x;i>=1;i-=TA_lowbit(i))res+=TA_a[i];
    return res;
}
//树状数组

//排列组合数
ll AC_fac[MAXN],AC_ifac[MAXN];

void AC_Ready(){
    AC_fac[0]=1;
    for(int i=1;i<MAXN;i++)AC_fac[i]=AC_fac[i-1]*i%MOD;
    AC_ifac[MAXN-1]=Quick_Power(AC_fac[MAXN-1],MOD-2);
    for(int i=MAXN-1;i>=1;i--)AC_ifac[i-1]=AC_ifac[i]*i%MOD;
}

ll A(int n,int k){
    if(k<0||k>n)return 0;
    return AC_fac[n]*AC_ifac[n-k]%MOD;
}

ll C(int n,int k){
    if(k<0||k>n)return 0;
    return AC_fac[n]*AC_ifac[k]%MOD*AC_ifac[n-k]%MOD;
}
//排列组合数

//排序
int msort_a[MAXN],msort_tmp[MAXN];
void Merge_Sort(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    Merge_Sort(l,mid);
    Merge_Sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(msort_a[i]<=msort_a[j])msort_tmp[k++]=msort_a[i++];
        else msort_tmp[k++]=msort_a[j++];
    }
    while(i<=mid)msort_tmp[k++]=msort_a[i++];
    while(j<=r)msort_tmp[k++]=msort_a[j++];
    for(int i=l;i<=r;i++){
        msort_a[i]=msort_tmp[i];
    }
}

int qsort_a[MAXN];
void Quick_Sort(int l,int r){
    if(l>=r)return ;
    int x=qsort_a[(l+r)>>1];
    int i=l-1,j=r+1;
    while(i<j){
        do i++;while(qsort_a[i]<x);
        do j--;while(qsort_a[j]>x);
        if(i<j)swap(qsort_a[i],qsort_a[j]);
    }
    Quick_Sort(l,j);
    Quick_Sort(j+1,r);
}
//排序

//背包问题
void YN_Bag(){
    int w[10005],c[10005],dp[10005];
    int t,m;
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>w[i]>>c[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=t;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    cout<<dp[t];
    return ;
}

void Completely_Bag(){
    int w[100005],c[100005],dp[100005];
    int t,m;
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=w[i];j<=t;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
		}
	}
    cout<<dp[t];
    return ;
}

void Some_Bag(){
    int m,n,dp[10005];
    cin>>m>>n;
    while(n--){
        int w,v,c;
        cin>>w>>v>>c;
        for(int i=1;i<=c;i++){
            for(int j=m;j>=w;j--){
                dp[j]=max(dp[j],dp[j-w]+v);
            }
        }
    }
    cout<<dp[m];
}

void Bin_Some_Bag(){
    int dp[1010];
    int w[1000100],v[1000100],cnt;
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		for(int j=1;j<=c;j*=2){
			cnt++;
			w[cnt]=a*j;
			v[cnt]=b*j;
            c-=j;
		}
        if(c>0){
            cnt++;
            w[cnt]=a*c;
            v[cnt]=b*c;
        }
	}
	for(int i=1;i<=cnt;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[m];
    return ;
}
//背包问题

//最长上升子序列
void Max_Long_Up(){//N^2
    int n,dp[10005],a[10005],mx=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<=i;j++){
            if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
        }
        mx=max(mx,dp[i]);
    }
    cout<<mx;
    return ;
}

void Better_Max_Long_Up(){
    int n,dp[10005],a[10005],g[10005],len=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int p=lower_bound(g+1,g+len+1,a[i])-g;
        g[p]=a[i];
        if(p>len)len=p;
    }
    cout<<len;
    return ;
}
//最长上升子序列

//最长公共子序列(两个排列)
void Max_Long_Both(){
    ll dp[1100][1100],a[1100],b[1100];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int j=1;j<=n;j++)cin>>b[j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	cout<<dp[n][n];
    return ;
}

void Better_Max_Long_Both(){
    int len=0,dp[100005],a[100005],b[100005],pos[100005];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pos[x]=i;
    }
    for(int j=1;j<=n;j++){
        int x;
        cin>>x;
        b[j]=pos[x];
    }
    for(int i=1;i<=n;i++){
        int p=lower_bound(dp+1,dp+len+1,b[i])-dp;
        dp[p]=b[i];
        if(p>len)len=p;
    }
    return ;
}
//最长公共子序列(两个排列)

//搜索

bool Search_End(int x,int y){
    return 0;
}

bool Search_Check(int x,int y){
    return 0;
}

int Search_dx[]={1,-1,0,0};
int Search_dy[]={0,0,1,-1};
int Search_vis[1005][1005];
void Square_DFS(int x,int y){
    if(Search_End(x,y))return ;
    for(int i=0;i<4;i++){
        int nx=x+Search_dx[i];
        int ny=y+Search_dy[i];
        if(Search_Check(nx,ny)){
            Search_vis[nx][ny]=1;
            Square_DFS(nx,ny);
        }
    }
}

void Square_BFS(int a,int b){
    queue< PII > q;
    q.push({a,b});
    while(q.size()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+Search_dx[i];
            int ny=y+Search_dy[i];
            if(Search_Check(nx,ny)){
                Search_vis[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
}
//并查集

//普通
int BC_fa[2000005];
int BC_get(int x){
	if(BC_fa[x]==x)return x;
	return BC_fa[x];
}
void BC_merge(int x,int y){
	BC_fa[BC_get(x)]=BC_get(y);
}
void BCJ(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		BC_fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int z,x,y;
		cin>>z>>x>>y;
        if(z==1){
            if(BC_get(x)!=BC_get(y)){
    			BC_merge(x,y);
    		}
        }
        else{
            if(BC_get(x)==BC_get(y)){
    			cout<<"Y";
    		}
            else{
    			cout <<"N";
    		}
            cout<<endl;
        }
		
	}
    return ;
}
//普通

//路径压缩优化
int BCYS_fa[2000005];
int BCYS_get(int x){
	if(BCYS_fa[x]==x)return x;
	return BCYS_fa[x]=BCYS_get(BCYS_fa[x]);
}
void BCYS_merge(int x,int y){
	BCYS_fa[BCYS_get(x)]=BCYS_get(y);
}
void BCJYS(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		BCYS_fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int z,x,y;
		cin>>z>>x>>y;
        if(z==1){
            if(BCYS_get(x)!=BCYS_get(y)){
    			BCYS_merge(x,y);
    		}
        }
        else{
            if(BCYS_get(x)==BCYS_get(y)){
    			cout<<"Y";
    		}
            else{
    			cout <<"N";
    		}
            cout<<endl;
        }
		
	}
    return ;
}
//路径压缩优化
//并查集

//最小生成树
//Kruskal
struct Kruskal_node{
    int u,v;
};
struct Kruskal__3{
    int aa,bb,cc;
}Kruskal_v[200005];
int Kruskal_fa[5005];
int Kruskal_get(int x){
    if(Kruskal_fa[x]==x)return x;
    return Kruskal_get(Kruskal_fa[x]);
}
void Kruskal_merge(int x,int y){
    Kruskal_fa[Kruskal_get(x)]=Kruskal_get(y);
}
bool Kruskal_cmp(Kruskal__3 a,Kruskal__3 b){
    return a.cc<b.cc;
}
vector<Kruskal_node> Kruskal_x[200005];
void Kruskal(){
    int n,m;
    cin>>n>>m;
     for(int i=1;i<=n;i++){
        Kruskal_fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        Kruskal_x[a].push_back({b,c});
        Kruskal_x[b].push_back({a,c});
        Kruskal_v[i].aa=a;
        Kruskal_v[i].bb=b;
        Kruskal_v[i].cc=c;
    }
    set<int> Kruskal_se;
    sort(Kruskal_v+1,Kruskal_v+m+1,Kruskal_cmp);
    int sum=0,len=0;
    for(int i=1;i<=m;i++){
        int uu=Kruskal_v[i].aa,vv=Kruskal_v[i].bb,ww=Kruskal_v[i].cc;
        if(Kruskal_get(uu)==Kruskal_get(vv))continue;
        sum+=ww;
        len++;
        Kruskal_merge(uu,vv);
        Kruskal_se.insert(uu);
        Kruskal_se.insert(vv);
        if(len==n-1)break;
    }
    if(len==n-1 && Kruskal_se.size()==n)cout<<sum;
    else cout<<"orz";
    return ;
}
//Kruskal

//prim
vector<PII> Prim_adj[MAXN];
int Prim_dist[MAXN];
bool Prim_vis[MAXN];
int Prim_n,Prim_m;
ll Prim(){
    memset(Prim_dist, 0x3f, sizeof(Prim_dist));
    memset(Prim_vis, false, sizeof(Prim_vis));
    priority_queue<PII, vector<PII>, greater<PII>> Prim_pq;
    Prim_dist[1]=0;
    Prim_pq.push({0,1});
    ll tot=0;
    int cnt=0;
    while (!Prim_pq.empty()) {
        auto x=Prim_pq.top();
        auto w=x.first;
        auto u=x.second;
        Prim_pq.pop();
        if (Prim_vis[u])continue;
        Prim_vis[u]=1;
        tot+=w;
        cnt++;
        for(auto x:Prim_adj[u]){
            auto v=x.first;
            auto val=x.second;
            if (!Prim_vis[v]&&val<Prim_dist[v]) {
                Prim_dist[v]=val;
                Prim_pq.push({Prim_dist[v],v});
            }
        } 
    }
    if(cnt!=Prim_n)return -1;
    return tot;
}

void Prim_Start() {
    cin>>Prim_n>>Prim_m;
    for(int i=0;i<Prim_m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        Prim_adj[x].emplace_back(y, z);
        Prim_adj[y].emplace_back(x, z);
    }
    ll ans=Prim();
    if(ans==-1){
        cout<<"orz"<<endl;
    }
    else{
        cout<<ans<<endl;
    }
    return ;
}
//prim

//最小生成树

//搜索

//状态压缩dp操作(二进制集合)
//s={1,2,3,4,5}
//10101表示1,3,5
int ZT_dp_s,ZT_dp_d,ZT_dp_s_size;
bool ZT_dp_FIND(int i){//查找第i个
    return ZT_dp_s>>i&1;
}
void ZT_dp_ADD(int i){//加入第i个
    ZT_dp_s=ZT_dp_s|(1<<i);
}

void ZT_dp_DEL(int i){//删除第i个
    ZT_dp_s=ZT_dp_s& ~(1<<i);
}

void ZT_dp_TURN(int i){//第i个取反
    ZT_dp_s=ZT_dp_s& ~(1<<i);
}

void ZT_dp_ALL(int i){//全集
    ZT_dp_s=(1<<ZT_dp_s_size)-1;
}

int ZT_dp_SIZE(int i){//集合大小
    return __builtin_popcount(ZT_dp_s);
}

int ZT_dp_BING(int i){//并集
    return ZT_dp_s|ZT_dp_d;
}

int ZT_dp_JIAO(int i){//交集
    return ZT_dp_s&ZT_dp_d;
}
//状态压缩dp操作(二进制集合)

//二维前缀和
//s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
//int sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
//二位前缀和

//真·AC自动机
void auto_AC(int N,int X){
    for(int i=1;i<=N;i++){
        cout<<"if(n=="<<i<<")cout<<"<<X<<endl;
    }

}
//真·AC自动机

//单源最短路

//Dijkstra

struct Dijkstra_node{
    int u;
    long long dis;
    bool operator<(const Dijkstra_node &t)const{
        return dis>t.dis;
    }
};
long long Dijkstra_dist[1000005];
vector<Dijkstra_node>Dijkstra_g[1000005];
void Dijkstra(int x){
    memset(Dijkstra_dist,0x3f,sizeof Dijkstra_dist);
    priority_queue<Dijkstra_node> pq;
    pq.push({x,0});
    Dijkstra_dist[x]=0;
    while(pq.size()){
        auto u=pq.top().u;
        auto dis=pq.top().dis;
        pq.pop();
        if(dis>Dijkstra_dist[u]){
            continue;
        }
        for(auto &x:Dijkstra_g[u]){
            auto v=x.u;
            auto d=x.dis;
            if(dis+d<Dijkstra_dist[v]){
                Dijkstra_dist[v]=dis+d;
                pq.push({v,Dijkstra_dist[v]});
            }
        }
    }
}
void Dijkstra_Start(){
    int n,m,s;
	cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        Dijkstra_g[u].push_back({v,w});
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++){
        
        cout<<Dijkstra_dist[i]<<' ';
    }
	return ;
}
//Dijkstra

//SPFA
struct SPFA_Node{
	int z,q;
};
vector<SPFA_Node>SPFA_v[100005];
int SPFA_dis[100005];
bool SPFA_vis[100005]; 
queue<int>SPFA_q;
void SPFA(){
	int n,m,s,t;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		SPFA_v[x].push_back({y,z});
	}
	for(int i=0;i<=n+1;i++){
		SPFA_dis[i]=1e9;
	}
	SPFA_dis[s]=0;
	SPFA_vis[s]=1;
	SPFA_q.push(s);
	while(!SPFA_q.empty()){
		int k=SPFA_q.front();
		SPFA_q.pop();
		SPFA_vis[k]=0;
		for(int i=0;i<SPFA_v[k].size();i++){
			int to=SPFA_v[k][i].z;
			int len=SPFA_v[k][i].q;
			if(SPFA_dis[to]>SPFA_dis[k]+len){
				SPFA_dis[to]=SPFA_dis[k]+len;
				if(!SPFA_vis[to]){
					SPFA_vis[to]=1;
					SPFA_q.push(to);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
        cout<<SPFA_dis[i]<<" ";
    }
	return ;
}
//SPFA

//单源最短路

//多源最短路

//Floyd
void Floyd(){
    int a[1005][1005],n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                a[i][j]=0x3f3f3f3f;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        a[u][v]=min(a[u][v],w);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][k]<0x3f3f3f3f&&a[k][j]<0x3f3f3f3f){
                    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i][i]<0){
            cout<<"no solution";
            return ;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[s][i]>=0x3f3f3f3f){
            cout<<"-1 ";
        }
        else{
            cout<<a[s][i]<<' ';
        }
    }
    return ;
}
//Floyd

//多源最短路
void Solve(){

    return ;
}

int main(){
    //freopen("xxx.in","r",stdin);
    //freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    AC_Ready();

    int T=1;
    //cin>>T;

    while(T--){
        Solve();
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 4

热门讨论