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

2789617221guo · 2025-02-25 20:10:12 · 题解

思路

这题是一道简单的 DFS 搜索题，在读入字符串 str 后，遍历 str，如果 str[i] 为 *，则计数器 p 加一，并且记录下来当前的位置 i（为后面的 DFS 搜索位置做铺垫）。

这里可以进行一个特判：若 p=0（即没有污点），则直接判断 str 表示的数是否是质数，如果是的话直接输出 str，否则输出 -1（无解）。

否则就调用函数 dfs(int t,string s)，其中 t 表示当前在搜索的是第 t 个数位，s 表示当前的已经修改 t-1 个被污染数位后的字符串。如果 t>p（即已经搜索完所有的污染数位），就判断 s 是否是质数，若是的话就直接输出 s，并且判断最小答案的变量 flag 记为 true，后面的所有 DFS 函数直接return；其他情况下，若当前枚举的数位 c(pos[t]) 是第 0 位（即开头），就从 1 到 9 枚举数字（防止前导 0），然后带入 s 进行下一次 dfs 递归，否则就从 0 到 9 枚举数字。

最后，不要忘了在每个数据组开始时清空所有变量。

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

#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