模板复习

就最后这几天了,越来越方,但是却又越来越颓了起来,只能逼着自己写一些东西了

1.归并排序

虽然是在快速排序的模板中写的,但是也懒得去找其他的归并排序的板子题写了

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)

主体思想就是 分而治之

先将数组中每个元素分开,拆分子序列,接着两两比较,由两个有序的子序列互相比较合并为一个大的有序子序列,最后就可以得到有序的序列了

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
void _merge(int arr[],int left,int mid,int right)
{
int p=1,que[N]={0};
int pl=left,pr=mid;
int ql=mid+1,qr=right;
while(pl<=pr||ql<=qr)
{
if((ql>qr)||pl<=pr&&arr[pl]<=arr[ql])
{
que[p++]=arr[pl++];
}
else que[p++]=arr[ql++];
}
while(left<=right)
{
arr[right--]=que[--p];
}
}
void mergesort(int arr[],int left,int right)
{
if(left>=right)return ;
int mid=(left+right)>>1;
mergesort(arr,left,mid);
mergesort(arr,mid+1,right);
_merge(arr,left,mid,right);
}

2.并查集->kruskal

最基础的东西,也是用途最广的之一,可以处理一些图论和搜索的问题,例如kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int findf(int x)
{
return fa[x]==x?fa[x]:fa[x]=findf(fa[x]);
}
struct node
{
int x,y,z;
bool operator < (const node &a)const
{
return z<a.z;
}
}q[N];
......
sort(q+1,q+1+m);
for(int i=1;i<=m;i++)
{
int fx=findf(q[i].x),fy=findf(q[i].y);
if(fx==fy)continue;
if(fx<fy)swap(fx,fy);
fa[fx]=fy;
ans+=q[i].z;
cnt++;
if(cnt==n-1)break;
}

3.快速幂和龟速乘

也是相当基础的东西,前者在一些数论和找规律中可以用到,后者可以解决快速幂乘法中爆long long的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll mul(ll x,ll y)
{
ll sum=0;
while(y)
{
if(y%2){sum=(sum+x)%p;}
x=(x+x)%p;
y/=2;
}
return sum;
}
ll ksm(ll x,ll y)
{
ll sum=1;
while(y)
{
if(y%2){sum=mul(sum,x);}
x=mul(x,x);
y/=2;
}
return sum;
}

4.线性筛素数+欧拉函数

传统的线性筛(最基础的)是用已知的素数作为质因子筛掉含有此质因子的数
但是问题是每个合数会被多个质因子筛掉,这个时候我们可以让每个合数都被他最小的质因数(欧拉筛)筛掉
然后求phi(小于n的正整数中又几个是与n互质的)时也可以用到欧拉筛虽说不是很懂就是了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void get()
{
for(int i=2;i<=n;i++)
{
if(!flag[i])
{
prim[++num]=i;
phi[i]=i-1;
}
for(int j=1;j<=num&&i*prim[j]<=n;j++)
{
flag[i*prim[j]]=true;
phi[i*prim[j]]=phi[i]*(prim[j]-1);
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
}
}
}

5.堆

手写堆我是不会的…STL多好啊

1
2
priority_queue <int, vector <int> ,greater <int> >//小根堆
priority_queue <int, vector <int> ,less <int> >//大根堆

6.字符串哈希

luogu上面这个模板貌似…可以用map水过去
map<string ,int> mp;......if(!mp[a[i]])cnt++,mp[a[i]]=1;
所以当hash容易被冲突时,考场上我可以尝试打map
当然hash本身也是很好的

1
2
3
4
5
6
7
8
9
10
11
const int mod=1e9+7;
int n,base=233,prime=2048,h[N];
int gethash(string a)
{
int l=a.size(),x=0;
for(int i=0;i<l;i++)
{
x=(x*base+a[i])%mod+prime;
}
return x;
}

7.最短路

spfa写的滚瓜烂熟了,这里写一下dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dijkstra()
{
priority_queue< pair<int,int> ,vector< pair<int,int> > ,greater <pair<int,int> > >p;
for(int i=1;i<=n;i++)dist[i]=inf,inq[i]=0;
dist[s]=0;
p.push(make_pair(dist[s],s));
while(!p.empty())
{
int u=p.top().second;p.pop();
if(inq[u])continue;
inq[u]=1;
for(int i=head[u];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
if(dist[v]>dist[u]+q[i].w)
{
dist[v]=dist[u]+q[i].w;
p.push(make_pair(dist[v],v));
}
}
}
}

8.树状数组+部分差分

luogu上第一个模板就是最裸的树状数组了,首先要明确的是这里的树状数组维护的不是单纯一个数的值,而是通过一个数的lowbit连接起来的一连串的数的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int lowbit(int x){return x&(-x);}
void update(int x,int d)
{
while(x<=n)
{
a[x]+=d;
x+=x&(-x);
}
}
int getsum(int x)
{
int sum=0;
while(x>0)
{
sum+=a[x];
x-=x&(-x);
}
return sum;
}
单点修改update(x,d)
区间求和getsum(y)-getsum(x-1)//前缀和思想

第二个板子,原数组我们直接读入,对于区间修改,我们树状数组维护的是差分数组,然后单点查询就是一个数的原值加上到他为止的差分数组前缀和了

1
2
区间修改 add(x,z),add(y+1,-z);
单点查询 a[x]+getsum(x);

9.lca

其实可以不用复习的…自己写的最多的两个算法,一个是最短路,另外一个就是树剖求lca了…虽然lca的求法还有倍增等高级算法,但是显然我考场上是写出来的…

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
void dfs1(int x,int father,int dep)
{
siz[x]=1;
fa[x]=father;
deep[x]=dep;
for(int i=head[x];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
if(v!=fa[x])
{
dfs1(v,x,dep+1);
siz[x]+=siz[v];
if(siz[son[x]]<siz[v])
{
son[x]=v;
}
}
}
}
void dfs2(int x,int note)
{
++id;
pos[x]=id;
belong[x]=note;
if(son[x])
{
dfs2(son[x],note);
}
for(int i=head[x];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
if(v!=fa[x]&&v!=son[x])
{
dfs2(v,v);
}
}
}
int lca(int x,int y)
{
while(belong[x]!=belong[y])
{
if(deep[belong[x]]<deep[belong[y]])swap(x,y);
x=fa[belong[x]];
}
if(pos[x]>pos[y])swap(x,y);
return x;
}

10.线段树

虽然会考线段树,但是肯定不是裸的,写这个板子单纯是练自己打线段树的速度,事实证明我的速度只能达到10~15min,不像机房巨神的5min线段树
线段树本身作用其实很多的,当然,跟平衡树等树结合起来的时候才是作用最大的…然而并没有写过树套数 更难的区间处理都用分块写过去了…

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
struct node
{
int left,right,val,sum;
}a[N];
int data[N],n,m;
void pushup(int p)
{
a[p].sum=a[p<<1].sum+a[p<<1|1].sum;
}
void pushdown(int p)
{
a[p<<1].val+=a[p].val;
a[p<<1|1].val+=a[p].val;
a[p<<1].sum+=(a[p<<1].right-a[p<<1].left+1)*a[p].val;
a[p<<1|1].sum+=(a[p<<1|1].right-a[p<<1|1].left+1)*a[p].val;
a[p].val=0;
}
void build(int p,int l,int r)
{
a[p].left=l;
a[p].right=r;
if(l==r)
{
a[p].sum=data[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,int d)
{
if(a[p].left==l&&a[p].right==r)
{
a[p].val+=d;
a[p].sum+=(r-l+1)*d;
return ;
}
if(a[p].val)pushdown(p);
int mid=(a[p].left+a[p].right)>>1;
if(r<=mid)update(p<<1,l,r,d);
else if(l>mid)update(p<<1|1,l,r,d);
else update(p<<1,l,mid,d),update(p<<1|1,mid+1,r,d);
pushup(p);
}
int query(int p,int l,int r)
{
if(a[p].left==l&&a[p].right==r)
{
return a[p].sum;
}
if(a[p].val)pushdown(p);
int mid=(a[p].left+a[p].right)>>1;
if(r<=mid)return query(p<<1,l,r);
else if(l>mid)return query(p<<1|1,l,r);
else return query(p<<1,l,mid)+query(p<<1|1,mid+1,r);
}

11.二分图最大匹配

不知道会不会考…只是把板子打了一下毫无卵用
大致思想就是先看能不能直接配对,如果不能,找到先前已经配好的对,看能否让他找到另外一个配对的对象
大概吧

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
inline bool findf(int u)
{
for(int i=head[u];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
if(!vis[v])
{
vis[v]=1;
if(!match[v]||findf(match[v]))
{
match[v]=u;
return 1;
}
}
}
return 0;
}
......
for(int i=1;i<=e;i++)
{
int u=read(),v=read();
if(v>m||u>n)continue;
add(u,v);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(findf(i))ans++;
}

12.高斯消元法

主要用到了平时解多元一次方程组的方法,然而平时是瞎解,oi这边就要把整个解方程组的顺序搞成有序的/可以用计算机解决的程序
大致思路就是每一次用一个方程里面的x[i]消掉其余所有方程中的x[i],然后处理x[i+1]~x[n],每次取系数最大的处理

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
#include <bits/stdc++.h>
#define N 201
#define eps 1e-9
using namespace std;
typedef pair<int,int>p2;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
bool flag=0;
double a[N][N];
double x[N];
void gauss()
{
for(int i=1;i<=n;i++)
{
int p=i;
for(int j=i+1;j<=n;j++)
{
if(fabs(a[j][i])>fabs(a[p][i]))p=j;
}
if(fabs(a[p][i])<eps)
{
flag=1;
return ;
}
if(p!=i)swap(a[p],a[i]);
for(int j=1;j<=n;j++)
{
if(i!=j)
{
double b=a[j][i]/a[i][i];
for(int k=1;k<=n+1;k++)
{
a[j][k]-=a[i][k]*b;
}
}
}
}
}
main()
{
n=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n+1;j++)
{
scanf("%lf",&a[i][j]);
}
}
gauss();
if(flag){printf("No Solution\n");return 0;}
for(int i=1;i<=n;i++)
{
printf("%.2lf\n",x[i]=a[i][n+1]/a[i][i]);
}
return 0;
}

13.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
void tarjan(int x)
{
++id;
pos[x]=low[x]=id;
stc[++top]=x;
suc[x]=1;
for(int i=head[x];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
if(!pos[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(suc[v])
{
low[x]=min(low[x],low[v]);
}
}
if(pos[x]==low[x])
{
int y;
while(y=stc[top--])
{
belong[y]=x;
suc[y]=0;
if(y==x)break;
val[x]+=val[y];
}
}
}
......
for(int i=1;i<=n;i++)
{
if(!pos[i])tarjan(i);
}
for(int i=0;i<m;i++)
{
int fx=belong[q[i].fr],fy=belong[q[i].to];
if(fx==fy)continue;
add2(fx,fy);
}

14.推逆元

数论本身不清楚,总之很短,比费马小优秀的,而且费马小模数必须是质数,这个就没限制了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//线性
inv[1]=1;
for(int i=2;i<=n;i++)
{
inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;
}
//exgcd
int x,y,t;
void exgcd(int a1,int b1)
{
if(!b1)
{x=1;y=0;return;}
exgcd(b1,a1%b1);
t=x;x=y;
y=t-a1/b1*y;
return;
}
b的逆元exgcd(b,mod)求得的x

15.拓扑排序

入度为0的进队,将所连的边的in[to]–,如此往复,可以解决一些处理先后顺序的问题

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
void topo()
{
queue<int> p;//如果有一些字典序从小到大或是从大到小的要求,改为priority_queue
int cnt=0;
for(int i=1;i<=n;i++)
{
if(!in[i])p.push(i);
}
while(!p.empty())
{
int u=p.front();
ans[++ans[0]]=u;
p.pop();
for(int i=head[u];i!=-1;i=q[i].nxt)
{
int v=q[i].to;
in[v]--;
if(!in[v])
{
p.push(v);
}
}
}
if(ans[0]<n)
{
printf("Impossible!\n");
return ;
}
}