题目链接
https://pintia.cn/problem-sets/994805260223102976/problems/1071785997033074688。
题面
本题要求你编程解决一个更通用的问题:从任一给定的长度为 L 的数字中,找出最早出现的 K 位连续数字所组成的素数。
输入格式
输入在第一行给出 2 个正整数,分别是 L(不超过 1000 的正整数,为数字长度)和 K(小于 10 的正整数)。接下来一行给出一个长度为 L 的正整数 N。
输出格式
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在,则输出 404
。注意,原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数,0023 算是解;但第一位 2 不能被当成 0002 输出,因为在原始数字中不存在这个 2 的前导零。
输入样例1
20 5
23654987725541023819
输出样例1
49877
输入样例2
10 3
2468024680
输出样例2
404
题目分析
任何题目的解法都有很多种,选择一个自己最熟练的方式很重要。如何选择呢?重点在于数据规模的大小。常言到暴力出奇迹。所以任何题目的核心都是数据范围。要知道算法比赛中的题解,不是通解,而是针对本题的特解。
本题考点:字符串处理和质数判定。
本题可以看到几个核心数据:
- L 不超过 1000 位的正整数。什么意思?就是说 L 是一个非常非常大的数,大到已经超过了long long的表示范围。所以不能选择用long long来表示 L,那么只有用字符数组来表示。
- K 小于 10 位的正整数。那么 K 可以用 int 表示。
通过分析,我们发现本题的数据量不大,因此最简单的办法就是枚举。也就是遍历整个数据,从开始出发,每次取出 K 长度的子串,判断这个字串的数据是否是质数。如果是,答案找到。如果不是,继续,直到数据遍历完成,那么输出 404 。
本题有一个小坑,很不幸,我踩中了,怪我语文不好。
例如在 200236 中找 4 位素数,0023 算是解。
说明输出要采用字符串形式。因为数字是没有前面两个零的。
样例代码
题解代码
#include <cstdio>
#include <cstring>
bool isPrime(int n) {
if (n<=1) {
//特判1不是质数
return false;
}
for (int i=2; i*i<=n; i++) {
if (0==n%i) {
return false;
}
}
return true;
}
int main() {
int l, k;
char data[1002];
char ans[10];
scanf("%d %d %s", &l, &k, data);
int num;//判断这个数是否是质数
int i, j;
for (i=0; i+k<=strlen(data); i++) {
num = 0;
for (j=0; j<k; j++) {
ans[j] = data[j+i];
num = num*10 + (ans[j]-'0');
}
ans[j] = '\0';
//测试数据
if (isPrime(num)) {
printf("%s\n", ans);
return 0;
}
}
//运行到这里,说明没有找到
printf("404\n");
return 0;
}
测试数据生成代码
惭愧,这题的测试数据生成代码没有写。找个时间补一下。
TBD
Windows下对拍参考
@echo off
:loop
gen.exe %random% > data.in
std.exe < data.in >std.out
pta1094.exe < data.in > my.out
fc my.out std.out
if not errorlevel 1 goto loop
pause
goto loop
广告
有兴趣可以关注我在GitHub上的题解。
GitHub的项目地址
https://github.com/justidle2012/PATSolution/
本题链接
https://github.com/justidle2012/PATSolution/blob/master/Basic%20Level/1093/pta1094.cpp