By

蓝桥算法回顾

一些函数与算法

1.字符串相关函数

截取字符串 str=s.substr(开始位置,截取长度) ；

插入字符串 str=s.insert(开始位置,插入字符串) ;

查找字符串 tmp=s.find(查找串,开始查找位置) ；

删除字符串 s.erase(开始位置,删除长度) ;

输入一行 getline(cin,字符串名) ;

2.STL回顾

容器

vector定义：vector<int> v(n,x)；长度为n，初始化为x。

迭代器定义：vector<int>::iterator it;

栈定义：stack<int> st;

队列定义：queue<int> q;

大根堆定义：priority_queue<int> q;

小根堆定义：priority_queue<int,vector<int>,greater<int> > q;

map定义：map<int,int> mp;

map使用二分函数，查找比较的是第一个属性，返回迭代器。

pair定义：pair<int,int> p;

pair赋值：x=make_pair(1,2)或x={1,2}

pair使用：a=x.first,b=x.second;

无序map定义：unordered_map<int,int> m;

map查找为\(O(log n)\)，无序map查找为\(O(1)\)。

算法

翻转：reverse(a,a+5)

第k个有序：nth_element(a,a+k,a+5)

下一个排列：next_permutation(a,a+5)

上一个排列：prev_permutation(a,a+5)

3.二分

bool check(int x){
	
}
int er(int l,int r){
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid,l=mid+1;
		}else r=mid;
	}
    return ans;
}

4.并查集

并查集数组需要初始化，fa[i]=i。

int find(int x){//查询是否是同一个集合
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void join(int x1,int x2){
	int f1=find(x1),f2=find(x2);
	if(fa[x1]!=fa[x2]) fa[x1]=x2;
}

5.DFS

void dfs(int k){//k代表递归层数，或者填第几个空
	if(所有空已经填完){
		判断最优解/记录答案;
		return;
	}
	for(枚举这个空能填的选项){
		if(这个选项合法){
			保存现场;
			dfs(k+1);
			恢复现场;
		}
	}	
}

6.ST表

ST表（Sparse Table，稀疏表）是用于解决 可重复性贡献问题 （区间最值、区间gcd……重复计算不会对贡献有变化）的数据结构，倍增+动态规划的思想。

状态：\(F[i][j]\) 代表以 \(i\) 为起点，长度为 \(2^j\) 的区间最大值，即区间 \([i,i+2^j-1]\) 的最大值

初始化：\(F[i][0]=a[i]\)

转移方程：

\[F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1])\]

区间\([L,R]\) 的最大值：

\[len =R-L+1;log Len= \lfloor log(len) \rfloor\] \[ans=max(F[L][log Len],F[R-(1<<log Len)+1][log Len])\]

代码：

//初始化
for(int i=1;i<=n;i++) cin>>f[i][0];
//状态转移
for(int j=1;j<=log2(n);j++)
    for(int i=1;i<=n-(1<<j)+1;i++)
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
//查询
int l,r;cin>>l>>r;
int len=log2(r-l+1);
int ans=min(f[l][len],f[r-(1<<len)+1][len]);
cout<<ans<<" ";

7.倍增LCA

我采用常用的邻接表存储，链式前向星网上有很多。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
const int dep=20;
int fa[N][dep];
vector<int> e[N];//邻接表
int depth[N];
int n,m,s;
int maxdepth=0;
//dfs遍历无向图，确定各个结点的深度depth,树的深度maxdepth，父亲结点fa[i][0]
void dfs(int x,int y){
	for(int i=0;i<e[x].size();i++){
		if(e[x][i]==y) continue;
		depth[e[x][i]]=depth[x]+1;//记录深度
		maxdepth=max(maxdepth,depth[e[x][i]]);//更新树深
		fa[e[x][i]][0]=x;//2^0倍父亲结点
		dfs(e[x][i],x);
	}
}
//初始化倍增结点fa[x][i]
void init(int x){
	for(int i=0;i<dep;i++) fa[x][i]=0;
	//为0表示不存在2^k倍父亲结点
	for(int j=1;j<=log2(maxdepth);j++){
		for(int i=1;i<=n;i++){
			if(i==x) continue;
//i的2^j倍父节点是不是i的2^j-1倍父节点的2^j-1倍的父节点
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
}
//查找结点x,y的最近公共祖先
int find(int x,int y){
	if(depth[x]>depth[y]) swap(x,y);
	while(depth[y]>depth[x]){//找到同一深度的点
		int len=log2(depth[y]-depth[x]);
		y=fa[y][len];
	}
	if(x==y) return x;//点相同，为最近祖先
	for(int i=log2(depth[y]);i>=0;i--){
		if(fa[x][i]!=fa[y][i]){//不断寻找最近公共祖先
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	int u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);//构造无向图
		e[v].push_back(u);
	}
	depth[s]=0;//初始根结点深度为0
	dfs(s,-1);
	init(s);//初始化
	while(m--){
		cin>>u>>v;
		cout<<find(u,v)<<"\n";
	}
	return 0;
}