题目# B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全## 题目描述Alice 在纸条上写了一个质数第二天再看时发现有些地方污损看不清了。- 在大于 $1$ 的自然数中除了 $1$ 和它本身以外不再有其他因数的自然数称为质数请你帮助 Alice 补全这个质数若有多解输出数值最小的若无解输出 $-1$。例如纸条上的数字为 $\tt{1*}$$\tt{*}$ 代表看不清的地方那么这个质数有可能为 $11, 13, 17, 19$其中最小的为 $11$。## 输入格式第一行 $1$ 个整数 $t$代表有 $t$ 组数据。接下来 $t$ 行每行 $1$ 个字符串 $s$ 代表 Alice 的数字仅包含数字或者 $\tt{*}$并且保证首位不是 $\tt{*}$ 或者 $0$。## 输出格式输出 $t$ 行每行 $1$ 个整数代表最小可能的质数或者 $-1$ 代表无解。## 输入输出样例 #1### 输入 #1101*3**7**83*722626**129*7889*777*225*### 输出 #1113077018317-1601129178893-12251## 输入输出样例 #2### 输入 #2104039***2***5*5409996125**7577***0**1***00*41811*96***0*78***1**6561*59### 输出 #24039019-140999612509757700000310000034181129600004780001016561259## 说明/提示### 样例 3-6参考附件中的样例。### 数据范围$|s|$ 代表 $s$ 串的长度对于所有数据$1 \leq t \leq 10, 1 \leq |s| \leq 7$$s$ 中仅包含数字或者 $\tt{*}$并且保证首位不是 $\tt{*}$ 或者 $0$。本题采用捆绑测试你必须通过子任务中的所有数据点以及其依赖的子任务才能获得子任务对应的分数。| 子任务编号 | 分值 | $\mid s\mid$ | 特殊性质 | 子任务依赖 || :----------: | :----------: | :----------: | :----------: | :----------: || $1$ | $35$ | $\leq 7$ | $s$ 中没有 $\tt{*}$ | || $2$ | $30$ | $\leq 4$ | | || $3$ | $24$ | $\leq 7$ | $s$ 中至多包含 $1$ 个 $\tt{*}$ | $1$ || $4$ | $11$ | $\leq 7$ | | $1,2,3$ |————————————————————————————————————————AC代码cpp# include bits/stdc.h# define ll long longusing namespace std;string s[15]{};ll f10,dw0;bool f(int x){if(x1) return 0;for(int i2; isqrt(x); i){if(x%i0) return 0;}return 1;}void dfs(int w,int q,int c,unsigned ll d){if(f1) return;if(cw){if(f(d)){dwd;f11;}return;}if(s[q][c]*){for(int i0; i9; i){dfs(w,q,c1,d*10i);}}else{dfs(w,q,c1,d*10(s[q][c]-0));}}int main(){int n;cin n;for(int i1; in; i){cin s[i];}for(int i1; in; i){dfs(s[i].size(),i,0,0);if(dw0) cout -1endl;else cout dwendl;dw0; f10;}return 0;}___________________________________________________________________分步1.定义cppstring s[15]{};ll f10,dw0;cppint n;2.输入cppcin n;for(int i1; in; i){cin s[i];}3.质数筛从2到sqrt(n)去筛基础cppbool f(int x){if(x1) return 0;for(int i2; isqrt(x); i){if(x%i0) return 0;}return 1;}4.dfs从最小便利可以比暴力算快好多重点难点cppdfs(s[i].size(),i,0,0);cppvoid dfs(int w,int q,int c,unsigned ll d){if(f1) return;if(cw){if(f(d)){dwd;f11;}return;}if(s[q][c]*){for(int i0; i9; i){dfs(w,q,c1,d*10i);}}else{dfs(w,q,c1,d*10(s[q][c]-0));}}5.输出for(int i1; in; i){//dfs(s[i].size(),i,0,0);if(dw0) cout -1endl;else cout dwendl;dw0; f10;}6.总结本题dfs很难用简单方法过