您的位置: 首页  >  IT文章  >  临阵磨枪——CSP-S板子小总结 倍增lca(BY_ahawzlc)(P3379) 树剖(BY_ahawzlc)(P3384) 高精加乘——不考虑负数(BY_ahawzlc)(P1303/P1601) dijkstra(djh123)(BY_ahawzlc)(P4779) Tarjan割点、强连通分量(施公算法)(BY_ahawzlc)(P3388) 负环SPFA(BY_ahawzlc)(P3385) KMP(BY_ahawzlc)(P3375) AC自动机(BY_ahawzlc)(P3796) 最小生成树(BY_ahawzlc)(P3366)

临阵磨枪——CSP-S板子小总结 倍增lca(BY_ahawzlc)(P3379) 树剖(BY_ahawzlc)(P3384) 高精加乘——不考虑负数(BY_ahawzlc)(P1303/P1601) dijkstra(djh123)(BY_ahawzlc)(P4779) Tarjan割点、强连通分量(施公算法)(BY_ahawzlc)(P3388) 负环SPFA(BY_ahawzlc)(P3385) KMP(BY_ahawzlc)(P3375) AC自动机(BY_ahawzlc)(P3796) 最小生成树(BY_ahawzlc)(P3366)

分类: IT文章 • 2022-04-21 13:56:49 
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=500005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
int cnt,nxt[N<<1],to[N<<1],h[N],deep[N],p[N][20],n,m,s;
void add(int x,int y) {
	nxt[++cnt]=h[x];
	to[cnt]=y;
	h[x]=cnt;
}
int lca(int a,int b) {
	int dep;
	if(deep[a]<deep[b]) swap(a,b);
	for(dep=0;(1<<dep)<=deep[a];dep++);
	dep--;
	for(int i=dep;i>=0;i--) if(deep[a]-(1<<i)>=deep[b]) a=p[a][i];
	if(a==b) return a;
	for(int i=dep;i>=0;i--) if(p[a][i]!=-1&&p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i];
	return p[a][0];
}
void dfs(int x) {
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(!deep[y]&&y!=s) {
			deep[y]=deep[x]+1;
			p[y][0]=x;
			dfs(y);
		}
	}
}
void init(int s) {
	memset(p,-1,sizeof p);
	memset(deep,0,sizeof deep);
	dfs(s);
	for(int j=0;(1<<j)<=n;j++) 
		for(int i=1;i<=n;i++) if(p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1];
}
int main() {
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++) {
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	init(s);
	while(m--) {
		int x=read(),y=read(),ans;
		ans=lca(x,y);
		printf("%d
",ans);
	}
	return 0;
}

树剖(BY_ahawzlc)(P3384)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
#define mid ((l+r)>>1)
#define lson (now<<1)
#define rson (now<<1|1)
using namespace std;
const int N=200005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
int n,m,mod,r,cnt,nxt[N<<1],to[N<<1],h[N];
void add(int x,int y) {
	to[++cnt]=y;
	nxt[cnt]=h[x];
	h[x]=cnt;
}
int tree[N*5],lazy[N*5],va[N];
void update(int now) {
	tree[now]=(tree[lson]+tree[rson])%mod;
}
void pushdown(int now,int l,int r) {
	if(lazy[now]) {
		lazy[lson]+=lazy[now];
		lazy[rson]+=lazy[now];
		tree[lson]=(tree[lson]+lazy[now]*(mid-l+1))%mod;
		tree[rson]=(tree[rson]+lazy[now]*(r-mid))%mod;
		lazy[now]=0;
	}
}
void build(int now,int l,int r) {
	if(l==r) {tree[now]=va[l];return;}
	build(lson,l,mid);
	build(rson,mid+1,r);
	update(now);
}
void change(int now,int l,int r,int x,int y,int z) {
	if(x<=l&&r<=y) {lazy[now]+=z;tree[now]=(tree[now]+z*(r-l+1))%mod;return;}
	pushdown(now,l,r);
	if(x<=mid) change(lson,l,mid,x,y,z);
	if(y>mid) change(rson,mid+1,r,x,y,z);
	update(now);
}
int que=0;
void ask(int now,int l,int r,int x,int y) {
	if(x<=l&&r<=y) {que=(que+tree[now])%mod;return;}
	pushdown(now,l,r);
	if(x<=mid) ask(lson,l,mid,x,y);
	if(y>mid) ask(rson,mid+1,r,x,y);
}
int nn,dep[N],id[N],siz[N],ver[N],fa[N],w[N],top[N];
void dfs1(int x,int f,int d) {
	dep[x]=d;
	fa[x]=f;
	siz[x]=1;
	int ms=-1;
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==f) continue;
		dfs1(y,x,d+1);
		siz[x]+=siz[y];
		if(siz[y]>ms) ms=siz[y],ver[x]=y;
	}
}
void dfs2(int x,int topf) {
	top[x]=topf;
	id[x]=++nn;
	va[nn]=w[x];
	if(!ver[x]) return;
	dfs2(ver[x],topf);
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==fa[x]||y==ver[x]) continue;
		dfs2(y,y);
	}
}
void addr(int x,int y,int z) {
	z%=mod;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) 
			swap(x,y);
		change(1,1,n,id[top[x]],id[x],z);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) 
		swap(x,y);
	change(1,1,n,id[x],id[y],z);
}
void adds(int x,int z) {
	change(1,1,n,id[x],id[x]+siz[x]-1,z);
}
int queryr(int x,int y) {
	int ans=0;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) 
			swap(x,y);
		que=0;
		ask(1,1,n,id[top[x]],id[x]);
		ans=(ans+que)%mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) 
		swap(x,y);
	que=0;
	ask(1,1,n,id[x],id[y]);
	ans=(ans+que)%mod;
	return ans;
}
int querys(int x) {
	que=0;
	ask(1,1,n,id[x],id[x]+siz[x]-1);
	return que;
}
int main() {
	int r;
	n=read(),m=read(),r=read(),mod=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<n;i++) {
		int a=read(),b=read();
		add(a,b),add(b,a);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,1,n);
	while(m--) {
		int opt=read(),x=read(),y,z;
		if(opt==1) {
			y=read(),z=read();
			addr(x,y,z);
		}
		if(opt==2) {
			y=read();
			printf("%d
",queryr(x,y));
		}
		if(opt==3) {
			y=read();
			adds(x,y);
		}
		if(opt==4) 
			printf("%d
",querys(x));
	}
	return 0;
}

高精加乘——不考虑负数(BY_ahawzlc)(P1303/P1601)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
const int N=100005;
using namespace std;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+(ch-'0');
		ch=getchar();
	}
	return sum*w;
}
int numa[N],numb[N],numc[N];
char c[N],aa[N],bb[N];
void muti(const char *a,const char *b) {
    int lena=strlen(a),lenb=strlen(b);
    memset(c,0,sizeof c);
    memset(numc,0,sizeof numc);
    for(int i=1;i<=lena;++i) numa[i]=a[lena-i]-'0';
    for(int i=1;i<=lenb;++i) numb[i]=b[lenb-i]-'0';
    for(int i=1;i<=lena;i++) for(int j=1;j<=lenb;j++) numc[i+j-1]+=numa[i]*numb[j];
    int len=lena+lenb;
    for(int i=1;i<len;i++) if(numc[i]>9) {
        numc[i+1]+=numc[i]/10;numc[i]%=10;
    }
    while(numc[len]==0&&len>1) len--;
    for(int i=len;i>=1;i--) c[len-i]=numc[i]+'0';
}
void pl(const char *a,const char *b) {
    int lena=strlen(a),lenb=strlen(b);
    memset(c,0,sizeof c);
    memset(numc,0,sizeof numc);
    for(int i=1;i<=lena;++i) numa[i]=a[lena-i]-'0';
    for(int i=1;i<=lenb;++i) numb[i]=b[lenb-i]-'0';
    int len=max(lena,lenb);
    for(int i=1;i<=len;i++) numc[i]=numa[i]+numb[i];
    for(int i=1;i<=len;i++) if(numc[i]>9) {
        numc[i+1]+=numc[i]/10;numc[i]%=10;
    }
    len++;
    while(numc[len]==0&&len>1) len--;
    for(int i=len;i>=1;i--) c[len-i]=numc[i]+'0';
}
int main() {
	/*cin>>aa>>bb;
	pl(aa,bb);
	cout<<c;*/
        cin>>aa>>bb;
        muti(aa,bb);
        cout<<c;
	return 0;
}

dijkstra(djh123)(BY_ahawzlc)(P4779)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int N=200005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
int cnt,nxt[N],to[N],h[N],cost[N],dis[N],n,m,s;
priority_queue<pi> q;
bool vis[N];
void add(int x,int y,int z) {
	nxt[++cnt]=h[x];
	cost[cnt]=z;
	to[cnt]=y;
	h[x]=cnt;
}
void djh123(int s) {
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	while(q.size()) q.pop();
	q.push(mp(0,s));
	dis[s]=0;
	while(q.size()) {
		int u=q.top().S;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=nxt[i]) {
			int v=to[i];
			if(dis[u]+cost[i]<dis[v]) {
				dis[v]=dis[u]+cost[i];
				q.push(mp(-dis[v],v));
			}
		}
	}
}
int main() {
	n=read(),m=read(),s=read();
	for(int i=1;i<=m;i++) {
		int x=read(),y=read(),z=read();
		add(x,y,z);
	}
	djh123(s);
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}

Tarjan割点、强连通分量(施公算法)(BY_ahawzlc)(P3388)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=200005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
int n,m,h[N],cnt,nxt[N],to[N];
void add(int x,int y) {
	nxt[++cnt]=h[x];
	to[cnt]=y;
	h[x]=cnt;
}
int id,dfn[N],low[N],root,tot;
stack<int> s;
bool cut[N];
/*bool vis[N];
int siz[N],bl[N];
void tarjan(int u) {
	dfn[u]=low[u]=++id;
	s.push(u);
	vis[u]=1;
	for(int i=h[u];i;i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			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]) {
		int v;
		tarn++;
		do {
			v=s.top();
			s.pop();
			bl[v]=tarn;
			siz[tarn]++;
			vis[v]=0;
		} while(v!=u);
	}
}*/
void tarjan(int u) {
	dfn[u]=low[u]=++id;
	int flag=0;
	for(int i=h[u];i;i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				flag++;
				if(u!=root||flag>1) cut[u]=1;
			}
		} else low[u]=min(low[u],dfn[v]);
	}
} 
int main() {
	int n=read(),m=read();
	for(int i=1;i<=m;i++) {
		int x=read(),y=read();
		if(x==y) continue;
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i);
	for(int i=1;i<=n;i++) if(cut[i]) tot++;
	printf("%d
",tot);
	for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
	return 0;
}

负环SPFA(BY_ahawzlc)(P3385)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=200005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
int cnt,h[N],nxt[N*3],to[N*3],cost[N*3],tot[N],dis[N],n,m;
void add(int x,int y,int z) {
	nxt[++cnt]=h[x];
	to[cnt]=y;
	cost[cnt]=z;
	h[x]=cnt;
}
queue<int> q;
bool vis[N];
bool spfa(int s) {
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(tot,0,sizeof tot);
	while(q.size()) q.pop();
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(q.size()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=h[u];i;i=nxt[i]) {
			int v=to[i],c=cost[i];
			if(dis[v]>dis[u]+c) {
				dis[v]=dis[u]+c;
				tot[v]=tot[u]+1;
				if(tot[v]>=n) return 1;
				if(!vis[v]) {
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return 0;
}
int main() {
	int t=read();
	while(t--) {
		memset(h,0,sizeof h);
		memset(nxt,0,sizeof nxt);
		memset(cost,0,sizeof cost);
		memset(to,0,sizeof to);
		cnt=0;
		n=read(),m=read();
		while(m--) {
			int x=read(),y=read(),z=read();
			add(x,y,z);
			if(z>=0) add(y,x,z);
		}
		if(spfa(1)) puts("YES");
		else puts("NO");
	}
	return 0;
}

KMP(BY_ahawzlc)(P3375)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=1000006;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
char a[N],b[N];
int kmp[N],lena,lenb,now;
int main() {
	scanf("%s",a+1);
	scanf("%s",b+1);
	lena=strlen(a+1),lenb=strlen(b+1);
	for(int i=2;i<=lenb;i++) {
		while(now&&b[i]!=b[now+1]) now=kmp[now];
		if(b[now+1]==b[i]) now++;
		kmp[i]=now;
	}
	now=0;
	for(int i=1;i<=lena;i++) {
		while(now>0&&b[now+1]!=a[i]) now=kmp[now];
		if(b[now+1]==a[i]) now++;
		if(now==lenb) printf("%d
",i-lenb+1),now=kmp[now];
	}
	for(int i=1;i<=lenb;i++) printf("%d ",kmp[i]);
	return 0;
}

AC自动机(BY_ahawzlc)(P3796)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=2000005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
char s[N];
struct trie {
	int fail,vis[26],end;
}ac[N];
int tot;
void build(const char *s) {
	int len=strlen(s),now=0,c;
	for(int i=0;i<len;i++) {
		c=s[i]-'a';
		if(ac[now].vis[c]==0) ac[now].vis[c]=++tot;
		now=ac[now].vis[c];
	}
	ac[now].end++;
}
queue<int> q;
void get_fail() {
	while(q.size()) q.pop();
	for(int i=0;i<26;i++) {
		if(ac[0].vis[i]!=0) {
			ac[ac[0].vis[i]].fail=0;
			q.push(ac[0].vis[i]);
		}
	}
	while(q.size()) {
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++) {
			if(ac[u].vis[i]!=0) {
				ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i];
				q.push(ac[u].vis[i]);
			} else ac[u].vis[i]=ac[ac[u].fail].vis[i];
		}
	}
}
int ask(const char *s) {
	int len=strlen(s),now=0,ans=0,c;
	for(int i=0;i<len;i++) {
		c=s[i]-'a';
		now=ac[now].vis[c];
		for(int j=now;j&&ac[j].end!=-1;j=ac[j].fail) {
			ans+=ac[j].end;
			ac[j].end=-1;
		}
	}
	return ans;
}
int main() {
	int n=read();
	for(int i=1;i<=n;i++) {
		scanf("%s",s);
		build(s);
	}
	ac[0].fail=0;
	get_fail();
	scanf("%s",s);
	printf("%d",ask(s));
	return 0;
}

最小生成树(BY_ahawzlc)(P3366)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define re register
#define pi pair<int,int>
#define F first
#define S second
using namespace std;
const int N=200005;
inline int read() {
	int sum=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	}
	return sum*w;
}
struct node {
	int u,v,w;
}b[N];
int fa[N],n,m,tot,ans;
int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y) {
	x=find(x),y=find(y);
	if(x!=y) fa[x]=y;
}
bool cmp(node a,node b) {
	return a.w<b.w;
}
int main() {
	n=read(),m=read();
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) {
		int x=read(),y=read(),z=read();
		b[i].u=x,b[i].v=y,b[i].w=z;
	}
	sort(b+1,b+m+1,cmp);
	for(int i=1;i<=m;i++) {
		int x=b[i].u,y=b[i].v;
		if(find(x)!=find(y)) {
			tot++;
			merge(x,y);
			ans+=b[i].w;
		}
		if(tot==n-1) break;
	} 
	bool ok=0;
	for(int i=1;i<=n;i++) 
		if(fa[i]==i) {
			if(ok) {
				puts("orz");
				return 0;
			}
			ok=1;
		}
	printf("%d",ans);
	return 0;
}

相关推荐