2022tysc1985

UID: 10108, 注册于 2022-7-27 20:30:34, 最后登录于 2025-4-29 15:49:00, 最后活动于 2025-4-29 15:54:01.

解决了 641 道题目，RP: 274.87 (No. 30)

♂

个人简介

普及 & 普及+/提高- & 提高部分模板

dij

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
//万能头加火车头
using namespace std;




struct edge{
	int v,w;
	bool operator<(edge a)const{
		return w>a.w;
	}
};
const int MAXN=10001;
int n,m,a,b,w,dis[MAXN],vis[MAXN];
priority_queue <edge> q;
vector<edge> v[MAXN];//存边vector
void dij(int st){//dij yyds!!
	memset(dis,127,sizeof dis);
	dis[st]=0;
	q.push((edge){st,0});
	while(!q.empty()){
		int f=(q.top()).v;
		q.pop();
		if(vis[f]) continue;
		for(int i=0;i<v[f].size();i++){
			edge g=v[f][i];
			if(dis[f]+g.w<dis[g.v]){
				dis[g.v]=dis[f]+g.w;
				q.push((edge){g.v,dis[g.v]});
			}
		}
		vis[f]=true;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>w;
		v[a].push_back((edge){b,w});
	}
	dij(1);
	cout<<dis[n];
	return 0;
}

SPFA

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct edge{int to,num;};
vector<edge> v[101];
queue<int> q;
const int inf=99999999;
int n,m,st,en,a,b,k,dis[101],ans;
bool book[101];
void SPFA(int st){//关于SPFA，他已经死了
	memset(dis,inf,sizeof dis);
	dis[st]=0,book[st]=true;
	q.push(st);
	while(!q.empty()){
		int f=q.front();
		q.pop();
		book[f]=false;
		for(int i=0;i<v[f].size();i++){
			if(dis[f]+v[f][i].num<dis[v[f][i].to]){
				dis[v[f][i].to]=dis[f]+v[f][i].num;
				if(!book[v[f][i].to]){
					q.push(v[f][i].to);
					book[v[f][i].to]=true;
				}
			}
		}
	}
}
void add(int a,int b,int k){
	v[a].push_back((edge){b,k});
}
int main(){
	cin>>n>>m>>st;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>k;
		add(a,b,k);
	}
	SPFA(st);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

CRT&EXCRT

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;

int a[10007],m[10007],n,ans=0x3f3f3f3f3f3f3f3f;
int str[30007][128];
char cstr[128];
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int g=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return g;
}
int exCRT(){
	int spe=a[1],lcm=m[1],e,f;
	for(int i=2;i<=n;i++){
		int ri=((a[i]-spe)%m[i]+m[i])%m[i];
		int g=exgcd(lcm,m[i],e,f);
		if(ri%g!=0) return 0x3f3f3f3f3f3f3f3f;
		int z=(e*ri/g%(m[i])+(m[i]))%(m[i]);
		spe=spe+z*lcm;
		lcm=lcm/g*m[i];
		spe=(spe%lcm+lcm)%lcm;
	}
	return spe;
}
char ch;
int ptr;
signed main(){
	memset(str,-1,sizeof str);
	scanf("%lld",&n);
	getchar();
	for(int i=1;i<=n;i++){
		scanf("%s",cstr);
		int le=strlen(cstr);
		for(ptr=0;ptr<le;ptr++){
			str[i][cstr[ptr]]=ptr;
		}
		m[i]=le;
	}
	//for(int i=1;i<=n;i++){
		//for(char c=1;c<=126;c++){
			//printf("%lld ",str[i][c]);
		//}
		//printf("\n");
	//}
	for(char c=1;c<=126;c++){
		for(int i=1;i<=n;i++){
			if(str[i][c]==-1) goto br;
			a[i]=str[i][c];
		}
		//printf("I see U!\n");
		//for(int i=1;i<=n;i++){
			//printf("%lld+%lld ",a[i],m[i]);
		//}
		//printf("\n");
		ans=min(ans,exCRT());
		br:;
	}
	if(ans<0x3f3f3f3f3f3f) printf("%lld\n",ans+1);
	else printf("-1\n");
	return 0;
}

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstdio>
#define int long long
using namespace std;

int n,a[10007],m[10007],M=1,ans;
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&m[i],&a[i]);
		M=M*m[i];
	}
	for(int i=1;i<=n;i++){
		int Mi=M/m[i];
		int e,f;
		int g=exgcd(Mi,m[i],e,f);
		int Ti=((e/g)%(m[i]/g)+m[i]/g)%(m[i]/g);
		ans=(ans+a[i]%M*Mi%M*Ti%M)%M;
	}
	printf("%lld",ans);
	return 0;
}

Lucas(m less&p less)&exLucas

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstdio>
#define int long long
using namespace std;

int t,fac[10009],inv[10009],ifac[10009];
void init(int p){
	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=1;
	for(int i=2;i<=p;i++){
		fac[i]=fac[i-1]*i%p;
		inv[i]=(p-p/i)*inv[p%i]%p;
	}
	for(int i=1;i<=p;i++){
		ifac[i]=ifac[i-1]*inv[i]%p;
	}
	for(int i=0;i<=10;i++){
		//printf("%lld,%lld,%lld\n",fac[i],ifac[i],inv[i]);
	}
	return;
}
int C(int n,int m,int p){
	if(m>n) return 0;
	return fac[n]*ifac[n-m]%p*ifac[m]%p;
}
int Lu_C(int n,int m,int p){
	if(m==0) return 1;
	return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p;
}
int n,m,p;
signed main(){
	scanf("%lld",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld%lld%lld",&n,&m,&p);
		init(p);
		printf("%lld\n",Lu_C(n+m,m,p));
	}
	return 0;
}

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int qpow(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1) ans=ans%p*a%p;
		a=a%p*a%p;
		b=b>>1;
	}
	return ans;
}
int C(int n,int m,int p){
	if(m>n) return 0;
	int u=1,d=1;
	for(int i=1;i<=m;i++){
		u=u*(n-i+1)%p;
		d=d*i%p;
	}
	return u*qpow(d,p-2,p)%p;
}
int Lu_C(int n,int m,int p){
	if(m==0) return 1;
	return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p;
}
int t,n,m,p;
int main(){
	scanf("%lld",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld%lld%lld",&n,&m,&p);
		printf("%lld\n",Lu_C(n,m,p));
	}
	return 0;
}

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstdio>
#define int long long
using namespace std;
int qpow(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1) ans=ans%p*a%p;
		a=a%p*a%p;
		b=b>>1;
	}
	return ans;
}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-a/b*y;
	return d;
}
int inv(int a,int p){//a^{-1}%p
	int x,y;
	exgcd(a,p,x,y);
	return (x%p+p)%p;
}
int fac(int n,int und,int p){
	if(n==0) return 1;
	int pro=1,els=1;
	for(int i=2;i<=p;i++) if(i%und) pro=pro*i%p;
	for(int i=2;i<=n%p;i++) if(i%und) els=els*i%p;
	return qpow(pro,n/p,p)%p*els%p*fac(n/und,und,p)%p;
}
int C(int n,int m,int und,int p){
	if(m>n) return 0;
	int a=fac(n,und,p),b=fac(m,und,p),c=fac(n-m,und,p),cnt=0;
	for(int i=und;i<=n;i*=und) cnt+=n/i;
	for(int i=und;i<=m;i*=und) cnt-=m/i;
	for(int i=und;i<=n-m;i*=und) cnt-=(n-m)/i;
	return a%p*inv(b,p)%p*inv(c,p)%p*qpow(und,cnt,p)%p;
}
int exLu_C(int n,int m,int p){
	int tmp=p,sum=0;
	for(int i=2;i*i<=tmp;i++){
		if(tmp%i>0) continue;
		int cnt=0,prod=1;
		while(tmp%i==0){
			tmp=tmp/i;
			cnt++;
			prod=prod*i;
		}
		int c=C(n,m,i,prod)%p;
		//printf("%lld ",c);
		sum=(sum%p+c*(p/prod)%p*inv(p/prod,prod)%p)%p;
	}
	if(tmp>1){
		int c=C(n,m,tmp,tmp)%p;
		///printf("%lld ",c);
		sum=(sum%p+c*(p/tmp)%p*inv(p/tmp,tmp)%p)%p;
	}
	//printf("\n");
	return sum;
}
int n,m,p;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&p);
	printf("%lld",exLu_C(n,m,p));
	return 0;
}

并查集

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>

using namespace std;
const int maxn = 500521;
int n,m,p;
int mi;
int mj;
int pi;
int pj;
int f[maxn];
inline int read(){
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-f;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
} 
int query(int x){
    if(x == f[x])return x;
    else return f[x] = query(f[x]);
}
void merge(int x,int y){
    int f1 = query(x);
    int f2 = query(y);
    if(f1 != f2){
        if(rand()%2)f[f1] = f2;
        else f[f2] = f1;
    }
    return;
}
int main(){
    n = read();
    m = read();
    p = read();
    for(int i=1;i<=n;i++)f[i] = i;
    for(int i=1;i<=m;i++){
        mi = read();
        mj = read();
        merge(mi,mj);
    }
    for(int i=1;i<=p;i++){
        pi = read();
        pj = read();
        if(query(pi) == query(pj)){
            printf("Yes\n");
        }
        else printf("No\n");
    }
    
    return 0;
}

tarjan强联通

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

vector<int> g[10007];
int low[10007],dfn[10007],vis[10007],cnt,csum,numc[10007],bnc[10007];
stack<int> stk;
int n,m,a,b,ans;

void tarjan(int u){
	int v;
	dfn[u]=low[u]=++cnt;
	stk.push(u);
	vis[u]=true;
	for(int i=0;i<(g[u].size());i++){
		v=g[u][i];
		if(dfn[v]==0){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else{
			if(vis[v])
				low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){//源点 
		csum++;
		do{//出栈 
			numc[csum]++;
			v=stk.top();
			stk.pop();
			bnc[v]=cnt;
			vis[v]=false;
		}while(u!=v);
	}
}

void add(int a,int b){
	g[a].push_back(b);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tarjan(i);
		}
	}
	for(int i=1;i<=csum;i++){
		if(numc[i]>1) ans++; 
	}
	cout<<ans;
	return 0;
}

tarjan-割点，割边（桥）

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

vector<int> g[107];
int dfn[107],low[107],root=1;
bool vis[107];
int n,m,a,b,cnt=0,f,x,ans;

void tarjan(int u,int fa){
	dfn[u]=low[u]=++cnt;
	int child=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(dfn[v]==0){
			child++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				if(child>1||u!=1) vis[u]=true;
			}
		}else{
			if(v!=fa){
				low[u]=min(low[u],dfn[v]);
			}
	
		}
	}
}

int main(){
	while(true){
		memset(vis,false,sizeof vis);
		memset(dfn,0,sizeof dfn);
		memset(low,0,sizeof low);
		cin>>n;
		if(n==0) break;
		for(int i=1;i<=n;i++){
			g[i].clear();
		}
		while(true){
			cin>>f;
			if(f==0) break;
			for(int i=1;i<n;i++){
				cin>>x;
				g[f].push_back(x);
				g[x].push_back(f);
				if(cin.get()=='\n') break;
			}
		}
		cnt=ans=0;
		tarjan(1,0);
		for(int i=1;i<=n;i++) if(vis[i]) ans++;
		cout<<ans<<endl;
	}
	
}

Kruskal

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct edge{int u,v;double w;}g[1000007];
int n,m=1,cnt;
int f[1000007];
double s,ans;
int getf(int x){
	if(f[x]==x) return x;
	return f[x]=getf(f[x]);
}
void init(){
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
}
bool cmp(edge a,edge b){
	return a.w<b.w;
}
int main(){
	cin>>s>>n;
	init();
	while(cin>>g[m].u>>g[m].v>>g[m].w) m++;
	sort(g+1,g+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=getf(g[i].u);
		int y=getf(g[i].v);
		if(x==y) continue;
		f[x]=y;
		ans+=g[i].w;
		cnt++;
	}
	if(ans<=s&&cnt==n-1) cout<<"Need "<<fixed<<setprecision(2)<<ans<<" miles of cable\n";
	else cout<<"Impossible\n";
	return 0;
}

树状数组

#include <iostream>
using namespace std;

int n,m,b,l,r,tr[1000007];
char ch;
int lowbit(int x){return x&-x;}
int ask(int a){
	int ans=0;
	while(a>0){
		ans=ans+tr[a];
		a=a-lowbit(a);
	}
	return ans;
}
void upd(int a,int x){
	while(a<=n){
		tr[a]=tr[a]+x;
		a=a+lowbit(a);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>ch;
		if(ch=='Q'){
			cin>>b;
			cout<<ask(b)<<endl;
		}
		if(ch=='C'){
			cin>>l>>r;
			upd(l,1);
			upd(r+1,-1);
		}
	}
	return 0;
}

线段树（区间查询，区间修改）

#include <iostream>
#define int long long
#define func(a,b) a+b
#define E 0
using namespace std;

struct node{
	int lb,ub;
	int data;
	int tag;
}tr[4*10000007];
int n,m,p,x,y,s,d[10000007];
void build(int k,int a,int b){
	tr[k].lb=a;tr[k].ub=b;tr[k].tag=E;
	if(a==b){
		tr[k].data=d[a];
		return;
	}
	int mid=tr[k].lb+tr[k].ub>>1;
	build(k<<1,a,mid);
	build(k<<1|1,mid+1,b);
	tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data);
}
void dtag(int k,int ls,int rs){
	tr[k<<1].tag+=tr[k].tag;
	tr[k<<1|1].tag+=tr[k].tag;
	tr[k<<1].data+=tr[k].tag*(ls);
	tr[k<<1|1].data+=tr[k].tag*(rs);
	tr[k].tag=E;
}
void upd(int k,int x,int a,int b){
	if(tr[k].lb>=a&&tr[k].ub<=b){
		tr[k].data+=(tr[k].ub-tr[k].lb+1)*x;
		tr[k].tag+=x;
		return;
	}
	int mid=tr[k].lb+tr[k].ub>>1;
	dtag(k,mid-tr[k].lb+1,tr[k].ub-mid);
	if(a<=mid) upd(k<<1,x,a,b);
	if(b>mid) upd(k<<1|1,x,a,b);
	tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data);
}
int query(int k,int a,int b){
	if(tr[k].lb>=a&&tr[k].ub<=b){
		return tr[k].data;
	}
	int mid=tr[k].lb+tr[k].ub>>1;
	dtag(k,mid-tr[k].lb+1,tr[k].ub-mid);
	int ans=E;
	if(a<=mid) ans=func(ans,query(k<<1,a,b));
	if(b>mid) ans=func(ans,query(k<<1|1,a,b));
	return ans;
}
signed main(){
	cin>>n;
	cin>>m;
	for(int i=1;i<=n;i++){
		cin>>d[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>p>>x>>y;
		if(p==1){
			cin>>s;
			upd(1,s,x,y);
		}
		if(p==2){
			cout<<query(1,x,y)<<"\n";
		}
	}
	return 0;
}

LCA（倍增法）

#include <cstdio>
#include <vector>
#include <cmath>
#define int long long
using namespace std;

int k=27;
int n,m,x,y,root,f[40007][30],d[40007];
vector<int> g[40007];
void dfs(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		f[v][0]=u;
		for(int j=1;j<=k;j++) f[v][j]=f[f[v][j-1]][j-1];
		d[v]=d[u]+1;
		dfs(v,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(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];
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x,&y);
		if(y==-1){
			root=x;
		}else{
			g[x].push_back(y);
			g[y].push_back(x);
		}
	}
	d[root]=1;
	dfs(root,0);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		int a=lca(x,y);
		if(a==x) printf("%lld\n",1);
		else if(a==y) printf("%lld\n",2);
		else printf("%lld\n",0);
 	}
	return 0;
}

欧拉筛

#include <cstdio>
#include <cstring>
#define int long long
using namespace std;

int n,m=0,p[10000007];
bool v[10000007];
void init(){
	for(int i=2;i<=n;i++){
		if(!v[i]){
			m=m+1;
			p[m]=i;
		}
		for(int j=1;j<=m;j++){
			if(p[j]*i>n) break;
			v[p[j]*i]=true;
			if(i%p[j]==0) break;
		}
	}
}
signed main(){
	scanf("%lld",&n);
	memset(v,false,sizeof v);
	init();
	printf("%lld",m);
	return 0;
}

欧拉函数

#include <iostream>
#define int long long
using namespace std;

int n,m,ans,phi,ans2;
signed main(){
	scanf("%lld",&n);
	m=phi=n;
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			phi=phi/i*(i-1);
			while(n%i==0) n=n/i;
		}
	}
	if(n>1) phi=phi/n*(n-1);
	for(int i=1;i*i<=m;i++){
		if(m%i==0){
			ans++;
			if(i*i!=m) ans++;
		}
	}
	printf("%lld",m-phi-ans+1);
	return 0;
}

exgcd

#include <cstdio>
#define int long long
using namespace std;

void swap(int &a,int &b){
	int tmp=a;
	a=b;
	b=tmp;
}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-a/b*y;
	return d;
}
int x,y,m,o,l,e,f,a,b,n;
signed main(){
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&o,&l);
	a=o-m;
	b=l;
	n=x-y;
	if(a<0) a=-a,n=-n;
	int g=exgcd(a,b,e,f);
	if(n%g!=0){
		printf("Impossible\n");
		return 0;
	}
	int z=b/g;
	printf("%lld\n",(e*n/g%z+z)%z);
}

最近活动
Stat
Rating

2022tysc1985

个人简介

最近活动

Stat

Rating

状态

开发

支持