济南CSPS储备营DAY-2

快速幂

为了计算2^k可以用快速幂在0(log n)完成

代码呈现：

CPP

int ksm(int a,int b,int p)
{
	int ret=1;
	for(;b;b>>=1,a=(long long)a*a%p);
	{
		if(b&1)ret=(long long)ret*a%p;
	}
	return ret;
}//for循环

CPP

int ksm2(int a,int b,int p)
{
	if(b==0)return 1%p;
	if(b==1)return a%p;
	long long men=ksm2(a,b>>1,p);
	if(b&1)return men*men%p*a%p;
	return men*men%p;
}//递归

矩阵快速幂

两个矩阵为nm和mp，通过乘法结合律计算式子得结果
倍增

可替换为二分but更优秀
ST表

维护一个数据结构，支持查询任意区间的最大值。在每一个位置i维护区间[i,i+2^k)的最大值。
单调队列

可以看作两个栈模拟的队列如题P1886(板子题)

代码如下：

CPP

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
inline 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 - 48;
		ch = getchar();
	}
	return x * f;
}

int n, k;
int a[N];

int q[N], head, tail;

int mx[N], mn[N];

signed main() {
	n = read(), k = read();
	for(int i = 1; i <= n; ++ i)
		a[i] = read();
	head = 1, tail = 0;
	for(int i = 1; i <= n; ++ i) {
		while(head <= tail && a[q[tail]] <= a[i]) --tail;
		q[++ tail] = i;
		while(head <= tail && q[head] <= i - k) ++ head;
		if(i >= k) mx[i] = a[q[head]];
	}
	head = 1, tail = 0;
	for(int i = 1; i <= n; ++ i) {
		while(head <= tail && a[q[tail]] >= a[i]) --tail;
		q[++ tail] = i;
		while(head <= tail && q[head] <= i - k) ++ head;
		if(i >= k) mn[i] = a[q[head]];
	}
	for (int i = k; i <= n; ++ i)
		cout << mn[i] << " ";
	puts("");
	for (int i = k; i <= n; ++ i)
		cout << mx[i] << " ";
	puts("");
	return 0;
}

单调栈 如同站队，从左侧插入新人，将新人看不到的人（即被挡住的人）踢掉，得到一个单调递增的栈
堆

大根堆 or 小根堆 O(long n) ——优先队列(priority_queue)

对顶堆(~~bushi 有点恶心~~)

合并堆

并查集

少有的码量少但好用的算法，有名字可知作用为合并两个集合，可看作树，建立公共祖先，由此便可称之为找爸爸算法，其精华在于getfather函数中的递归常用为路径压缩和按秩合并

经典例题：P1892团伙

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dr[1145],fa[1145];
bool flag[1010];
int getf(int x){
	if(fa[x]==x) return x;
	return fa[x]=getf(fa[x]);
}
int main(){
	cin>>n>>m;
	char c;
	int x,y;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		cin>>c>>x>>y;
		if(c=='F')
			fa[getf(x)]=getf(y);
		else {
			if(!dr[x]) dr[x]=y;
			else fa[getf(y)]=getf(dr[x]);
			if(!dr[y]) dr[y]=x;
			else fa[getf(x)]=getf(dr[y]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		flag[getf(i)]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(flag[i])
		{	
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

P1551 亲戚代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,p,a,b,f[5555];
int getf(int x)
{
	if(f[x]!=x)
	{
		return getf(f[x]);
	}
	else return x;
}
void merge(int a,int b)
{
	int fa=getf(a);
	int fb=getf(b);
	if(fa!=fb)
	{
		f[fb]=fa;
	}
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}	
	for(int i=1;i<=m;i++)
	{
		
		cin>>a>>b;
		merge(a,b);
	}
	while(p--)
	{
		cin>>a>>b;
		if(getf(a)==getf(b))
		{
			cout<<"Yes"<<endl;
		}
		else
		{
			cout<<"No"<<endl;
		}
	}
	return 0;
 }

线段树
分治结构发挥神力，下放sum和懒标记

本章结

济南CSPS储备营DAY-2

文章操作

相关推荐

评论

济南CSPS储备营DAY-2