省选复习

OI&ACM, 模板
  1. 1 数据结构
    1. 1.1 线段树
    2. 1.2 树链剖分
    3. 1.3 SBT
    4. 1.4 splay
    5. 1.5 LCT
    6. 1.6 主席树
  2. 2 网络流
    1. 2.1 Dinic
    2. 2.2 MCF
  3. 3 字符串
    1. 3.1 KMP
    2. 3.2 后缀数组
    3. 3.3 AC自动机
    4. 3.4 Manacher
    5. 3.5 回文树
  4. 4 其他
    1. 4.1 STL
    2. 4.2 Tarjan
  5. 5 数学
    1. 5.1 exgcd
    2. 5.2 欧拉筛法
    3. 5.3 矩阵乘法
    4. 5.4 高斯消元
    5. 5.5 凸包
  6. 5.6 求质因子

1 数据结构

1.1 线段树

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
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5;
int n,m,tot,root;
struct Tree{
	int l,r,ls,rs,sum,max,tag;
}t[N*2];
void push_up(int x)
{
	int L=t[x].ls,R=t[x].rs;
	t[x].sum=t[L].sum+t[R].sum;
	t[x].max=max(t[L].max,t[R].max);
}
void push_down(int x)
{
	if(t[x].tag)
	{
		int L=t[x].ls,R=t[x].rs,T=t[x].tag;t[x].tag=0;
	 	t[L].sum+=(t[L].r-t[L].l+1)*T;t[L].max+=T;t[L].tag+=T;
		t[R].sum+=(t[R].r-t[R].l+1)*T;t[R].max+=T;t[R].tag+=T;
	}
}
void Build(int &x,int L,int R)
{
	x=++tot;
	t[x].l=L;t[x].r=R;
	if(L==R)
		{scanf("%d",&t[x].sum);t[x].max=t[x].sum;return;}
	int mid=(L+R)>>1;
	Build(t[x].ls,L,mid);
	Build(t[x].rs,mid+1,R);
	push_up(x);
}
void Change(int x,int pos,int key)
{
	if(t[x].l==t[x].r)
		{t[x].sum=t[x].max=key;return;}
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(pos<=mid) Change(t[x].ls,pos,key);
	else Change(t[x].rs,pos,key);
	push_up(x);
}
void Add(int x,int L,int R,int key)
{
	if(L<=t[x].l&&R>=t[x].r)
		{t[x].sum+=(t[x].r-t[x].l+1)*key;t[x].max+=key;t[x].tag+=key;return;}
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1;
	if(L<=mid) Add(t[x].ls,L,R,key);
	if(mid<R)  Add(t[x].rs,L,R,key);
	push_up(x);
}
int Sum(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].sum;
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1,sum=0;
	if(L<=mid) sum+=Sum(t[x].ls,L,R);
	if(R>mid)  sum+=Sum(t[x].rs,L,R);
	return sum;
}
int Max(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].max;
	push_down(x);
	int mid=(t[x].l+t[x].r)>>1,mx=0;
	if(L<=mid) mx=max(mx,Max(t[x].ls,L,R));
	if(R>mid)  mx=max(mx,Max(t[x].rs,L,R));
	return mx;
}
int main()
{
	freopen("tree.in","r",stdin);
	scanf("%d%d",&n,&m);
	Build(root,1,n);
	for(int i=1,t,x,y,z;i<=m;i++)
	{
		scanf("%d",&t);
		if(t==1)	  scanf("%d%d",&x,&y),Change(1,x,y);
		else if(t==2) scanf("%d%d%d",&x,&y,&z),Add(1,x,y,z);
		else if(t==3) scanf("%d%d",&x,&y),printf("%d\n",Sum(1,x,y));
		else scanf("%d%d",&x,&y),printf("%d\n",Max(1,x,y));
	}
}

1.2 树链剖分

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
#include<iostream>
#include<cstdio>
const int N=30010;
int n,Q,ans,tot,dep[N],fa[N],size[N],son[N],top[N],pos[N],a[N];
int head[N],next[N*2],to[N*2];
struct node{
	int l,r,ls,rs,max,sum;
}t[N*2];
void Dfs(int x)
{
	dep[x]=dep[fa[x]]+1;size[x]=1;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(y!=fa[x])
		{
			fa[y]=x;Dfs(y);
			size[x]+=size[y];
			if(size[y]>size[son[x]]) son[x]=y;
		}
}
void Dfs(int x,int f)
{
	pos[x]=++tot;top[x]=f;
	if(son[x]) Dfs(son[x],f);
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(y!=fa[x]&&y!=son[x])
			Dfs(y,y);
}
void push_up(int x)
{
	int L=t[x].ls,R=t[x].rs;
	t[x].sum=t[L].sum+t[R].sum;
	t[x].max=std::max(t[L].max,t[R].max);
}
void Build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	if(l==r) { t[x].max=t[x].sum=a[l];return; }
	int mid=(l+r)>>1;
	Build(t[x].ls=++tot,l,mid);
	Build(t[x].rs=++tot,mid+1,r);
	push_up(x);
}
void Change(int x,int num,int key)
{
	if(t[x].l==t[x].r) { t[x].max=t[x].sum=key;return; }
	int mid=(t[x].l+t[x].r)>>1;
	if(num<=mid) Change(t[x].ls,num,key);
	else Change(t[x].rs,num,key);
	push_up(x);
}
int Max(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].max;
	int mid=(t[x].l+t[x].r)>>1,num=-30001;
	if(L<=mid) num=std::max(num,Max(t[x].ls,L,R));
	if(R>mid)  num=std::max(num,Max(t[x].rs,L,R));
	return num;
}
int Sum(int x,int L,int R)
{
	if(L<=t[x].l&&R>=t[x].r) return t[x].sum;
	int mid=(t[x].l+t[x].r)>>1,num=0;
	if(L<=mid) num+=Sum(t[x].ls,L,R);
	if(R>mid)  num+=Sum(t[x].rs,L,R);
	return num;
}
int GetMax(int x,int y)
{
	for(ans=-30001;top[x]!=top[y];x=fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
		ans=std::max(ans,Max(1,pos[top[x]],pos[x]));
	}
	if(pos[x]>pos[y]) std::swap(x,y);
	return std::max(ans,Max(1,pos[x],pos[y]));
}
int GetSum(int x,int y)
{
	for(ans=0;top[x]!=top[y];x=fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
		ans+=Max(1,pos[top[x]],pos[x]);
	}
	if(pos[x]>pos[y]) std::swap(x,y);
	return ans+Max(1,pos[x],pos[y]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,ecnt=0,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		to[++ecnt]=y;next[ecnt]=head[x];head[x]=ecnt;
		to[++ecnt]=x;next[ecnt]=head[y];head[y]=ecnt;
	}
	Dfs(1);Dfs(1,1);
	for(int i=1;i<=n;i++) scanf("%d",&a[pos[i]]);
	Build(tot=1,1,n);
	scanf("%d",&Q);char s[10];
	for(int i=1,x,y;i<=Q;i++)
	{
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='C') Change(1,pos[x],y);
		else if(s[1]=='M') printf("%d\n",GetMax(x,y));
		else printf("%d\n",GetSum(x,y));
	}
}

1.3 SBT

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
114
115
116
117
118
119
120
121
122
123
124
#include<cstdio>
using namespace std;
const int N=1e5+5;
int tot,root,key[N],size[N],son[N][2];
void Rotate(int &x,bool flag) //0->left_rotate 1->right_rotate
{
	int y=son[x][!flag];
	son[x][!flag]=son[y][flag];
	son[y][flag]=x;
	size[y]=size[x];
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
	x=y;
}
void Maintain(int &x,bool flag) //0->ls 1-> rs
{
	if(size[son[son[x][flag]][flag]]>size[son[x][!flag]])
	  Rotate(x,!flag);
	else if(size[son[son[x][flag]][!flag]]>size[son[x][!flag]])
	  Rotate(son[x][flag],flag),Rotate(x,!flag);
	else return;
	Maintain(son[x][0],0);
	Maintain(son[x][1],1);
	Maintain(x,1);
	Maintain(x,0); 
}
void Insert(int &x,int y)
{
	if(!x)
	{
		x=++tot;
		key[x]=y;
		size[x]=1;
		son[x][0]=son[x][1]=0;
		return;
	}
	size[x]++;
	if(y<=key[x]) Insert(son[x][0],y);
	else Insert(son[x][1],y);
	Maintain(x,y>key[x]);
}
int Delete(int &x,int y)
{
	size[x]--;
	if((y<key[x]&&!son[x][0])||(y>key[x]&&!son[x][1])) return 0;
	if(y==key[x])
	{
		int ans=key[x];
		if(!son[x][0]||!son[x][1]) x=son[x][0]+son[x][1];
		else
		{
			int k=son[x][0]; while(son[k][1]) k=son[k][1]; 
			key[x]=Delete(son[x][0],key[k]);
		}
		return ans;
	}
	if(y<key[x]) return Delete(son[x][0],y);
	else return Delete(son[x][1],y);
}
int Find(int x,int y)
{
	if(!x) return 0;
	if(y==key[x]) return 1;
	else if(y<key[x]) return Find(son[x][0],y);
	else return Find(son[x][1],y);
}
int Rank(int x,int y)
{
	if(!x) return 1;
	else if(y<=key[x]) return Rank(son[x][0],y);
	else return size[son[x][0]]+1+Rank(son[x][1],y);
}
int Kth(int x,int y)
{
	if(y==size[son[x][0]]+1) return key[x];
	else if(y<=size[son[x][0]]) return Kth(son[x][0],y);
	else return Kth(son[x][1],y-size[son[x][0]]-1);
}
int Pred(int &x,int y)
{
	if(!x) return y;
	if(y<=key[x]) return Pred(son[x][0],y);
	else
	{
		int ans=Pred(son[x][1],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
int Succ(int &x,int y)
{
	if(!x) return y;
	if(y>=key[x]) return Succ(son[x][1],y);
	else
	{
		int ans=Succ(son[x][0],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
void Inorder(int x)
{
	if(x)
	{
		Inorder(son[x][0]);
		printf("%d ",key[x]);
		Inorder(son[x][1]);
	}
}
int main()
{
	freopen("sbt.in","r",stdin);
	int x,y;
	while(scanf("%d%d",&x,&y)!=EOF)
	{
		if(x==1) Insert(root,y);
		else if(x==2) Delete(root,y);
		else if(x==3) printf("%d\n",Find(root,y));
		else if(x==4) printf("%d\n",Rank(root,y));
		else if(x==5) printf("%d\n",Kth(root,y));
		else if(x==6) printf("%d\n",Pred(root,y));
		else printf("%d\n",Succ(root,y));
		//if(x<=2) Inorder(root),printf("\n");
	}
}

1.4 splay

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
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
const int N=1e5+5;
int tot,root,size[N],num[N],key[N],fa[N],son[N][2];
void push_up(int x)
{
	size[x]=size[son[x][0]]+size[son[x][1]]+num[x];
}
void Rotate(int x)
{
	//push_down(fa[x]);push_down(x); 
	int y=fa[x],z=fa[y],t=(son[y][0]==x);
	if(z) son[z][son[z][1]==y]=x;fa[x]=z;
	son[y][!t]=son[x][t];fa[son[y][!t]]=y;
	son[x][t]=y;fa[y]=x;
	push_up(y);push_up(x);
}
void Splay(int x,int f)
{
	while(fa[x]!=f)
	{
		int y=fa[x],z=fa[y];
		if(z!=f)
		{
			if(son[z][0]==y^son[y][0]==x) Rotate(x);
			else Rotate(y);
		} 
		Rotate(x);	
	}
	if(!f) root=x;
}
void Insert(int &x,int v,int f)
{
	if(!x)
	{
		x=++tot;
		son[x][0]=son[x][1]=0;
		size[x]=num[x]=1;
		key[x]=v;fa[x]=f;
		Splay(x,0);
		return;
	}
	if(v==key[x])
	{
		num[x]++;size[x]++;
		Splay(x,0);
		return;
	}
	Insert(son[x][v>key[x]],v,x);
	push_up(x);
}
int Get(int v)
{
	int x=root;
	while(x&&v!=key[x]) x=son[x][v>key[x]];
	return x;
}
void Delete(int x)
{
	x=Get(x);if(!x) return;
	Splay(x,0);
	if(num[x]>1) {num[x]--;size[x]--;return;}
	if(!son[x][0]||!son[x][1]) root=son[x][0]+son[x][1];
	else
	{
		int y=son[x][1];while(son[y][0]) y=son[y][0];
		Splay(y,x);
		son[y][0]=son[x][0];fa[son[y][0]]=y;
		root=y;
	}
	fa[root]=0;
	push_up(root);
}
int Rank(int v)
{
	Insert(root,v,0);
	int ans=size[son[root][0]]+1;
	Delete(v);
	return ans;
}
int Kth(int x)
{
	int y=root;
	while(x<=size[son[y][0]]||x>size[son[y][0]]+num[y])
	{
		if(x<=size[son[y][0]]) y=son[y][0];
		else x-=size[son[y][0]]+num[y],y=son[y][1];
	}
	return key[y];
}
int Pred(int v)
{
	Insert(root,v,0);
	int x=son[root][0];while(son[x][1]) x=son[x][1];
	Delete(v);
	return key[x];
}
int Succ(int v)
{
	Insert(root,v,0);
	int x=son[root][1];while(son[x][0]) x=son[x][0];
	Delete(v);
	return key[x];
}
void Inorder(int x)
{
	if(son[x][0]) Inorder(son[x][0]);
	for(int i=1;i<=num[x];i++) printf("%d ",key[x]);
	if(son[x][1]) Inorder(son[x][1]);
}
int main()
{
	for(int x,y;scanf("%d%d",&x,&y)!=EOF;)
	{
		if(x==1) Insert(root,y,0);
		else if(x==2) Delete(y);
		else if(x==3) printf("%d\n",Get(y));
		else if(x==4) printf("%d\n",Rank(y));
		else if(x==5) printf("%d\n",Kth(y));
		else if(x==6) printf("%d\n",Pred(y));
		else printf("%d\n",Succ(y));
		//if(x<=2) Inorder(root),printf("\n");
	}
}

1.5 LCT

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
#include <iostream>
#include <cstdio>
const int N=1e5;
int n,m,fa[N],son[N][2],size[N],key[N],sum[N],max[N],tag[N],rev[N];
inline bool isroot(int x)
{
	return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
inline void Add(int x,int v)
{
	key[x]+=v;sum[x]+=v*size[x];max[x]+=v;tag[x]+=v;
}
inline void push_up(int x)
{
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
	sum[x]=sum[son[x][0]]+sum[son[x][1]]+key[x];
	max[x]=std::max(std::max(max[son[x][0]],max[son[x][1]]),key[x]);
}
inline void push_down(int x)
{
	if(rev[x]) rev[x]^=1,rev[son[x][0]]^=1,rev[son[x][1]]^=1,std::swap(son[x][0],son[x][1]);
	if(tag[x]) Add(son[x][0],tag[x]),Add(son[x][1],tag[x]),tag[x]=0;
}
inline void Rotate(int x)
{
	push_down(fa[x]);push_down(x);
	int y=fa[x],z=fa[y],t=(son[y][0]==x);
	if(!isroot(y)) son[z][son[z][1]==y]=x;fa[x]=z;
	son[y][!t]=son[x][t];fa[son[y][!t]]=y;
	son[x][t]=y;fa[y]=x;
	push_up(y);push_up(x);
}
inline void Splay(int x)
{
	push_down(x);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(son[z][0]==y^son[y][0]==x) Rotate(x);
		    else Rotate(y);
		}  
		Rotate(x);
	}
}
inline void Access(int x) //将x到root的路径变成实路径
{
	for(int y=0;x;y=x,x=fa[x]) Splay(x),son[x][1]=y,push_up(x);
}
inline void Makeroot(int x) //将x变为root
{
	Access(x);Splay(x);rev[x]^=1;
}
inline void Split(int x,int y) //将x到y的路径放入splay，x为根
{
	Makeroot(x);Access(y);Splay(x);
}
inline void Link(int x,int y)
{
	Makeroot(x);fa[x]=y;
}
inline void Cut(int x,int y)
{
	Split(x,y);son[x][1]=fa[y]=0;
}
inline int Find(int x) //找到x所在树的root
{
	Access(x);Splay(x);while(son[x][0]) x=son[x][0];return x;
}
int main()
{
	max[0]=-0x7fffffff;
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)
	  scanf("%d",&x),size[i]=1,Add(i,x),tag[i]=0;
	for(int i=1,opt,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) Link(x,y);
		else if(opt==2) Cut(x,y);
		else if(opt==3) Splay(x),key[x]=y,push_up(x); //更改x的权值为y
		else if(opt==4) Split(x,y),printf("%d\n",max[x]); //求x到y路径上的最大值
		else if(opt==5) Split(x,y),printf("%d\n",sum[x]); //求x到y路径上的和
		else if(opt==6) printf("%d\n",Find(x)==Find(y));  //判断x和y是否连通
		else scanf("%d",&z),Split(x,y),Add(x,z);  //将x到y路径上加z
	}
}

1.6 主席树

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
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,tot,totn,a[N],b[N],root[N],size[N*20],ls[N*20],rs[N*20];
void Insert(int l,int r,int x,int &y,int v)
{
	y=++tot;
	size[y]=size[x]+1;
	ls[y]=ls[x];rs[y]=rs[x];
	if(l==r) return;
	int mid=(l+r)>>1;
	if(v<=mid) Insert(l,mid,ls[x],ls[y],v);
	else Insert(mid+1,r,rs[x],rs[y],v);
}
int Quary(int l,int r,int x,int y,int v)
{
	if(l==r) return l;
	int mid=(l+r)>>1,k=size[ls[y]]-size[ls[x]];
	if(v<=k) return Quary(l,mid,ls[x],ls[y],v);
	else return Quary(mid+1,r,rs[x],rs[y],v-k);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	totn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
	  Insert(1,totn,root[i-1],root[i],lower_bound(b+1,b+totn+1,a[i])-b);
	for(int i=1,x,y,z;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),printf("%d\n",b[Quary(1,totn,root[x-1],root[y],z)]);
}

2 网络流

2.1 Dinic

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N=5005,M=10005;
int n,m,S,T,ans,ecnt=1,ds[N],head[N],to[M<<1],rest[M<<1],next[M<<1];
std::queue<int> Q;
void Addedge(int x,int y,int z)
{
	to[++ecnt]=y;rest[ecnt]=z;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;next[ecnt]=head[y];head[y]=ecnt;
}
bool Bfs()
{
	memset(ds,0,sizeof(ds));
	Q.push(S);ds[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&!ds[y])
		    ds[y]=ds[x]+1,Q.push(y);
	}
	return ds[T];
}
int Dfs(int x,int flow)
{
	if(x==T) return flow;
	int a=0,b;
	for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
	  if(rest[e]&&ds[y]==ds[x]+1)
	  {
	  	b=Dfs(y,std::min(flow-a,rest[e]));
	  	rest[e]-=b;rest[e^1]+=b;a+=b;
	  	if(a==flow) break;
	  }
	if(!a) ds[x]=0;
	return a;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=1,x,y,z;i<=m;i++)
	  scanf("%d%d%d",&x,&y,&z),Addedge(x,y,z);
	while(Bfs()) ans+=Dfs(S,0x7fffffff);
	printf("%d\n",ans);
}

2.2 MCF

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
#include<cstdio>
#include<queue>
using namespace std;
const int inf=0x3fffffff;
const int N=100;
const int M=2000;
int n,m,S,T,ds[N],pre[N],maxflow,mincost;
int ecnt=1,st[N],to[M*2],rest[M*2],cost[M*2],next[M*2];
bool used[N];
queue<int> Q;
void Addedge(int x,int y,int r,int c)
{
	to[++ecnt]=y;rest[ecnt]=r;cost[ecnt]=c;next[ecnt]=st[x];st[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;cost[ecnt]=-c;next[ecnt]=st[y];st[y]=ecnt;
}
bool Spfa()
{
	for(int i=0;i<=T;i++) ds[i]=inf;
	Q.push(S);ds[S]=0;used[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();used[x]=0;
		for(int e=st[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&ds[y]>ds[x]+cost[e])
		  {
		  	ds[y]=ds[x]+cost[e];
		  	pre[y]=e;
		  	if(!used[y]) used[y]=1,Q.push(y); 
		  }
	}
	return ds[T]<inf;
}
void Update(int flow)
{
	for(int e=pre[T];e;e=pre[to[e^1]])
	  flow=min(flow,rest[e]);
	for(int e=pre[T];e;e=pre[to[e^1]])
	  rest[e]-=flow,rest[e^1]+=flow;
	maxflow+=flow;mincost+=flow*ds[T];
}
int main()
{
	scanf("%d%d",&n,&m);
	S=1;T=n;
	for(int i=1,u,v,r,c;i<=n;i++)
	  scanf("%d%d%d%d",&u,&v,&r,&c),Addedge(u,v,r,c);
	while(Spfa()) Update(inf);
	printf("Maxflow:%d\nMinflow:%d\n",maxflow,mincost);
}

3 字符串

3.1 KMP

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
#include<cstring>
#include<cstdio>
int n,m,next[100001];
char a[100001],b[100001];
void Getnext()
{
	next[0]=-1;
	for(int i=1,j=0;i<m;i++,j++)
	{
		while(j!=-1&&b[i]!=b[j]) j=next[j];
		next[i+1]=j+1;
	}
}
void KMP()
{
	for(int i=0,j=0;i<n;i++,j++)
	{
		while(j!=-1&&a[i]!=b[j]) j=next[j];
		if(j==m-1) printf("%d\n",i-j+1);
	}
}
int main()
{
	scanf("%s%s",a,b); //a->long b->short
	n=strlen(a);m=strlen(b);
	Getnext();
	KMP();
}

3.2 后缀数组

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int base=29;
int n,sa[10001];
char s[10001];
unsigned long long ha[10001],power[10001]={1};
inline unsigned long long HASH(int l,int r)
{
	return ha[r]-ha[l-1]*power[r-l+1];
}
inline int LCP(int x,int y)
{
	int l=0,r=std::min(n-x+1,n-y+1),mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(HASH(x,x+mid-1)==HASH(y,y+mid-1)) l=mid; else r=mid-1;
	}
	return l;
}
inline bool cmp(int x,int y)
{
	int z=LCP(x,y);return s[x+z]<s[y+z];
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	  ha[i]=ha[i-1]*base+s[i]-'a'+1,power[i]=power[i-1]*base,sa[i]=i;
	std::sort(sa+1,sa+n+1,cmp);
	for(int i=2;i<=n;i++) height[i]=LCP(sa[i-1],sa[i]);
}

3.3 AC自动机

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
#include <cstring>
#include <cstdio>
#include <queue>
const int N=500005;
int T,n,tot,end[N],fail[N],son[N][26];
char s[N*2];
std::queue<int> Q;
inline void init(int x)
{
	end[x]=0;
	for(int i=0;i<26;i++) son[x][i]=0;
}
inline void Add()
{
	scanf("%s",s);
	int len=strlen(s),pre=0;
	for(int i=0;i<len;i++)
	{
		if(!son[pre][s[i]-'a'])
		  init(son[pre][s[i]-'a']=++tot);
		pre=son[pre][s[i]-'a'];
	}
	end[pre]++;
}
inline void Build()
{
	Q.push(0);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<26;i++)
		{
			if(son[x][i])
			{
				Q.push(son[x][i]);
				fail[son[x][i]]=x?son[fail[x]][i]:0;
			}
			else son[x][i]=x?son[fail[x]][i]:0;
		}
	}
}
inline int Calc()
{
	scanf("%s",s);
	int len=strlen(s),pre=0,ans=0;
	for(int i=0;i<len;i++)
	{
		pre=son[pre][s[i]-'a'];
		for(int j=pre;j;j=fail[j])
		  ans+=end[j],end[j]=0;
	}
	return ans;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init(tot=0);
		for(scanf("%d",&n);n;n--) Add();
		Build();
		printf("%d\n",Calc());
	}
}

3.4 Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <cstdio>
int n,m,maxpos,maxlen,len[200001];
char s[100001],a[200001];
int main()
{
	scanf("%s",s);
	n=strlen(s);
	for(int i=0;i<n;i++) a[m++]='#',a[m++]=s[i];
	a[m++]='#';maxlen=-1;
	for(int i=0,j;i<m;i++)
	{
		j=std::min(len[maxpos*2-i],maxlen-i)*(i<=maxlen);
		while(i-j>=0&&i+j<=m&&a[i-j]==a[i+j]) j++;
		len[i]=j-1;
		if(i+j>maxlen) maxpos=i,maxlen=i+j;
	}
	for(int i=0;i<m;i++) printf("%d ",len[i]);
}

3.5 回文树

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
#include <cstring>
#include <cstdio> 
using namespace std;
const int N=1e6;
int n,LEN,tot,last,son[N][26],fail[N],len[N],num[N];
char s[N];
inline int newnode(int l)
{
	len[++tot]=l;
	return tot;
}
inline int getnode(int x)
{
	while(s[n-len[x]-1]!=s[n]) x=fail[x];
	return x;
}
inline void Add(int c)
{
	int cnt=getnode(last);
	if(!son[cnt][c])
	{
		int now=newnode(len[cnt]+2);
		fail[now]=son[getnode(fail[cnt])][c];
		son[cnt][c]=now;
	}
	num[last=son[cnt][c]]++;
}
int main()
{
	scanf("%s",s+1);
	LEN=strlen(s+1);
	newnode(-1);fail[0]=1;
	while(++n<=LEN) Add(s[n]-'a');
	for(int i=tot;i>=2;i--) num[fail[i]]+=num[i];
}

4 其他

4.1 STL

4.2 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
39
40
41
42
43
#include <iostream>
#include <cstdio>
const int N=1e4+5;
const int M=1e5+5;
int n,m,dfsnum,tot,top,ecnt,st[N],dfn[N],low[N],pos[N],head[N],to[M],next[M];
bool vis[N];
inline void Addedge(int x,int y)
{
	to[++ecnt]=y;next[ecnt]=head[x];head[x]=ecnt;
}
inline void Tarjan(int x)
{
	dfn[x]=low[x]=++dfsnum;
	vis[x]=1;
	st[++top]=x;
	for(int e=head[x],y=to[e];e;y=to[e=next[e]])
		if(!dfn[y])
			Tarjan(y),low[x]=std::min(low[x],low[y]);
		else if(vis[y])
			low[x]=std::min(low[x],dfn[y]);
	/*{//A一个奇怪的写法 
		if(!dfn[y]) Tarjan(y);
		if(vis[y]) low[x]=std::min(low[y],low[x]);
	}*/
	if(dfn[x]==low[x])
	{
		tot++;
		for(int y=-1;y!=x;)
		{
			y=st[top--];
			pos[y]=tot;
			vis[y]=0;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),Addedge(x,y);
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
}

5 数学

  1. 看
  1. 敲
  • exgcd 筛法 快速幂 矩阵乘法 高斯消元
  1. 背
  • 旋转卡壳 半平面角 凸包
  1. 学
  • 莫比乌斯反演 FFT

5.1 exgcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
using namespace std;
int a,b,c,d,x,y;
inline void exgcd(int a,int b,int &d,int &x,int &y)
{
	if(!b) d=a,x=1,y=0;
	else exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	exgcd(a,b,d,x,y);
	if(!(c%d))
	{
		x*=c/d;y*=c/d;a/=d;b/=d;
		for(int k=-2;k<=2;k++)
		printf("%d %d\n",x+k*b,y-k*a);
	}
}

5.2 欧拉筛法

\(phi[x]\) : \(1\)~\(x\)中与\(x\)互质的数的个数 \(phi[x]=x\times \prod\limits_{p|x} \frac{p-1}{p}\)
\(d[x]\) : x的因数的个数 \(d[x]=\prod\limits_{p|x} (p+1)\)
\(e[x]\) : x的最小素因子的个数
\(mu[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
31
32
33
34
35
36
37
#include<cstdio>
const int N=101;
int tot,prime[N],not_p[N],phi[N],d[N],e[N],mu[N];
int main()
{
	not_p[1]=1;d[1]=1;mu[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!not_p[i])
		{
			prime[++tot]=i;
			phi[i]=i-1;
			d[i]=2;
			e[i]=1;
			mu[i]=-1;
		} 
		for(int j=1,k=2*i;j<=tot&&k<N;k=prime[++j]*i)
		{
			not_p[k]=1;
			if(i%prime[j])
			{
				phi[k]=phi[i]*phi[prime[j]];
				d[k]=d[i]*d[prime[j]];
				e[k]=1;
				mu[k]=-mu[i];
			}
			else
			{
				phi[k]=phi[i]*prime[j];
				d[k]=d[i]/(e[i]+1)*(e[i]+2);
				e[k]=e[i]+1;
				mu[k]=0;
				break;
			}
		}
	}
}

5.3 矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstring>
#include <cstdio>
struct Matrix{
	int m[11][11],W,H;
};
Matrix operator * (const Matrix a,const Matrix b) //默认a.W==b.H
{
	Matrix c;  
	c.H=a.H;c.W=b.W;
	memset(c.m,0,sizeof(c.m));
	for(int i=1;i<=c.H;i++)
	  for(int j=1;j<=c.W;j++)
	  	for(int k=1;k<=a.W;k++)
	      c.m[i][j]+=a.m[i][k]*b.m[k][j];
	return c;
}

5.4 高斯消元

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
#include <iostream>
#include <cstdio>
const int N=1001;
int n,m,line,row,a[N][N+1],sure[N];
inline int gcd(int x,int y)
{
	return !y?x:gcd(y,x%y);
}
inline int Guass()
{
	for(line=row=1;line<=n&&row<=m;line++,row++) //line->hang row->lie 
	{
		int t=line;while(t<=n&&!a[t][row]) t++;
		if(t>n) {line--;continue;}
		if(t!=line) std::swap(a[t],a[line]);
		for(int i=1;i<=n;i++)
			if(i!=line&&a[i][row])
			{
				int d=gcd(a[i][row],a[line][row]);
				int ta=a[line][row]/d,tb=a[i][row]/d;
				for(int j=1;j<=m+1;j++)
					a[i][j]=a[i][j]*ta-a[line][j]*tb;
			}
	}
	line--;row--;
	for(int i=line+1;i<=n;i++)
	  if(a[i][m+1]) return -1;
	if(line<m)
	{
		for(int i=1;i<=m;i++) sure[i]=-1;
		for(int i=line;i;i--)
		{
			int cnt=0,num;
			for(int j=1;j<=m;j++)
			  if(a[i][j]&&sure[j]==-1) cnt++,num=j;
			if(cnt==1) sure[num]=a[i][m+1];
		}
		return 1;
	} 
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m+1;j++)
	    scanf("%d",&a[i][j]);
	Guass();
}

5.5 凸包

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
#include <algorithm>
#include <cstdio>
#include <cmath>
const int N=1e5+5;
const double eps=1e-6;
int n,top;
double len,S;
struct Point { double x,y; } a[N],b[N];
double dis(Point x,Point y)
{
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double Cross(Point x,Point y,Point z)
{
	return (x.x-z.x)*(y.y-z.y)-(x.y-z.y)*(y.x-z.x);
}
double Cross(Point x,Point y)
{
	return x.x*y.y-x.y*y.x;
}
bool cmp(const Point &x,const Point &y)
{
	double t=Cross(x,y,a[1]);return abs(t)>eps?t>0:dis(a[1],x)<dis(a[1],y);
}
inline void Graham()
{
	int t=1;
	for(int i=2;i<=n;i++)
	  if(a[i].x<a[t].x||(a[i].x==a[t].x&&a[i].y<a[t].y)) t=i;
	if(t!=1) std::swap(a[t],a[1]);
	std::sort(a+2,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&Cross(a[i],b[top],b[top-1])>=0) top--;
		b[++top]=a[i];
	}
	b[top+1]=b[1];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	Graham();
	for(int i=1;i<=top;i++) len+=dis(b[i],b[i+1]);
	printf("L: %.8lf\n",len);
	for(int i=1;i<=top;i++) S+=Cross(b[i],b[i+1]);
	printf("S: %.8lf\n",S/2);
}

5.6 求质因子

Miller_Rabin & Pollard_rho

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
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
inline int power(int a,int b,int P)
{
	int c=1;
	for(;b;b>>=1,a=(long long)a*a%P)
		if(b&1) c=(long long)c*a%P;
	return c;
}
inline bool Prime(int base,int x)
{
	if(base==x) return 1;
	for(int i=x-1;;i>>=1)
	{
		int y=power(base,i,x);
		if(y==x-1) return 1;
		if(y!=1) return 0;
		if(i&1) return 1;
	}
}
inline bool Miller_Rabin(int x)
{
	if(x==2) return 1;
	else if(x<2||!(x&1)) return 0;
	for(int i=1;i<=10;i++)
		if(!Prime(rand()%(x-1)+1,x))
			return 0;
	return 1;
} 
inline int gcd(int x,int y)
{
	return !y?x:gcd(y,x%y);
}
inline int Pollard_rho(int n,int a)
{
	for(int i=1,k=1,x=rand()%n,y=x;;i++)
	{
		x=((long long)x*x%n+a)%n;
		int d=gcd(abs(y-x),n);
		if(d>1&&d<n) return d;
		if(x==y) return n;
		if(i==k) y=x,k<<=1;
	}
}
inline void findfac(int n)
{
	if(Miller_Rabin(n))
	{ 
		printf("%d ",n);return;
	}
	int p=n;
	while(p>=n) p=Pollard_rho(p,rand()%(n-1)+1);
	findfac(p);findfac(n/p);
}
int main()
{
	std::srand(time(NULL));
	int n;
	while(scanf("%d",&n))
		findfac(n),printf("\n");
}