企业官网建设流程全解析

题目

# 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

### 输入 #1

```
10
1*
3**
7**
83*7
2262
6**1
29*7
889*
777*
225*
```

### 输出 #1

```
11
307
701
8317
-1
6011
2917
8893
-1
2251
```

## 输入输出样例 #2

### 输入 #2

```
10
4039***
2***5*5
4099961
25**757
7***0**
1***00*
41811*9
6***0*7
8***1**
6561*59
```

### 输出 #2

```
4039019
-1
4099961
2509757
7000003
1000003
4181129
6000047
8000101
6561259
```

## 说明/提示

### 样例 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 long
using namespace std;
string s[15]={};
ll f1=0,dw=0;
bool f(int x){
if(x<=1) return 0;
for(int i=2; i<=sqrt(x); i++){
if(x%i==0) return 0;
}
return 1;
}
void dfs(int w,int q,int c,unsigned ll d){
if(f1) return;
if(c==w){
if(f(d)){
dw=d;
f1=1;
}
return;
}
if(s[q][c]=='*'){
for(int i=0; i<=9; i++){
dfs(w,q,c+1,d*10+i);
}
}else{
dfs(w,q,c+1,d*10+(s[q][c]-'0'));
}
}
int main(){
int n;
cin >>n;
for(int i=1; i<=n; i++){
cin >>s[i];
}
for(int i=1; i<=n; i++){
dfs(s[i].size(),i,0,0);
if(dw==0) cout <<-1<<endl;
else cout <<dw<<endl;
dw=0; f1=0;
}
return 0;
}

___________________________________________________________________

分步

1.定义

cpp

string s[15]={};
ll f1=0,dw=0;

cpp

int n;

2.输入

cpp

cin >>n;
for(int i=1; i<=n; i++){
cin >>s[i];
}

3.质数筛

从2到sqrt(n)去筛，基础

cpp

bool f(int x){
if(x<=1) return 0;
for(int i=2; i<=sqrt(x); i++){
if(x%i==0) return 0;
}
return 1;
}

4.dfs

从最小便利，可以比暴力算快好多（重点，难点）

cpp

dfs(s[i].size(),i,0,0);

cpp

void dfs(int w,int q,int c,unsigned ll d){
if(f1) return;
if(c==w){
if(f(d)){
dw=d;
f1=1;
}
return;
}
if(s[q][c]=='*'){
for(int i=0; i<=9; i++){
dfs(w,q,c+1,d*10+i);
}
}else{
dfs(w,q,c+1,d*10+(s[q][c]-'0'));
}
}

5.输出

for(int i=1; i<=n; i++){
//dfs(s[i].size(),i,0,0);
if(dw==0) cout <<-1<<endl;
else cout <<dw<<endl;
dw=0; f1=0;
}

6.总结

本题dfs很难用简单方法过