ACM模板

  1. 0 其他
    1. vimrc
    2. 对拍
  2. 1 数据结构
    1. 1.1 线段树
    2. 1.2 树状数组
    3. 1.3 树链剖分
    4. 1.4 SBT
    5. 1.5 splay
    6. 1.6 LCT
    7. 1.7 主席树
  3. 2 字符串
    1. 2.1 KMP
    2. 2.2 后缀数组
    3. 2.3 SAM后缀自动机
    4. 2.4 AC自动机
    5. 2.5 Manacher
    6. 2.6 回文树
  4. 3 数学
    1. 3.1 数论
      1. 3.1.1 中国剩余定理
      2. 3.1.2 lucas定理
      3. 3.1.3 欧拉定理
      4. 3.1.4 莫比乌斯反演
      5. 3.1.5 快速幂
      6. 3.1.6 exgcd
      7. 3.1.7 欧拉筛法
      8. 3.1.8 求质因子
      9. 3.1.9 FFT
      10. 3.1.10 NTT
    2. 3.2 组合数学
    3. 3.3 计算几何
      1. 3.3.1 凸包
      2. 3.3.2 半平面交
      3. 3.3.3 旋转卡壳
    4. 3.4 概率期望
    5. 3.5 矩阵
      1. 3.5.1 矩阵乘法
      2. 3.5.2 高斯消元
    6. 3.6 博弈论
  5. 4 图论
    1. 4.1 Tarjan
    2. 4.2 最短路
    3. 4.3 最小生成树
    4. 4.4 LCA
  6. 5 网络流
    1. 5.1 Dinic
    2. 5.2 ISAP
    3. 5.3 MCF
    4. 5.4 上下界网络流
  7. 6 其他
    1. 6.1 读入优化
    2. 6.2 STL
      1. 6.2.1 set
      2. 6.2.2 vector

0 其他

vimrc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
set ts=4 "tapstop
set sw=4 "shiftwidth
set sc "showcmd
set nu "number
set ru "ruler
set ai "autoindent
set mouse=a
filetype indent on
set et "expandtab
set smarttab
set autowrite
inoremap { {}<LEFT>
inoremap {<CR> {}<LEFT><CR><CR><UP><TAB>
inoremap } {<CR><ESC>A<CR>}<UP><ESC>A
map <F5> :w<CR> :!gdb %< -q <CR>
map <F9> :w<CR> :!g++ % -o %< -g -Wall<CR>
map <F10> :w<CR> :!time ./%< <CR>

对拍

1
2
3
4
5
6
7
8
9
10
while true; do
./data > a.in
./a > a.out
./std > std.out
if diff a.out std.out; then
echo AC
else
exit 0
fi
done

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
inline int Sum(int x){
int sum=0;
for(;x;x-=x&(-x)) sum+=c[x];
return sum;
}
inline void Add(int x,int v){
for(;x<=n;x+=x&(-x)) c[x]+=v;
}

1.3 树链剖分

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.4 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.5 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.6 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.7 主席树

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 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();
}

2.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]);
}
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
#include<cstdio>
const int N=10001;
int r[N],sa[N],a[N],b[N],v[N],s[N],rank[N],height[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=a,*y=b,*z;
for(i=0;i<m;i++) s[i]=0;
for(i=0;i<n;i++) s[x[i]=r[i]]++;
for(i=1;i<m;i++) s[i]+=s[i-1];
for(i=n-1;i>=0;i--) sa[--s[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) v[i]=x[y[i]];
for(i=0;i<m;i++) s[i]=0;
for(i=0;i<n;i++) s[v[i]]++;
for(i=1;i<m;i++) s[i]+=s[i-1];
for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=0;i<n;i++) rank[sa[i]]=i;//论文1~n
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

2.3 SAM后缀自动机

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 <cstring>
#include <cstdio>
const int N=10005;
char s[N];
int last,cnt,n,len[N<<1],fa[N<<1],son[N<<1][26];
inline void Add(int x)
{
int c=s[x]-'a',p=last,np=++cnt;
len[last=np]=x;
for(;p&&!son[p][c];p=fa[p]) son[p][c]=np;
if(!p) fa[np]=1;
else
{
int q=son[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else
{
int nq=++cnt;
len[nq]=len[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for(;son[p][c]==q;p=fa[p]) son[p][c]=nq;
}
}
}
int main()
{
scanf("%s",s+1);
last=cnt=1;
n=strlen(s+1);
for(int i=1;i<=n;i++) Add(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
struct NODE{
int par, go[cL];
int len,s;
}nodes[maxn*2];
int cn=1;
int root, last;
struct LIST{
int v;
int next;
}list[maxn*2];
int cl=1,head[maxn];
void addList(int v, int h){
list[cl]=(LIST){v,head[h]};
head[h]=cl++;
}
int newNode(int len,int s){
int ret = cn++;
nodes[ret].len=len;
nodes[ret].s=s;
nodes[ret].par=0;
memset(nodes[ret].go,0,sizeof(nodes[ret].go));
addList(ret, len);
return ret;
}
void extend(int w){
int p=last, np=newNode(nodes[p].len+1,1);
while(p && !nodes[p].go[w]){
nodes[p].go[w] = np;
p=nodes[p].par;
}
if(!p){
nodes[np].par = root;
}else{
int q = nodes[p].go[w];
if(nodes[p].len + 1 == nodes[q].len){
nodes[np].par=q;
}else{
int nq = newNode(nodes[p].len+1,0);
memcpy(nodes[nq].go, nodes[q].go, sizeof(nodes[nq].go));
nodes[nq].par = nodes[q].par;
nodes[q].par = nq;
nodes[np].par = nq;
while(p && nodes[p].go[w] == q){
nodes[p].go[w] = nq;
p=nodes[p].par;
}
}
}
last=np;
}

2.4 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());
}
}

2.5 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]);
}

2.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
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];
}

3 数学

3.1 数论

3.1.1 中国剩余定理

的解为 .其中M=i=1nmiM=\prod\limits_{i=1}^nm_i, Mi=MmiM_i=\frac{M}{m_i}, .

3.1.2 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) .

3.1.3 欧拉定理

.

3.1.4 莫比乌斯反演

μ(d)\mu(d) 的定义:
(1) 若 d=1d=1,则μ(d)=1\mu(d)=1
(2) 若 pip_i为互异素数,则μ(d)=(1)k\mu(d)=(-1)^k
(3) 其他情况下 μ(d)=0\mu(d)=0

莫比乌斯反演:
F(n)=dnf(d)f(n)=dnμ(d)F(nd).F(n)=\sum\limits_{d|n} f(d) \Rightarrow f(n)=\sum\limits_{d|n}\mu(d) F(\frac{n}{d}).
F(n)=ndf(d)f(n)=ndμ(dn)F(d).F(n)=\sum\limits_{n|d} f(d) \Rightarrow f(n)=\sum\limits_{n|d}\mu(\frac{d}{n}) F(d).

3.1.5 快速幂

1
2
3
4
5
6
7
int power(int a,int b,int P)
{
int re=1;
for(;b;b>>=1,a=(long long)a*a%P)
if(b&1) re=(long long)re*a%P;
return re;
}

3.1.6 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;
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);
}
}

3.1.7 欧拉筛法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}
}
}
}
LL Phi(LL x) //单独求欧拉函数
{
LL i,re=x;
for(i=2;i*i<=x;i++)
if(x%i==0)
{
re/=i;
re*=i-1;
while(x%i==0)
x/=i;
}
if(x!=1)
re/=x,re*=(x-1);
return re;
}

3.1.8 求质因子

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");
}

3.1.9 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
28
29
30
31
32
33
34
35
#include <complex>
#include <cstdio>
const double pi=acos(-1);
int len1,len2,n,m,rev[262200];
std::complex<double> a[262200],b[262200];
inline void FFT(std::complex<double> *a,int f)
{
for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1)
{
std::complex<double> wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=(i<<1))
{
std::complex<double> w(1,0);
for(int k=0;k<i;k++,w*=wn)
{
std::complex<double> x=a[j+k],y=a[j+k+i]*w;
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
}
int main()
{
scanf("%d%d",&len1,&len2);
for(int i=0;i<=len1;i++) scanf("%lf",&a[i].real());
for(int i=0;i<=len2;i++) scanf("%lf",&b[i].real());
for(n=1,m=0;n<=len1+len2;n<<=1,m++);
// m=ceil(log(len1+len2+1)/log(2)),n=1<<m;
for(int i=0;i<n;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(m-1);
FFT(a,1);FFT(b,1);
for(int i=0;i<n;i++) a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<=len1+len2;i++) printf("%d ",(int)(a[i].real()/n+0.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
typedef complex<double> cmplx;
double Pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172;
void rev_inc(int &v,int n){
n>>=1;
while(v&n){v^=n;n>>=1;}
v^=n;
}
void DFT(cmplx *a,int len,int dir){
int n=1<<len;
for(int i=1,j=n>>1;i<n;++i,rev_inc(j,n)) if(i<j) swap(a[i],a[j]);
for(int i=0;i<len;++i){
int m=1<<i;
cmplx wm(cos(Pi/m),dir*sin(Pi/m));
for(int j=0;j<n;j+=(m<<1)){
cmplx w(1);
for(int k=0;k<m;++k){
cmplx u=a[j+k],t=w*a[j+k+m];
a[j+k]=u+t;
a[j+k+m]=u-t;
w*=wm;
}
}
}
if(dir==-1) for(int i=0;i<n;++i) a[i]/=n;
}
void multiply(cmplx *a,cmplx *b,int n,cmplx *c){
int l=log2(n-1)+2;
n=1<<l;
DFT(a,l,1);
DFT(b,l,1);
for(int i=0;i<n;++i) c[i]=a[i]*b[i];
DFT(c,l,-1);
for(int i=0;i<n;++i) a[i]=b[i]=0;
}

3.1.10 NTT

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
#include <iostream>
#include <cstdio>
#define Inv(x) (power(x,P-2))
const int P=(479<<21)+1;
const int G=3;
int len1,len2,n,m,rev[262200],a[262200],b[262200];
inline int power(int x,int y)
{
int z=1;
for(;y;y>>=1,x=(long long)x*x%P)
if(y&1) z=(long long)z*x%P;
return z;
}
inline void NTT(int *a,int f)
{
for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
for(int i=1,t=1;i<n;i<<=1,t++)
{
int wn=power(G,(P-1)/(1<<t));
if(f==-1) wn=Inv(wn);
for(int j=0;j<n;j+=(i<<1))
for(int k=0,w=1;k<i;k++,w=(long long)w*wn%P)
{
int x=a[j+k],y=(long long)a[j+k+i]*w%P;
a[j+k]=(x+y)%P;a[j+k+i]=(x-y+P)%P;
}
}
}
int main()
{
scanf("%d%d",&len1,&len2);
for(int i=0;i<=len1;i++) scanf("%d",&a[i]);
for(int i=0;i<=len2;i++) scanf("%d",&b[i]);
for(n=1,m=0;n<=len1+len2;n<<=1,m++);
for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1)<<(m-1);
NTT(a,1);NTT(b,1);
for(int i=0;i<n;i++) a[i]=(long long)a[i]*b[i]%P;
NTT(a,-1);n=Inv(n);
for(int i=0;i<=len1+len2;i++) printf("%lld ",(long long)a[i]*n%P);
}

3.2 组合数学

3.3 计算几何

3.3.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
#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);
}

3.3.2 半平面交

求交点:(不小心把x轴画到了O上)
k1=(b.b-a.a)*(a.b-a.a) 即三角形ACD的面积
k2=(a.b-a.a)*(b.a-a.a) 即三角形ABC的面积
∴ S△ACD/S△ABC = DF/BE = OF/OE = OH/OG = k1/k2
∴ OG = GH * k1/(k1+k2)
∴ O的坐标就求出来了

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<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,cnt,tot;
struct node1 { double x,y; } p[55],a[505];
struct node2 { node1 a,b; double k; } l[505],q[505];
node1 operator -(node1 a,node1 b)
{ node1 t;t.x=a.x-b.x;t.y=a.y-b.y;return t; }
double operator *(node1 a,node1 b)
{ return a.x*b.y-a.y*b.x; }
bool operator <(node2 a,node2 b)
{ return a.k==b.k?(a.b-a.a)*(b.b-a.a)<0:a.k<b.k; }
node1 Inter(node2 a,node2 b)
{
double k1,k2,t;
k1=(b.b-a.a)*(a.b-a.a);
k2=(a.b-a.a)*(b.a-a.a);
t=k1/(k1+k2);
node1 ans;
ans.x=b.b.x+(b.a.x-b.b.x)*t;
ans.y=b.b.y+(b.a.y-b.b.y)*t;
return ans;
}
bool jud(node2 a,node2 b,node2 c)
{
return (c.b-c.a)*(Inter(a,b)-c.a)<0;
}
double calc()
{
sort(l+1,l+cnt+1);
int L=1,R=0;
for(int i=1;i<=cnt;i++)
if(l[i].k!=l[i-1].k) l[++tot]=l[i];
for(int i=1;i<=tot;i++)
{
while(L<R&&jud(q[R-1],q[R],l[i])) R--;
while(L<R&&jud(q[L+1],q[L],l[i])) L++;
q[++R]=l[i];
}
while(L<R&&jud(q[R-1],q[R],l[L])) R--;
while(L<R&&jud(q[L+1],q[L],l[R])) L++;
q[R+1]=q[L];tot=0;
for(int i=L;i<=R;i++) a[++tot]=Inter(q[i],q[i+1]);
a[++tot]=a[1];
if(tot<3) return 0;
double ans=0;
for(int i=1;i<=tot;i++) ans+=a[i]*a[i+1];
return fabs(ans)/2;
}
int main()
{
scanf("%d",&n);
for(int i=1,k;i<=n;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++) scanf("%lf%lf",&p[j].x,&p[j].y);
p[k+1]=p[1];
for(int j=1;j<=k;j++) l[++cnt].a=p[j],l[cnt].b=p[j+1];
}
for(int i=1;i<=cnt;i++)
l[i].k=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
printf("%.3lf",calc());
}

3.3.3 旋转卡壳

求最远点对距离

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
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,top;
struct node{
int x,y;
}a[50005],b[50005];
node operator -(node a,node b)
{
node t;
t.x=a.x-b.x;t.y=a.y-b.y;
return t;
}
int operator *(node a,node b)
{
return a.x*b.y-a.y*b.x;
}
int dis(node a,node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool operator <(node aa,node bb)
{
int t=(aa-a[1])*(bb-a[1]);
return (!t)?dis(aa,a[1])<dis(bb,a[1]):t>0;
}
void Graham()
{
int k=1;
for(int i=2;i<=n;i++)
if(a[i].x<a[k].x||(a[i].x==a[k].x)&&a[i].y<a[k].y) k=i;
if(k!=1) swap(a[k],a[1]);
sort(a+2,a+n+1);
for(int i=1;i<=n;i++)
{
while(top>1&&(a[i]-b[top-1])*(b[top]-b[top-1])>=0) top--;
b[++top]=a[i];
}
b[top+1]=b[1];
}
int Calc()
{
int q=2,ans=0;
for(int i=1;i<=top;i++)
{
while((b[i+1]-b[i])*(b[q+1]-b[i])>(b[i+1]-b[i])*(b[q]-b[i]))
q=q%top+1;
ans=max(ans,dis(b[q],b[i]));
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
Graham();
printf("%d\n",Calc());
}

求两个凸多边形最近距离

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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-10
using namespace std;
struct node{ double x,y; }a[10005],b[10005],t;
double ans;
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Cross(node a,node b,node c)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
double Dot(node a,node b,node c)
{
return (a.x-c.x)*(b.x-c.x)+(a.y-c.y)*(b.y-c.y);
}
bool cmp(node aa,node bb)
{
double k=Cross(aa,bb,t);
return (!k)?dis(aa,t)<dis(bb,t):k>0;
}
void Sort(node *a,int n)
{
int k=1;
for(int i=2;i<=n;i++) if((a[k].y>a[i].y)||(a[k].y==a[i].y&&a[k].x>a[i].x)) k=i;
t=a[k];
sort(a+1,a+n+1,cmp);
}
void Add(node x,node y,node z)
{
if(Dot(z,y,x)/dis(x,z)/dis(x,y)<-eps) ans=min(ans,dis(x,z));
else if(Dot(x,z,y)/dis(y,z)/dis(x,y)<-eps) ans=min(ans,dis(y,z));
else ans=min(ans,fabs(Cross(z,y,x))/dis(x,y));
}
void Calc(node *a,node *b,int n,int m)
{
int P=1,Q=1;
for(int i=1;i<=n;i++) if(a[i].y<a[P].y) P=i;
for(int i=1;i<=m;i++) if(b[i].y>b[Q].y) Q=i;
for(int i=1,t;i<=n;i++)
{
while(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<-eps) Q=Q%m+1;
Add(a[P],a[P+1],b[Q]);
if(Cross(b[Q+1],a[P+1],a[P])-Cross(b[Q],a[P+1],a[P])<eps) Add(a[P],a[P+1],b[Q+1]);
P=P%n+1;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n)
{
ans=30000;
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=m;i++) scanf("%lf%lf",&b[i].x,&b[i].y);
Sort(a,n);Sort(b,m);
a[n+1]=a[1];b[m+1]=b[1];
Calc(a,b,n,m);Calc(b,a,m,n);
printf("%.6lf\n",ans);
}
}

3.4 概率期望

3.5 矩阵

3.5.1 矩阵乘法

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;
}

3.5.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
#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();
}
  • 行列式
  • MatrixTree定理

3.6 博弈论

4 图论

4.1 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
#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]);
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);
}

4.2 最短路

SPFA O(kE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
memset(ds,0x7f,sizeof(ds));
ds[S]=0; vis[S]=1; q.push(S);
while(!q.empty())
{
int x=q.front(); q.pop(); vis[x]=0;
for(int i=0;i<to[x].size();i++)
{
int y=to[x][i],c=cost[x][i];
if(ds[y]>ds[x]+c)
{
ds[y]=ds[x]+c;
if(!vis[y])
{
vis[y]=1; q.push(y);
}
}
}
}

Dijkstra O(n*logn)

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
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=10005;
const int M=100005;
const int inf=0x7fffffff;
int st[N],next[2*M],ed[2*M],cost[2*M],tot,ds[N],n,m;
inline void add(int x,int y,int z)
{
next[++tot]=st[x],st[x]=tot,ed[tot]=y,cost[tot]=z;
}
struct node{
int x,d;
inline node(int a,int b):x(a),d(b){}
inline bool operator<(const node&t) const{return d>t.d;}
};
priority_queue<node> q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
int S=1,T=n;
for(int i=1;i<=n;i++) ds[i]=inf;
q.push(node(S,0));
while(!q.empty()){
node x=q.top(); q.pop();
if(ds[x.x]<inf) continue;
ds[x.x]=x.d;
for(int now=st[x.x];now;now=next[now])
q.push(node(ed[now],x.d+cost[now]));
}
printf("%d\n",ds[T]);
}

4.3 最小生成树

Kruskal O(E*logE)

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
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,x,y,z,f1,f2,tot,k,fa[1001];
struct node{
int x,y,v;
}a[10001];
int cmp(const node &a,const node &b)
{
return a.v<b.v;
}
int father(int x)
{
return fa[x]==x?x:fa[x]=father(fa[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
x=a[i].x;y=a[i].y;z=a[i].v;
f1=father(x);f2=father(y);
if(f1==f2) continue;
fa[f1]=f2;tot+=z;k++;
if(k==n-1) break;
}
printf("%d",tot);
}

4.4 LCA

注意dep[1]=1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=log(n)/log(2)+1;i++)
for(int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],
//g[j][i]=max(g[j][i-1],g[fa[j][i-1]][i-1]);
int lca(int x,int y)
{
//int ans=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=log(n)/log(2);i>=0;i--)
if(dep[fa[x][i]]>=dep[y])
//ans=max(ans,g[x][i]),
x=fa[x][i];
if(x==y) return x;
for(int i=log(n)/log(2);i>=0;i--)
if(fa[x][i]!=fa[y][i])
//ans=max(ans,g[x][i]),ans=max(ans,g[y][i]),
x=fa[x][i],y=fa[y][i];
//ans=max(ans,g[x][0]);ans=max(ans,g[y][0]);
return fa[x][0];
}

5 网络流

5.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);
}

5.2 ISAP

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
int source; // 源点
int sink; // 汇点
int p[max_nodes]; // 可增广路上的上一条弧的编号
int num[max_nodes]; // 和 t 的最短距离等于 i 的节点数量
int cur[max_nodes]; // 当前弧下标
int d[max_nodes]; // 残量网络中节点 i 到汇点 t 的最短距离
bool visited[max_nodes];
// 预处理, 反向 BFS 构造 d 数组
bool bfs()
{
memset(visited, 0, sizeof(visited));
queue<int> Q;
Q.push(sink);
visited[sink] = 1;
d[sink] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) {
Edge &e = edges[(*ix)^1];
if (!visited[e.from] && e.capacity > e.flow) {
visited[e.from] = true;
d[e.from] = d[u] + 1;
Q.push(e.from);
}
}
}
return visited[source];
}
// 增广
int augment()
{
int u = sink, df = __inf;
// 从汇点到源点通过 p 追踪增广路径, df 为一路上最小的残量
while (u != source) {
Edge &e = edges[p[u]];
df = min(df, e.capacity - e.flow);
u = edges[p[u]].from;
}
u = sink;
// 从汇点到源点更新流量
while (u != source) {
edges[p[u]].flow += df;
edges[p[u]^1].flow -= df;
u = edges[p[u]].from;
}
return df;
}
int max_flow()
{
int flow = 0;
bfs();
memset(num, 0, sizeof(num));
for (int i = 0; i < num_nodes; i++) num[d[i]]++;
int u = source;
memset(cur, 0, sizeof(cur));
while (d[source] < num_nodes) {
if (u == sink) {
flow += augment();
u = source;
}
bool advanced = false;
for (int i = cur[u]; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if (e.capacity > e.flow && d[u] == d[e.to] + 1) {
advanced = true;
p[e.to] = G[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if (!advanced) { // retreat
int m = num_nodes - 1;
for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix)
if (edges[*ix].capacity > edges[*ix].flow)
m = min(m, d[edges[*ix].to]);
if (--num[d[u]] == 0) break; // gap 优化
num[d[u] = m+1]++;
cur[u] = 0;
if (u != source)
u = edges[p[u]].from;
}
}
return flow;
}

5.3 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);
}

5.4 上下界网络流

一、无源汇

  1. 可行流

可以想到为了满足流量的下限 lowlow,将边的流量设为 highlowhigh-low
但是求出这个图的最大流之后,加上 lowlow,会使得某些点不满足流量平衡。
所以可以建立附加源和附加汇,来补充和吸收这些流量。

法一:
由于下届是一条弧上的流必需要满足的确定值。下面引出必要弧的概念:必要弧是一定流要满的弧。必要弧的构造,讲容量下界的限制分离开了,从而构造了一个没有下界的网络GG'
1.将原弧(u,v)(u,v)分离出一条必要弧:c(u,v)nes=b(u,v)c'(u,v)_ {nes}=b(u,v).(红色表示)
2.原弧:c(u,v)=c(u,v)b(u,v)c'(u,v)=c(u,v)-b(u,v). 由于必要弧的有一定要满的限制,将必要弧“拉”出来集中考虑: 添加附加源xx,附加汇yy。想象一条不限上届的(y,x)(y,x),有必要弧将它们“串”起来,即对于有向必要弧(u,v)(u,v),添加(u,y),(x,v)(u,y),(x,v),容量为必要弧容量。这样就建立了一个等价的网络。 一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉(y,x)(y,x)后,附加源xx到汇yy的最大流,能使得xx的出弧或者yy的入弧都满,充要于原图有可行流。 即对于一条边 (u,v)(u,v) ,在图中建三条边 (u,v,highlow),(S,v,low),(u,T,low)(u,v,high-low) , (S,v,low) , (u,T,low)

法二:
发现上图中存在许多流量可以直接从 SS 经过点 xxTT ,这样的流量对答案没有贡献
所以考虑 du[i]du[i] 表示点 ii 的入度-出度,则如果 du[i]>0du[i] > 0,建边(S,i,du[i]) (S,i,du[i]) ;否则建边(i,T,du[i]) (i,T,-du[i])。这样就省去了不少空间。

二、有源汇

  1. 可行流
    TTSS 连一条 [0,inf][0,inf] 的边,有源汇就变成了无源汇,就和上面一样了

  2. 最大流

法一:
二分最大流量,判断是否可行
TT->SS 的边的流量为 [x,inf][x,inf]
1 . x>ansx>ansmin(T>S)>max(S>T)min(T->S) > max(S->T) ,会使求新网络的无源汇可行流无解的(S,T流量怎样都不能平衡)
2 . x<=ansx<=ans 会有解.

法二:
1 . 连上 TT->SS 流量为 infinf 的边,求一次附加源到附加汇的最大流,若不满流则无解
2 . 在残量网络上求一次 sstt 的最大流
3 . 答案就是第二次求出的最大流(因为第一次求出的最大流是 TT->SS 的流量,而这个流量在他的反向边 ss->tt 中出现,所以不需要另外加上)

第一次求出的最大流是为了满足 lowlow 尽可能流满,然而此时 ss->tt 上可能还有可行的流,我们在残量网络上继续来求最大流,可以使得最后求出的流既满足 的限制,且最大。

  1. 最小流

法一:
二分最小流量,判断是否可行
TT->SS 的边的流量为 [0,x][0,x]

法二:
1 . 先不连 TT->SS 流量为 infinf 的边,求一次附加源到附加汇的最大流
2 . 再连上 TT->SS 流量为 infinf 的边,在残量网络上求一次 sstt 的最大流
3 . 若最后满流,则答案为 TT->SS 的反向边的流量

因为第一遍做的时候并无这条边,所以 ss->tt的流量在第一遍做的时候都已经尽力往其他边流了.
于是加上 TT->SS 这条边后,都是些剩余的流不到其他边的流量. 从而达到尽可能减少 TT->SS 这边上的流量的效果,即减小了最终答案.

6 其他

6.1 读入优化

1
2
3
4
5
6
7
int read()
{
int 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;
}

6.2 STL

6.2.1 set

set:不可重复 multiset:可重复

基本操作:

  1. begin() : 返回第一个元素的位置
  2. end() : 返回最后一个元素的位置
  3. clear() : 删除set容器中的所有的元素
  4. empty() : 判断set容器是否为空
  5. size() : 返回当前set容器中的元素个数
  6. count() : 某个键值出现的次数
  7. find() : 返回给定值值得定位器,如果没找到则返回end()
  8. 遍历:for(set<int>::iterator iter=s.begin();iter!=s.end();iter++) printf("%d ",*iter);

插入&删除:

  1. insert(key_value) : 将key_value插入到set中 ,返回值是pair<set<int>::iterator, bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。
  2. inset(first,second) : 将定位器first到second之间的元素插入到set中,返回值是void.
  3. erase(iterator) : 删除定位器iterator指向的值
  4. erase(first,second) : 删除定位器first和second之间的值
  5. erase(key_value) : 删除键值key_value的值

前后:

  1. upper_bound(key_value) : 大于key_value的定位器
  2. lower_bound(key_value) : 大于等于key_value的定位器
  3. --upper_bound(key_value) : 小于等于key_value的定位器
  4. --lower_bound(key_value) : 小于key_value的定位器

6.2.2 vector

在vector中,如果一个函数中需要两个迭代器,一般后一个都不包含.

  1. 创建vector对象 : vector<int> vec;
  2. 尾部插入数字 : vec.push_back(a);
  3. 使用下标访问元素 : cout<<vec[i]<<endl;记住下标是从0开始的。
  4. 使用迭代器访问元素 : for(iter=vec.begin();iter!=vec.end();it++) printf("%d ",*iter);
  5. 插入元素 : vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a
  6. 删除元素 : vec.erase(vec.begin()+i);删除第i+1个元素
  7. 删除区间 : vec.erase(vec.begin()+i,vec.begin()+j);删除区间[i,j-1]
  8. 大小 : vec.size();
  9. 清空 : vec.clear();
  10. 使用reverse将元素翻转 : reverse(vec.begin(),vec.end());
  11. 使用sort排序 : sort(vec.begin(),vec.end());