Criska

NOIP模板整合

• 分类: KMP, 同余方程, 快速幂, 对数, 单调队列, 最小生成树 • 标签: KMP, 单调队列, 同余方程, 对数, 快速幂, 最小生成树

1.KMP字符串匹配

求匹配字符的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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int N=2000000;
int al,bl,next[N];
char a[N],b[N];
int kmp()
{
	for(int i=0,j=0;i<=al;++i,++j)
	{
		while(j!=-1&&a[i]!=b[j]) j=next[j];
		if(j==bl-1&&(i-bl+2!=al))
		printf("%d\n",i-bl+2);//每次匹配时，输出它的匹配位置的起点，它可以有多次匹配
	}
}
void qiunext()
{
	next[0]=-1;
	for(int i=1;i<bl;++i)
		for(int j=next[i];j>=0;j=next[j])
		if(b[j]==b[i])
		{
			next[i+1]=j+1;
			break;
		}		
}
int main()
{
	scanf("%s%s",a,b);
	al=strlen(a);
	bl=strlen(b);
	qiunext();//先求出它的前缀数组next
	kmp();
	for(int i=1;i<=bl;++i)
		printf("%d ",next[i]);
	return 0;
}

2.快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
using namespace std;
inline int pow(int x,int y,int P)
{
    int sv=1;
    for(;y;y>>=1,x=x*x%P)
        if(y&1)
            sv=sv*x%P;
    return sv;
}
int main()
{
	int a,b,p;
	cin>>a>>b>>p;
	cout<<pow(a,b,p);//求a的b次方
	return 0;
}

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
#include<iostream>
#include<cstdio>
using namespace std;
int x,y,a,b,t;
int gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;y=0;
	}
	else
	{
		gcd(b,a%b,x,y); 
		t=x;
		x=y;
		y=t-a/b*y;
	}
}
int main()
{
	scanf("%d%d",&a,&b);
	gcd(a,b,x,y);
	// ax=1(mod p) 可以转化成 ax=yp+1 也就是 ax-yp=1     ax+(-y)p=1 
	x=x%b;
	while(x<0) x+=b;
	cout<<x;
	return 0;
}

4.对数（log）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,x;
int Log2(int a)
{
    int r;
    for (r=0;(1<<r)<=a;r++);
    return r-1;
}
int main()
{
	cin>>n;
	x=Log2(n);
	cout<<x;
	return 0;
}

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
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=2000001,M=21;
int a[N],q[N],head=1,tail=1,n,m;
void push(int x)
{
	while(a[x]<=a[q[tail]]&&head<=tail)
		tail--;
	q[++tail]=x;
}
void pop(int x)
{
	if(q[head]<x-m+1)
		head++;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	cout<<0<<endl;
	q[1]=1;	
	for(int i=2;i<=n;++i)
	{
		printf("%d\n",a[q[head]]);
		push(i);
		pop(i);
	}
	return 0;
}
`

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
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200010;
int tot,k,m,n,ans;
int father[N];
struct node{
	int x,y,z;
}e[N];
int comp(const node & a,const node & b)
{
	return a.z<b.z;
}
int fa(int x)
{
	if(father[x]!=x)
	father[x]=fa(father[x]);
	return father[x];
}
int un(int r1,int r2)
{
	father[r2]=r1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int a,b,z;
		scanf("%d%d%d",&a,&b,&z);
		e[i].x=a;e[i].y=b;e[i].z=z;
	}
	sort(e+1,e+m+1,comp);
	ans=0;k=0;
	for(int i=1;i<=n;++i)
	{
		father[i]=i;
	}
	for(int i=1;i<=m;++i)
	{
		int x=e[i].x,y=e[i].y,z=e[i].z;
		int r1=fa(x),r2=fa(y);
		if(r1!=r2)
		{
			un(r1,r2);
			ans+=z;
			k++;
		}
		if(k==n-1)
		break;
	}
	printf("%d",ans);
	return 0;
}

7.生成随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<windows.h>
using namespace std;
int main()
{
	//freopen("data.in","w",stdout);
	srand(GetTickCount());   
	for(int i=1;i<=100;++i)
	cout<<rand()%101<<endl;
	 
	  //确保数据随机，这只是很多写法里的一种
	/*
	 * 这里开始用一些奇奇怪怪的方法生成符合题目条件的数据
	 * 随机的东西用=rand()赋值
	 * 为了不超过数据范围，生成的数据要%一下 
	 * 最后别忘了输出数据 
	 */
	return 0;
}