第十五届蓝桥杯C++B组第二场真题-质数变革

315 阅读 0 评论 0 点赞

##思路
由于给出的数据大小以及题意可知，这道题考察的应该是线性筛和二分查找，本人由于太弱了，没想到我居然之前接触过欧拉筛，应该也叫做线性筛吧，时间紧迫来不及多思考，比赛中用的朴素做法，估计能拿个1分2分这样，以下是我补题后的写法
####参考代码
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+3;                       //开到第一个大于1000000的质数 
const int M = 2e5+10;
int n,q;
vector<int> cha[M];                        //查找值
int a[M];                                  //初始数组a
int pri[N],pri_num=0,lu[N],qp=0;           //质数，质数个数,记录因子数组 
bool ji[N],zhi[M];
inline void dabiao(){                      //欧拉筛
	for(int i=2;i<=N;i++){
		if(!ji[i]) lu[++qp]=i;
		for(int j=1;lu[j]*i<=N;j++){
			ji[lu[j]*i]=true;
			if(i%lu[j]==0) break;
		}
	}
	for(int i=2;i<=N;i++){
		if(!ji[i]) pri[++pri_num]=i;
	}
	return ;
}
inline int find_da(int x){                   //在质数表里寻找第一个大等于a[i]的数
	int l=1,r=pri_num;
	while(l<r){
		int mid=l+r>>1;
		if(pri[mid]>=x) r=mid;
		else l=mid+1;
	}
	return r;
}
inline int find_xiao(int x){                 //在质数表里寻找第一个小等于a[i]的数
	int l=1,r=pri_num;
	while(l<r){
		int mid=l+r+1>>1;
		if(pri[mid]<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
inline int he(int i){                      //找要替换成的数
	int sum=0;
	for(auto e:cha[i]){
		sum+=e;
	}
	return sum;
}
inline void tihuan(){                      //替换
	for(int i=1;i<=n;i++){
		if(cha[i].size()>0){
			if(!zhi[i]){                   //如果不是质数要把其按照第一次的变化变为质数，如果第一次是往大取，则先变小一位质数，反之则取大一位的质数
				int first=cha[i][0];
				if(first>0){
					int pri_ai=find_xiao(a[i]);
					a[i]=pri[pri_ai];
				}
				else{
					int pri_ai=find_da(a[i]);
					a[i]=pri[pri_ai];
				}
			}
			int sum=he(i);
			if(sum>0){
				int pri_ai=find_xiao(a[i]);
				if(sum+pri_ai<pri_num){
					a[i]=pri[pri_ai+sum];
				}
				else a[i]=1;
			}
			else{
				int pri_ai=find_da(a[i]);
				if(sum+pri_ai>0){
					a[i]=pri[pri_ai+sum];
				}
				else a[i]=0;
			}
		}
	}
	return ;
}
int main(){
	scanf("%d %d",&n,&q);
	dabiao();                   //先打一个质数表
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(pri[find_da(a[i])]==a[i]){     //记录每一个数是不是质数
			zhi[i]=true;
		}
	}
	while(q--){
		int op,k,x;
		scanf("%d %d %d",&op,&k,&x);
		for(int i=k;i<=n;i+=k){
			if(op==1){
				cha[i].push_back(x);        //记录每一次的搜索
			}
			else{
				cha[i].push_back(0-x);
			}
		}
	}
	tihuan();                   //替换   
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}
```

0.0分

2 人评分

本文分类：文章列表
浏览次数：315 次浏览
发布日期：2024-04-23 00:33:47
本文链接：https://blog.dotcpp.com/a/104645

上一篇 > 字符串字符串
下一篇 > 第十五届蓝桥杯C++B组第二场真题-最强小队

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

第十五届蓝桥杯C++B组第二场真题-质数变革

评论列表共有 0 条评论

发表评论取消回复

第十五届蓝桥杯C++B组第二场真题-质数变革

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复