題目# B4158 [BCSP-X 2024 12 月小學高年級組] 質數補全## 題目描述Alice 在紙條上寫了一個質數第二天再看時發(fā)現有些地方污損看不清了。- 在大于 $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很難用簡單方法過