省选复习

  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 求质因子

HAOI加油↖(^ω^)↗

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 数学

    • 斐蜀定理 更相减损术 欧拉函数 费马小定理 中国剩余定理 lucas定理( C(n,m)%p=C(n÷p,m÷p)×C(n%p,m%p) C(n,m) \% p = C(n\div p,m\div p) \times C(n\% p,m\% p) ) 乘法逆元 行列式 MatrixTree定理 博弈 SG函数 容斥原理 模线性方程组
    • 概率期望 组合数学 数论 计算几何
    • exgcd 筛法 快速幂 矩阵乘法 高斯消元
    • 旋转卡壳 半平面角 凸包
    • 莫比乌斯反演 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]phi[x] : 11~xx中与xx互质的数的个数 phi[x]=x×pxp1pphi[x]=x\times \prod\limits_{p|x} \frac{p-1}{p}
d[x]d[x] : x的因数的个数 d[x]=px(p+1)d[x]=\prod\limits_{p|x} (p+1)
e[x]e[x] : x的最小素因子的个数
mu[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");
}