自动搬运

查看原文

来自洛谷，原作者为

	2789617221guo 身在井隅，心向璀璨。

搬运于2025-08-24 21:17:27，当前版本为作者最后更新于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