dfs+剪枝（自行判断）https://www.luogu.com.cn/problem/B4158

张开发
• 2026/4/19 8:42:58 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

dfs+剪枝（自行判断）https://www.luogu.com.cn/problem/B4158
B4158 [BCSP-X 2024 12 月小学高年级组] 质数补全 - 洛谷https://www.luogu.com.cn/problem/B4158#includebits/stdc.husingnamespacestd;#definell long longll n,k; ll arr[9999999]; vectorllp; string t[11]; ll flag0;voiddfs(ll dep,string str){if(flag1)return;if(depk) {if(arr[stoll(str)]0) { flag1; coutstrendl; }return; }if(str[dep]!*) {dfs(dep1,str); }else{for(charx0;x9;x) {//两个if 这里可以剪枝可以不剪枝也能过if(dep 0 x 0)continue;if(depk-1k1) {if(!(x1||x3||x7||x9))continue; } str[dep]x;dfs(dep1,str); } } }voidisp(){for(ll x2;x9999999;x) {if(arr[x]0) { p.push_back(x); }for(autok:p) {if(k*x9999999)break;//不要越界判断好边界就行arr[k*x]1;if(x%k0)break; } } }intmain(){ cinn;isp();for(ll x1;xn;x) { string str;cinstr; t[x]str; }for(ll x1;xn;x) { flag0; kt[x].size();dfs(0,t[x]);if(flag0)cout-1endl; } }

更多文章