备战蓝桥杯算法整合

这里写目录标题

六倍法判断素数

bool is_sprime(int x){
	if(x==1)return false;//1不是素数 
	if(x==2||x==3||x==5){//2,3,5是素数 
		return true;
	}
	if(x%2==0||x%3==0){//2和3的倍数一定不是素数 
		return false;
	}
	for(int i=5;i<=sqrt(x);i+=6){
		if(x%i==0||x%(i+2)==0){
			return false;
		}
	}
	return true;
}

欧拉筛

bool check[10000];//标记合数
vector<int> prime;
void isprime(int n){
	check[0]=true;
	check[1]=true;
	for(int i=2;i<=n;i++){
		if(!check[i])prime.push_back(i);
		for(int j=0;j<prime.size()&&i*prime[j]<=n;j++){
			check[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}

01背包

for(int i=1;i<=n;i++){//n是物品总数 
		for(int j=m;j>=w[i];j--){//m是背包大小 
			dp[j]=max(dp[j],v[i]+dp[j-w[i]]);
		}
	}

完全背包

	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=m;j++){
			dp[j]=max(dp[j],v[i]+dp[j-w[i]]);
		}
	}

多重度背包

struct node{//包结构体 
	int v,w;//价值重量 
	node(int vv,int ww){
		v=vv;
		w=ww;
	}
};
vector<node> goods;

for(int i=1;i<=n;i++){//拆包 
	int tv,tw,s;
	cin>>tv>>tw>>s;
	for(int k=1;k<=s;k*=2){//二进制优化 
		s-=k;
		goods.push_back(node(tv*k,tw*k));//装包 
	}
	if(s>0)goods.push_back(node(tv*s,tw*s));//剩下的也要装入包中 
}
	//01背包
for(int i=0;i<goods.size();i++){
	for(int j=m;j>=goods[i].w;j--){
		dp[j]=max(dp[j],goods[i].v+dp[j-goods[i].w]);
	}
} 

Floyd-Warshall（多源最短路）

	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
			}
		}
	}

Dijkstra(单源最短路)

无法处理带有负权边和负权回路的图

book[cnt]=true;//起始点标记为访问过
for(int i=1;i<=n-1;i++){//需要松弛n-1次
		int mint=INF;
		for(int j=1;j<=n;j++){//找出和起始点最近的点 
			if(!book[j]&&dis[j]<mint){
				u=j;//记录最近点下标
				mint=dis[j];//记录最近点距离
			}
		}
		book[u]=true;//标记为访问过
		for(int v=1;v<=n;v++){//查询和最近点有连接的点 
			if(e[u][v]<INF){//保证u可以到v 
				dis[v]=min(dis[v],dis[u]+e[u][v]);//松弛 
			}
		}
	}

最大公约数

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

最小公倍数

int icm(int a,int b){
	return a*b/gcd(a,b);
}

分解质因数

void zhiyinshu(int n){
	is_prime(n);//利用欧拉筛建素数表 
	int i=0;
	while(n!=1){//n==1找完了所有质因数
		if(!n%prime[i]){
			printf("%d\n",prime[i]);//找到了一个质因数
			n/=prime[i]; 
			continue;//质因数可以相同 
		} 
		i++;//遍历下一个素数 
		
	}
}

全排列（递归）

void permutaion(int k){//调用permutation(0) 
	if(k==n){//完成一次排列 
		if(check()){//判断是否满足条件 
			//操作 
		}
		return;
	}
	for(int i=k;i<n;i++){
		swap(a[i],a[k]);
		permutaion(k+1);
		swap(a[i],a[k]);
	}
}

区间全排列

void permutation(int p,int q){//对区间[p,q]进行全排列 
	if(p==q){//出口 
		if(check()){//用来检查题目的条件 
		     //执行操作 
		}
		return; 
	}
	for(int i=p;i<q;i++){
		swap(a[i],a[p]); 
		permutation(p+1,q);
		swap(a[i],a[p]);
	}
}

并查集

//初始化
for(int i=1;i<=n;i++){
		parent[i]=i;//所有的点祖宗是自己
		rank[i]=0;
}


//找根节点（找祖宗） 
int find(int x){
	if(x==parent[x])return x;//自己的爸爸是自己，自己就是祖宗 
	return parent[x]=find(parent[x]);//路径压缩，将经过的点的祖宗全部更新 
}


//按秩合并集合 
void unite(int x,int y){
	int x_root=find(x);
	int y_root=find(y);
	if(x_root==y_root)return;//在同一集合中
	//认层数多的树的根节点做祖宗 
	if(rank[x_root]>rank[y_root]){
		parent[y_root]=x_root;
	}else{
		parent[x_root]=y_root;
		if(rank[x_root]==rank[y_root]){
			rank[y_root]++;//当两棵树一样高时，认y_root树做祖宗会是整体层数加一 
		}
	}
}