題目# B4158 [BCSP-X 2024 12 月小學(xué)高年級(jí)組] 質(zhì)數(shù)補(bǔ)全## 題目描述Alice 在紙條上寫了一個(gè)質(zhì)數(shù)第二天再看時(shí)發(fā)現(xiàn)有些地方污損看不清了。- 在大于 $1$ 的自然數(shù)中除了 $1$ 和它本身以外不再有其他因數(shù)的自然數(shù)稱為質(zhì)數(shù)請(qǐng)你幫助 Alice 補(bǔ)全這個(gè)質(zhì)數(shù)若有多解輸出數(shù)值最小的若無(wú)解輸出 $-1$。例如紙條上的數(shù)字為 $\tt{1*}$$\tt{*}$ 代表看不清的地方那么這個(gè)質(zhì)數(shù)有可能為 $11, 13, 17, 19$其中最小的為 $11$。## 輸入格式第一行 $1$ 個(gè)整數(shù) $t$代表有 $t$ 組數(shù)據(jù)。接下來(lái) $t$ 行每行 $1$ 個(gè)字符串 $s$ 代表 Alice 的數(shù)字僅包含數(shù)字或者 $\tt{*}$并且保證首位不是 $\tt{*}$ 或者 $0$。## 輸出格式輸出 $t$ 行每行 $1$ 個(gè)整數(shù)代表最小可能的質(zhì)數(shù)或者 $-1$ 代表無(wú)解。## 輸入輸出樣例 #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## 說(shuō)明/提示### 樣例 3-6參考附件中的樣例。### 數(shù)據(jù)范圍$|s|$ 代表 $s$ 串的長(zhǎng)度對(duì)于所有數(shù)據(jù)$1 \leq t \leq 10, 1 \leq |s| \leq 7$$s$ 中僅包含數(shù)字或者 $\tt{*}$并且保證首位不是 $\tt{*}$ 或者 $0$。本題采用捆綁測(cè)試你必須通過(guò)子任務(wù)中的所有數(shù)據(jù)點(diǎn)以及其依賴的子任務(wù)才能獲得子任務(wù)對(duì)應(yīng)的分?jǐn)?shù)。| 子任務(wù)編號(hào) | 分值 | $\mid s\mid$ | 特殊性質(zhì) | 子任務(wù)依賴 || :----------: | :----------: | :----------: | :----------: | :----------: || $1$ | $35$ | $\leq 7$ | $s$ 中沒(méi)有 $\tt{*}$ | || $2$ | $30$ | $\leq 4$ | | || $3$ | $24$ | $\leq 7$ | $s$ 中至多包含 $1$ 個(gè) $\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.質(zhì)數(shù)篩從2到sqrt(n)去篩基礎(chǔ)cppbool f(int x){if(x1) return 0;for(int i2; isqrt(x); i){if(x%i0) return 0;}return 1;}4.dfs從最小便利可以比暴力算快好多重點(diǎn)難點(diǎn)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.總結(jié)本題dfs很難用簡(jiǎn)單方法過(guò)