专栏文章

题解：P12157 [蓝桥杯 2025 省 Java B] 魔法科考试

cchina_history
P12157题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipkbqc3
此快照首次捕获于
2025/12/03 13:24
3 个月前
此快照最后确认于
2025/12/03 13:24
3 个月前
查看原文

前置芝士 线性筛 本题精髓

CPP
//线性筛(前置芝士P3383) 
void prime() {
	for (int i = 2; i <= n + m; i++) {
		if (!isp[i]) {
			p[++cnt] = i;
		}
		for (int j = 1; j <= cnt && i * p[j] <= n + m; j++) {
			isp[i * p[j]] = 1;
			if (i % p[j] == 0) {
				break;
			}
		}
	}
}

题意

给你两个数组 aa 和 bb 问你利用这两个数组中的数字，可以组合出多少符合要求的不重复的组合，要求为将 aa 数组中的任意一个数与 bb 数组中的任意一个数相加，得到 ss 这个数，我们的 ss 需要是质数，且 ss 小于等于 nn 与 mm 的和。

思路

我们可以先筛小于 nn 与 mm 的和的质数，运用 ispisp 数组来看某一个数是否是质数，在输入之后，我们可以使用两重循环，因为题目给了三秒的时间，所以暴力就可以，我们再看我们的 aia_i 与 bjb_j 的和 tt 是否符合要求，而且没有重复的，我们就可以将答案加一，并且将这个数的 visvis 标为访问过，最后输出答案。 本题主要考察的是会不会筛素数与会不会去重，没有别的，只是基本语法，并无难点。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
int n, m; //上半句与下半句的数量
int a[50005];//上半句 
int b[50005];//下半句 
int p[100001];//存质数 
int cnt = 0;
int isp[100001];//质数判断 
int vis[100001];//组合判重 
int sum=0;//总数 
void prime() {
	for (int i = 2; i <= n + m; i++) { //只找n+m以下的质数(线性筛)(埃式筛也可以)
		if (!isp[i]) {
			p[++cnt] = i;
		}
		for (int j = 1; j <= cnt && i * p[j] <= n + m; j++) {//线性筛(前置芝士P3383) 
			isp[i * p[j]] = 1;
			if (i % p[j] == 0) {
				break;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	prime();//筛素数 
	for (int i = 1; i <= n; i++) {//输入前半句 
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {//输入下半句 
		cin >> b[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//三秒钟，暴力即可 
			int t=a[i]+b[j];//总和 
			if(isp[t]==0&&t<=n+m&&vis[t]==0){//判断是否符合条件 
				sum++;//增加 
				vis[t]=1; //标记 
			} 
		}
	}
	cout << sum;
	return 0;//好习惯 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...