专栏文章

题解：B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全

EEnjoySilence
B4158题解参与者 6已保存评论 8

文章操作

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

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

思路

这题是一道简单的 DFS 搜索题，在读入字符串 strstr 后，遍历 strstr，如果 str[i]str[i] 为 *，则计数器 pp 加一，并且记录下来当前的位置 ii（为后面的 DFS 搜索位置做铺垫）。
这里可以进行一个特判：若 p=0p=0（即没有污点），则直接判断 strstr 表示的数是否是质数，如果是的话直接输出 strstr，否则输出 -1（无解）。
否则就调用函数 dfs(int t,string s)，其中 tt 表示当前在搜索的是第 tt 个数位，ss 表示当前的已经修改 t−1t-1 个被污染数位后的字符串。如果 t>pt>p（即已经搜索完所有的污染数位），就判断 ss 是否是质数，若是的话就直接输出 ss，并且判断最小答案的变量 flagflag 记为 true，后面的所有 DFS 函数直接return；其他情况下，若当前枚举的数位 c(pos[t])c(pos[t]) 是第 0 位（即开头），就从 1 到 9 枚举数字（防止前导 0），然后带入 ss 进行下一次 dfs 递归，否则就从 0 到 9 枚举数字。
最后，不要忘了在每个数据组开始时清空所有变量。

代码（我知道你们在等的是这个）

CPP
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const int N = 10;

string str;
int p, pos[N];
bool flag = 0;

bool prime(string s) {
    int a = atoi(s.c_str());
    if (a <= 1)
        return 0;
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0)
            return 0;
    }
    return 1;
}

void dfs(int t, string s) {
    if (flag)
        return;
    if (t > p) {
        if (prime(s)) {
            cout << s << endl;
            flag = 1;
        }
        return;
    }
    int c = pos[t];
    if (c == 0) {
        for (int i = 1; i <= 9; i++) {
            s[c] = i + '0';
            dfs(t + 1, s);
            s[c] = '*';
        }
    } else {
        for (int i = 0; i <= 9; i++) {
            s[c] = i + '0';
            dfs(t + 1, s);
            s[c] = '*';
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> str;
        p = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '*') {
                pos[++p] = i;
            }
        }
        flag = 0;
        if (p == 0) {
            if (prime(str))
                cout << str << endl;
            else {
                cout << -1 << endl;
            }
        } else {
            dfs(1, str);
            if (!flag)
                cout << -1 << endl;
        }
    }
    return 0;
}

Upd 25.3.4 AC记录

AC。
管理大大求过，我已经交了5次了QWQ

评论

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

正在加载评论...