首页 > itarticle > 模板库（持续更新）

模板库（持续更新）

admin 11月 14, 2020 0

整理一下我学过的部分算法模板。

AC自动机

HDU2222

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 

using namespace std;
const int maxn=1000000+10;
int trie[maxn][26];
int cntword[maxn];//统计每个节点为单词终点的个数 
int fail[maxn];//fail指针 
char s[maxn];
int cnt;
void (){
	memset(trie,0,sizeof(trie));
	memset(cntword,0,sizeof(cntword));
	memset(fail,0,sizeof(fail));
	cnt=0;
}
void insert(char* s){
	int len=strlen(s);
	int root=0;
	for(int i=0;i<len;i++){
		if(!trie[root][s[i]-'a']) trie[root][s[i]-'a']=++cnt;
		root=trie[root][s[i]-'a'];
	}
	cntword[root]++;
}
void getfail(){
	queue<int>que;
	for(int i=0;i<26;i++){
		if(trie[0][i]) que.push(trie[0][i]);
	}
	while(!que.empty()){
		int now=que.front();
		que.pop();
		for(int i=0;i<26;i++){
			if(trie[now][i]){
				fail[trie[now][i]]=trie[fail[now]][i];
				que.push(trie[now][i]);
			}
			else{
				trie[now][i]=trie[fail[now]][i];
			}
		} 
	}
}
int query(char *s){
	int len=strlen(s);
	int res=0,now=0;
	for(int i=0;i<len;i++){
		now=trie[now][s[i]-'a'];
		for(int j=now;j && cntword[j]!=-1;j=fail[j]){
			res+=cntword[j];
			cntword[j]=-1;
		}
	}
	return res;
}
int main()
{
	int t,n;
	scanf("%d",&t);
	while(t--){
		init();
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%s",s);
			insert(s);
		}
		cnt=0;
		getfail();
		scanf("%s",s);
		printf("%dn",query(s));
	}
	return 0;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
 
void (){
	for(int i=1;i<=n;i++) pre[i]=i;
}
int find(int x){
	return x==pre[x]?x:pre[x]=find(pre[x]);
}
void Union(int x,int y){
	x=find(x);
	y=find(y);
	if(x<y) pre[y]=x;
	else pre[x]=y;
}

FFT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
void (int lim,int bit_len){
    memset(r,0,sizeof(r));
    for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(bit_len-1));
}
void fft(cpx* a,int lim,int flag){
    for(int i=0;i<lim;i++){
        if(i<r[i]){
            swap(a[i],a[r[i]]);
        }
    }
    for(int i=1;i<lim;i<<=1){
        cpx part{cos(pi/i),flag*sin(pi/i)};
        int R=i<<1;
        for(int j=0;j<lim;j+=R){
            cpx w{1,0};
            for(int k=0;k<i;k++,w=w*part){
                cpx x=a[j+k];
                cpx y=w*a[j+i+k];
                a[j+k]=x+y;
                a[j+i+k]=x-y;
            }
        }
    }
    if(flag==-1){
        for(int i=0;i<lim;i++) a[i].x/=lim;
    }
}

GCD

1
2
3
 
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}

康托展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
void cantor(){
    ll sum=1,fac=1;
    for(int i=n-1;i>0;i--){
        fac*=(n-i);
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j]) sum+=fac;
        }
    }
    printf("%lldn",sum);
}
void inverse_cantor(){
    ll fac=1,num;
    k--;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<n;i++) fac*=i;
    for(int i=1;i<=n;i++){
        num=k/fac;
        k%=fac;
        if(n-i) fac/=(n-i);
        for(int j=1;j<=n;j++){
            if(num==0 && !vis[j]){
                printf("%d ",j);
                vis[j]=1;
                break;
            }
            if(!vis[j]) num--;
        }
    }
    printf("n");
}

KM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
int love[maxn][maxn];
int exgirl[maxn],exboy[maxn];
bool visgirl[maxn],visboy[maxn];
int match[maxn],slack[maxn];
int n,m;
bool dfs(int x){
	visgirl[x]=true;
	for(int i=0;i<n;i++){
		if(!visboy[i]){
			int gap=exgirl[x]+exboy[i]-love[x][i];
			if(gap==0){
				visboy[i]=true;
				if(match[i]==-1 || dfs(match[i])){
					match[i]=x;
					return true;
				}
			}
			else{
				slack[i]=min(slack[i],gap);
			}
		}
	}
	return false;
}
int km(){
	memset(match,-1,sizeof(match));
	memset(exboy,0,sizeof(exboy));
	for(int i=0;i<n;i++){
		exgirl[i]=love[i][0];
		for(int j=1;j<n;j++){
			exgirl[i]=max(exgirl[i],love[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		fill(slack,slack+n,INF);
		while(true){
			memset(visgirl,false,sizeof(visgirl));
			memset(visboy,false,sizeof(visboy));
			if(dfs(i)) break;
			
			int d=INF;
			for(int i=0;i<n;i++){
				if(!visboy[i]) d=min(d,slack[i]);
			}
			for(int i=0;i<n;i++){
				if(visgirl[i]) exgirl[i]-=d;
				if(visboy[i]) exboy[i]+=d;
				else slack[i]-=d;
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		res+=love[match[i]][i];
	}
	return res;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void get_nxt(){
	int i=1,next[1]=0,j=0;
	int len=strlen(str);
	while(i<len){
		if(j==0 || str[i]==str[j]){
			i++;
			j++;
			next[i]=j;
		}
		else
			j=next[i];
	}
}

Tarjan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
int n,m,tt,cnt,sig;
int vis[maxn],low[maxn],dfn[maxn];
int color[maxn],st[maxn];
vector<int>vec[maxn];
void (){
	memset(vis,0,sizeof(vis));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(color,0,sizeof(color));
	memset(st,0,sizeof(st));
	for(int i=1;i<=n;i++) vec[i].clear();
}
void tarjan(int x){
	vis[x]=1;
	dfn[x]=low[x]=cnt++;
	st[++tt]=x;
	for(int i=0;i<vec[x].size();i++){
		int y=vec[x][i];
		if(vis[y]==0) tarjan(y);
		if(vis[y]==1) low[x]=min(low[x],low[y]);
	}
	if(low[x]==dfn[x]){
		sig++;
		do{
			color[st[tt]]=sig;
			vis[st[tt]]=-1;
		}while(st[tt--]!=x);
	}
}
void solve(){
	tt=-1;cnt=1;sig=0;
	for(int i=1;i<=n;i++){
		if(vis[i]==0) tarjan(i);
	}
	/*
	此处添加其他操作 
	*/
}

凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
struct node{
	int x,y;
	int pos;
}p[maxn],q[maxn];
int n,l;
node getmag(node a,node b){
	node s;
	s.x=b.x-a.x;
	s.y=b.y-a.y;
	return s;
}
int multiX(node a,node b){
	return a.x*b.y-a.y*b.x;
}
bool cmp(node a,node b){
	return multiX(getmag(p[1],a),getmag(p[1],b))>0;
}
void graham(){
	int id=1;
	for(int i=2;i<=n;i++){ 
		if(p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y)) id=i;
	}
	if(id!=1) swap(p[id],p[1]);
	
	sort(p+2,p+n+1,cmp); 
	q[++l]=p[1]; 
	for(int i=2;i<=n;i++){
		
		while(l>=2 && multiX(getmag(q[l-1],p[i]),getmag(q[l-1],q[l]))>=0) l--;
		q[++l]=p[i];
	}
}

网络流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
struct edge{
    int to,dis,nxt;
}G[maxn];
int head[maxn],d[maxn],cur[maxn];
void add(int from,int to,int dis){
    G[cnt].to=to;
    G[cnt].dis=dis;
    G[cnt].nxt=head[from];
    head[from]=cnt++;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int x=0;
    for(int& i=cur[u];i!=-1;i=G[i].nxt){
        // cur[u]=G[i].nxt;
        int v=G[i].to;
        if(d[v]==d[u]+1 && G[i].dis>0){
            int res = dfs(v,min(flow,G[i].dis));
            flow -= res;
            x += res;
            G[i].dis   -= res;
            G[i^1].dis += res;
            if(flow == 0) break;
        }
    }
    if(!x) d[u]=-1;
    return x;
}
void bfs(){
    memset(d,-1,sizeof(d));
    queue<int>que;
    que.push(s);
    d[s]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=head[u];i!=-1;i=G[i].nxt){
            int v=G[i].to;
            if(d[v]==-1 && G[i].dis>0){
                d[v]=d[u]+1;
                que.push(v);
            }
        }
    }
}
void dinic(){
    ll max_flow=0;
    while(true){
        bfs();
        if(d[t]==-1) break;
        for(int i=1;i<=n;i++) cur[i]=head[i];
        max_flow+=dfs(s,INF);
    }
    printf("%lldn",max_flow);
}

线段树

线段树单点更新+查询区间最大值

HDU1754

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 

using namespace std;
#define ll long long
const int maxn=1000000;
int dat[maxn],n;
int m,a,b;
char op;
void (int x){
	n=1;
	while(n<x) n*=2;
	for(int i=0;i<n*2-1;i++){
		dat[i]=0;
	}
}
void update(int k,int a){
	k+=n-1;
	dat[k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=max(dat[k*2+1],dat[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return 0;
	if(a<=l && r<=b) return dat[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
		return max(vl,vr);
	}
}
int main()
{
	int n_;
	while(~scanf("%d %d",&n,&m)){
		n_=n;
		init(n);
		for(int i=0;i<n_;i++){
			scanf("%d",&dat[i+n-1]);
			update(i,dat[i+n-1]);
		}
		getchar();
		while(m--){
			scanf("%c %d %d",&op,&a,&b);
			getchar();
			if(op=='Q') printf("%dn",query(a-1,b-1,0,0,n-1));
			else if(op=='U') update(a-1,b);
		}
	}
	
	return 0;
}

线段树区间更新

FZU1608

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 

using namespace std;
#define ll long long
const int maxn=1000000;
int n,m,dat[maxn];
void init(int x){
	n=1;
	while(n<x) n*=2;
	for(int i=0;i<n*2-1;i++){
		dat[i]=0;
	}
}
void update(int a,int b,int x,int k,int l,int r){
	if(b<l || r<a) return ;
	if(a<=l && r<=b) dat[k]=max(x,dat[k]);
	else{
		update(a,b,x,k*2+1,l,(l+r)/2);
		update(a,b,x,k*2+2,(l+r)/2+1,r);
	}
}
int query(int l,int r,int k,int mmax){
	if(l==r) return max(mmax,dat[k]);
	dat[k]=max(mmax,dat[k]);
	int vl=query(l,(l+r)/2,k*2+1,dat[k]);
	int vr=query((l+r)/2+1,r,k*2+2,dat[k]);
	return vl+vr;
}
int main()
{
	int a,b,x;
	while(~scanf("%d %d",&n,&m)){
		init(n);
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&a,&b,&x);
			update(a,b-1,x,0,0,n-1);
		}
		printf("%dn",query(0,n-1,0,0));
	}
	return 0;
}

线段树区间更新+区间求和

POJ3468

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
const ll maxn=1000000;
ll dat[maxn],sum[maxn],n,m;
void update(ll a,ll b,ll x,ll k,ll l,ll r){
	if(a<=l && r<=b){
		dat[k]+=x;
	}
	else if(l<=b && a<=r){
		sum[k]+=(min(b,r)-max(a,l)+1)*x;
		update(a,b,x,k*2+1,l,(l+r)/2);
		update(a,b,x,k*2+2,(l+r)/2+1,r);
	}
}
ll query(ll a,ll b,ll k,ll l,ll r){
	if(b<l || r<a) return 0;
	else if(a<=l && r<=b) return dat[k]*(r-l+1)+sum[k];
	else{
		ll res=(min(b,r)-max(a,l)+1)*dat[k];
		res+=query(a,b,k*2+1,l,(l+r)/2);
		res+=query(a,b,k*2+2,(l+r)/2+1,r);
		return res;
	}
}
int main()
{
	ll a,b,x;
	char op;
	scanf("%lld %lld",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%lld",&x);
		update(i,i,x,0,0,n-1);
	}
	getchar();
	while(m--){
		scanf("%c",&op);
		if(op=='Q'){
			scanf("%lld %lld",&a,&b);
			printf("%lldn",query(a-1,b-1,0,0,n-1));
		}
		else{
			scanf("%lld %lld %lld",&a,&b,&x);
			update(a-1,b-1,x,0,0,n-1);
		}
		getchar();
	}
	return 0;
}

线性基求交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
void LinearBase(int v1,int v2,int res){
    int a[35],b[35];
    for(int i=0;i<32;i++) a[i]=b[i]=tree[v1][i];
    for(int i=0;i<32;i++){
        int q=tree[v2][i],t=0;
        if(!q) continue;
        int j=i;
        for(;j>=0;j--){
            if(q>>j){
                if(!a[j]) break;
                q^=a[j];
                t^=b[j];
            }
        }
        if(!q) tree[res][i]=t;
        else a[j]=q,b[j]=t;
    }
}

主席树

静态主席树

//查询区间第k小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# include<bits/stdc++.h>

using namespace std;
const int maxn=1000000+10;
int rt[maxn],ls[maxn*2],rs[maxn*2],sum[maxn*2];
int a[maxn],b[maxn];
int tot,N,n,q;
void build(int& o,int l,int r){
	o=++tot;
	sum[o]=0;
	if(l==r) return ;
	int m=(l+r)/2;
	build(ls[o],l,m);
	build(rs[o],m+1,r);
}
void update(int& o,int l,int r,int last,int k){
	o=++tot;
	ls[o]=ls[last];
	rs[o]=rs[last];
	sum[o]=sum[last]+1;
	if(l==r) return ;
	int m=(l+r)/2;
	if(k<=m) update(ls[o],l,m,ls[last],k);
	else update(rs[o],m+1,r,rs[last],k);
}
int query(int s,int e,int l,int r,int k){
	if(l==r) return l;
	int cnt=sum[ls[e]]-sum[ls[s]];
	int m=(l+r)/2;
	if(k<=cnt) return query(ls[s],ls[e],l,m,k);
	else return query(rs[s],rs[e],m+1,r,k-cnt);
}
int main()
{
	int t;
	int l,r,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		tot=0;
		sort(b+1,b+n+1);
		N=unique(b+1,b+n+1)-(b+1);
		build(rt[0],1,N);
		for(int i=1;i<=n;i++) update(rt[i],1,N,rt[i-1],lower_bound(b+1,b+N+1,a[i])-b);
		while(q--){
			scanf("%d %d %d",&l,&r,&k);
			int ans=query(rt[l-1],rt[r],1,N,k);
			printf("%dn",b[ans]);
		}
	}
	return 0;
}

动态主席树

//修改单点+查询区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# include<bits/stdc++.h>

using namespace std;
const int maxn=60000+10;
int a[maxn],hash[maxn];
int rt[maxn],RT[maxn],ls[maxn*32],rs[maxn*32],sum[maxn*32];
int ul[maxn],ur[maxn]; 
int tot,n,q,N;
struct node{
	int l,r,k;
	bool flag;
}op[maxn];
int lowbit(int x){
	return x&(-x);
}
void build(int& o,int l,int r){ 
	o=++tot;
	sum[o]=0;
	if(l==r) return;
	int m=(l+r)/2;
	build(ls[o],l,m);
	build(rs[o],m+1,r);
}
void update(int& o,int l,int r,int last,int p,int val){ 
	o=++tot;
	ls[o]=ls[last];
	rs[o]=rs[last];
	sum[o]=sum[last]+val;
	if(l==r) return ;
	int m=(l+r)/2;
	if(p<=m) update(ls[o],l,m,ls[last],p,val);
	else update(rs[o],m+1,r,rs[last],p,val);
}
void add(int x,int val){
	int res=lower_bound(hash+1,hash+N+1,a[x])-hash;
	while(x<=n){ 
		update(RT[x],1,N,RT[x],res,val);
		x+=lowbit(x);
	}
}

int Sum(int x,bool flag){
	int res=0;
	while(x){
		if(flag) res+=sum[ls[ur[x]]];
		else res+=sum[ls[ul[x]]];
		x-=lowbit(x);
	}
	return res;
}

int query(int s,int e,int ts,int te,int l,int r,int k){
	if(l==r) return l;
	int m=(l+r)/2;
	int cnt=Sum(e,true)-Sum(s,false)+sum[ls[te]]-sum[ls[ts]];
	if(k<=cnt){ 
		for(int i=e;i;i-=lowbit(i)) ur[i]=ls[ur[i]];
		for(int i=s;i;i-=lowbit(i)) ul[i]=ls[ul[i]];
		return query(s,e,ls[ts],ls[te],l,m,k);
	}
	else{ 
		for(int i=e;i;i-=lowbit(i)) ur[i]=rs[ur[i]];
		for(int i=s;i;i-=lowbit(i)) ul[i]=rs[ul[i]];
		return query(s,e,rs[ts],rs[te],m+1,r,k-cnt);
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			hash[i]=a[i];
		}
		char str[2];
		N=n;
		for(int i=1;i<=q;i++){
			scanf("%s",str);
			if(str[0]=='Q'){
				scanf("%d %d %d",&op[i].l,&op[i].r,&op[i].k);
				op[i].flag=true;
			}
			else{
				scanf("%d %d",&op[i].r,&op[i].k);
				op[i].flag=false;
				hash[++N]=op[i].k;
			}
		}
		sort(hash+1,hash+N+1);
		N=unique(hash+1,hash+N+1)-(hash+1);
		tot=0;
		build(rt[0],1,N);
		for(int i=1;i<=n;i++) update(rt[i],1,N,rt[i-1],lower_bound(hash+1,hash+N+1,a[i])-hash,1);
		for(int i=1;i<=n;i++) RT[i]=rt[0]; 
		for(int i=1;i<=q;i++){
			int l=op[i].l,r=op[i].r,k=op[i].k;
			if(op[i].flag){
				for(int j=r;j;j-=lowbit(j)) ur[j]=RT[j];
				for(int j=l-1;j;j-=lowbit(j)) ul[j]=RT[j];
                int res=query(l-1,r,rt[l-1],rt[r],1,N,k);
                printf("%dn",hash[res]);
            }
            else{
                add(r,-1);
                a[r]=k;
                add(r,1);
            }
        }
    }
    return 0;
}

__int128输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能