提高板子默写

2020-11-03

提高板子默写

1 最小生成树

https://www.luogu.com.cn/problem/P3366

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=5009,M=2e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,id[N],ans;
int find(int i) {return id[i]==i ? i : id[i]=find(id[i]);}
void unite(int u,int v) {id[find(u)]=find(v);}

struct edge {int u,v,w;} e[M];
bool cmp(const edge &a,const edge &b) {return a.w<b.w;}

void kruskal() {
	sort(e+1,e+m+1,cmp);
	rep(i,1,n) id[i]=i;
	rep(i,1,m) if(find(e[i].u)!=find(e[i].v))
		unite(e[i].u,e[i].v), ans+=e[i].w;
	rep(i,1,n) if(find(i)!=find(1)) ans=-1;
}

signed main() {
	n=read(), m=read();
	rep(i,1,m) e[i].u=read(), e[i].v=read(), e[i].w=read();
	kruskal();
	if(ans==-1) puts("orz");
	else printf("%lld\n",ans);
	return 0;
}

2 字符串哈希

https://www.luogu.com.cn/problem/P3370

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

const int b1=19260817, b2=131, mod=1e7+3;
struct hset {
	bool exist1[mod+6], exist2[mod+6];
	int hsh1(string s,int ret=0) {
		rep(i,0,s.size()-1) ret=(ret*b1%mod+s[i])%mod;
		return ret;
	}
	int hsh2(string s,int ret=0) {
		rep(i,0,s.size()-1) ret=(ret*b2%mod+s[i])%mod;
		return ret;
	}
	int ins(string s) {
		int h1=hsh1(s), h2=hsh2(s);
		exist1[h1]=exist2[h2]=1;
	}
	bool find(string s) {
		int h1=hsh1(s), h2=hsh2(s);
		return exist1[h1]&&exist2[h2];
	}
} strmap;

signed main() {
	int n=read(), ans=0;
	while(n--) {
		string s; cin>>s;
		if(!strmap.find(s)) ans++, strmap.ins(s);
	}
	printf("%lld\n",ans);
	return 0;
}

3 单调队列

https://www.luogu.com.cn/problem/P1886

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e6+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,k,a[N];

int q[N],l,r;
void get_min() {
	l=1, r=2; q[1]=1;
	if(k==1) printf("%d ",a[1]);
	rep(i,2,n) {
		while(l<r&&i-q[l]>=k) l++;
		while(l<r&&a[q[r-1]]>=a[i]) r--;
		q[r++]=i;
		if(i>=k) printf("%d ",a[q[l]]);
	}
	puts("");
}
void get_max() {
	l=1, r=2; q[1]=1;
	if(k==1) printf("%d ",a[1]);
	rep(i,2,n) {
		while(l<r&&i-q[l]>=k) l++;
		while(l<r&&a[q[r-1]]<=a[i]) r--;
		q[r++]=i;
		if(i>=k) printf("%d ",a[q[l]]);
	}
	puts("");
}

int main() {
	n=read(), k=read();
	rep(i,1,n) a[i]=read();
	get_min();
	get_max();
	return 0;
}

4 树状数组点更段查

https://www.luogu.com.cn/problem/P3374

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=5e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,a[N];

int s[N];
#define lb(x) ((x)&-(x))
void add(int x,int k) {for(;x<=n;x+=lb(x)) s[x]+=k;}
int sum(int x,int ret=0) {for(;x;x-=lb(x)) ret+=s[x]; return ret;}
int query(int l,int r) {return sum(r)-sum(l-1);}

signed main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read(), add(i,a[i]);
	while(m--) {
		int opt=read(), x=read(), y=read();
		if(opt==1) add(x,y);
		else printf("%lld\n",query(x,y));
	}
	return 0;
}

5 线性逆元

https://www.luogu.com.cn/problem/P3811

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=3e6+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,p,inv[N];

signed main() {
	n=read(), p=read();
	inv[1]=1; puts("1");
	rep(i,2,n) inv[i]=(p-p/i)*inv[p%i]%p, printf("%lld\n",inv[i]);
	return 0;
}

6 线段树

https://www.luogu.com.cn/problem/P3372

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,a[N];

struct node {int l,r,val,tag;} t[N<<2];
void build(int p,int l,int r) {
	if(l==r) {t[p]=(node){l,r,a[l],0}; return;}
	build(p*2,l,(l+r)/2), build(p*2+1,(l+r)/2+1,r);
	t[p]=(node){l,r,t[p*2].val+t[p*2+1].val,0};
}
void pushdown(int p) {
	t[p*2].tag+=t[p].tag, t[p*2+1].tag+=t[p].tag;
	t[p*2].val+=(t[p*2].r-t[p*2].l+1)*t[p].tag,
	t[p*2+1].val+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].tag;
	t[p].tag=0;
}
void add(int p,int x,int y,int k) {
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(l==x&&r==y) {t[p].val+=k*(r-l+1); if(l!=r) t[p].tag+=k; return;}
	pushdown(p);
	if(y<=mid) add(p*2,x,y,k);
	else if(x>mid) add(p*2+1,x,y,k);
	else add(p*2,x,mid,k), add(p*2+1,mid+1,y,k);
	t[p].val=t[p*2].val+t[p*2+1].val;
}
int query(int p,int x,int y) {
	int l=t[p].l, r=t[p].r, mid=(l+r)/2;
	if(l==x&&r==y) return t[p].val;
	pushdown(p);
	if(y<=mid) return query(p*2,x,y);
	else if(x>mid) return query(p*2+1,x,y);
	else return query(p*2,x,mid)+query(p*2+1,mid+1,y);
}

signed main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read();
	build(1,1,n);
	rep(i,1,m) {
		int opt=read(), x=read(), y=read(), k;
		if(opt==1) k=read(), add(1,x,y,k);
		else printf("%lld\n",query(1,x,y));
	}
	return 0;
}

7 树状数组段更点查

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=5e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,a[N];

int s[N];
#define lb(x) ((x)&-(x))
void add(int x,int k) {for(;x<=n;x+=lb(x)) s[x]+=k;}
int sum(int x,int ret=0) {for(;x;x-=lb(x)) ret+=s[x]; return ret;}

signed main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read(), add(i,a[i]), add(i+1,-a[i]);
	while(m--) {
		int opt=read(), x=read(), y, k;
		if(opt==1) y=read(), k=read(), add(x,k), add(y+1,-k);
		else printf("%lld\n",sum(x));
	}
	return 0;
}

8 最近公共祖先

https://www.luogu.com.cn/problem/P3379

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt;} e[N*2]; int hd[N],tot;
void add(int u,int v) {e[++tot]=(edge){v,hd[u]};hd[u]=tot;}

int n,m,s,d[N],f[N][29];

void dfs(int u,int fa) {
	d[u]=d[fa]+1, f[u][0]=fa;
	rep(h,1,20) f[u][h]=f[f[u][h-1]][h-1];
	for(int i=hd[u],v;i;i=e[i].nxt) {
		if((v=e[i].to)==fa) continue;
		dfs(v,u);
	}
}
int lca(int u,int v) {
	if(d[u]<d[v]) swap(u,v);
	per(h,20,0) if(d[f[u][h]]>=d[v]) u=f[u][h];
	if(u==v) return u;
	per(h,20,0) if(f[u][h]!=f[v][h]) u=f[u][h], v=f[v][h];
	return f[u][0];
}

int main() {
	n=read(), m=read(), s=read();
	rep(i,1,n-1) {
		int u=read(), v=read();
		add(u,v), add(v,u);
	}
	dfs(s,0);
	rep(i,1,m) {
		int u=read(), v=read();
		printf("%d\n",lca(u,v));
	}
	return 0;
}

9 负环判断

https://www.luogu.com.cn/problem/P3385

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=3009;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt,w;}e[N*2]; int hd[N],tot;
void add(int u,int v,int w) {e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;}

int T,n,m,d[N],cnt[N];
bool in[N];
int spfa() {
	memset(d,0x3f,sizeof(d));
	memset(cnt,0,sizeof(cnt));
	memset(in,0,sizeof(in));
	queue<int>q; q.push(1); d[1]=0;
	while(!q.empty()) {
		int u=q.front(); q.pop(); in[u]=0;
		for(int i=hd[u],v;i;i=e[i].nxt) 
			if(d[v=e[i].to]>d[u]+e[i].w) {
				d[v]=d[u]+e[i].w;
				if(!in[v]) {
					q.push(v), in[v]=1, cnt[v]++;
					if(cnt[v]>n) return 1;
				}
			}
	}
	return 0;
}

int main() {
	T=read();
	while(T--) {
		memset(hd,0,sizeof(hd)); tot=0;
		n=read(), m=read();
		rep(i,1,m) {
			int u=read(), v=read(), w=read();
			if(w>=0) add(u,v,w), add(v,u,w);
			else add(u,v,w);
		}
		if(spfa()) puts("YES");
		else puts("NO");
	}
	return 0;
}

10 ST表

https://www.luogu.com.cn/problem/P3865

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,a[N],f[N][29];

int main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read(), f[i][0]=a[i];
	rep(j,1,20) rep(i,1,n) {
		if(i+(1<<j)-1>n) continue;
		f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
	}
	rep(i,1,m) {
		int l=read(), r=read(), llen=log2(r-l+1);
		printf("%lld\n",max(f[l][llen],f[r-(1<<llen)+1][llen]));
	}
	return 0;
}

11 最短路

https://www.luogu.com.cn/problem/P4779

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=2e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt,w;} e[N*2]; int hd[N],tot;
void add(int u,int v,int w) {e[++tot]=(edge){v,hd[u],w}, hd[u]=tot;}

int n,m,s,d[N];
bool vst[N];

struct node {
	int u,w;
	bool operator < (const node &b) const {return w>b.w;}
};
void dijkstra() {
	priority_queue<node> q; q.push((node){s,0});
	memset(d,0x3f,sizeof(d)), d[s]=0;
	while(!q.empty()) {
		int u=q.top().u; q.pop();
		if(vst[u]) continue;
		vst[u]=1;
		for(int i=hd[u],v;i;i=e[i].nxt)
			if(!vst[v=e[i].to]&&d[v]>d[u]+e[i].w)
				q.push((node){v,d[v]=d[u]+e[i].w});
	}
}

signed main() {
	n=read(), m=read(), s=read();
	rep(i,1,m) {
		int u=read(), v=read(), w=read();
		add(u,v,w);
	}
	dijkstra();
	rep(i,1,n) printf("%lld ",d[i]);
	puts("");
	return 0;
}

12 Nim游戏

https://www.luogu.com.cn/problem/P2197

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=10009;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,a[N],xans;

int main() {
	int T=read();
	while(T--) {
		n=read();
		rep(i,1,n) a[i]=read();
		xans=0;
		rep(i,1,n) xans^=a[i];
		if(xans) puts("Yes");
		else puts("No");
	}
	return 0;
}

13 缩点

https://www.luogu.com.cn/problem/P3387

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+9;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt;} e[N]; int hd[N],tot;
void add(int u,int v) {e[++tot]=(edge){v,hd[u]}, hd[u]=tot;}

struct egde {int u,v;} ed[N];

int n,m,a[N],dfn[N],low[N],scc[N],sum[N],tick,cnt;
bool in[N];
stack<int> st;

void tarjan(int u) {
	dfn[u]=low[u]=++tick;
	in[u]=1, st.push(u);
	for(int i=hd[u],v;i;i=e[i].nxt) {
		if(!dfn[v=e[i].to]) tarjan(v), low[u]=min(low[u],low[v]);
		else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		int v=st.top();
		scc[u]=++cnt, sum[cnt]=a[u];
		while((v=st.top())!=u) st.pop(), in[v]=0, sum[cnt]+=a[v], scc[v]=cnt;
		st.pop(), in[u]=0;
	}
}

int deg[N],f[N],ans;
void topo() {
	queue<int>q;
	rep(i,1,n) if(!deg[i]) q.push(i), f[i]=sum[i];
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=hd[u],v;i;i=e[i].nxt) {
			deg[v=e[i].to]--;
			f[v]=max(f[v],f[u]+sum[v]);
			if(!deg[v]) q.push(v);
		}
	} 
}

int main() {
	n=read(), m=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,m) {
		int u=read(), v=read();
		add(u,v);
		ed[i]=(egde){u,v};
	}
	rep(i,1,n) if(!dfn[i]) tarjan(i);
	//rep(i,1,n) printf("%d\n",scc[i]); 
	memset(hd,0,sizeof(hd)); tot=0;
	rep(i,1,m) {
		int u=scc[ed[i].u], v=scc[ed[i].v];
		if(u==v) continue;
		add(u,v), deg[v]++;
	}
	topo();
	rep(i,1,n) ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}

14 差分约束

https://www.luogu.com.cn/problem/P5960

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=5009;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

struct edge {int to,nxt,w;}e[N*2]; int hd[N],tot;
void add(int u,int v,int w) {e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;}

int n,m,d[N],cnt[N];
bool in[N];
int spfa() {
	queue<int>q; 
	rep(i,1,n) q.push(i);
	while(!q.empty()) {
		int u=q.front(); q.pop(); in[u]=0;
		for(int i=hd[u],v;i;i=e[i].nxt) 
			if(d[v=e[i].to]>d[u]+e[i].w) {
				d[v]=d[u]+e[i].w;
				if(!in[v]) {
					q.push(v), in[v]=1, cnt[v]++;
					if(cnt[v]>n) return 1;
				}
			}
	}
	return 0;
}

int main() {
	n=read(), m=read();
	rep(i,1,m) {
		int u=read(), v=read(), w=read();
		add(v,u,w);
	}
	if(!spfa()) rep(i,1,n) printf("%d ",d[i]);
	else puts("NO");
	return 0;
}