【题目来源】洛谷P1218 [USACO1.5] 特殊的质数肋骨 Superprime Rib - 洛谷【题目描述】农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨是因为从右边开始切下肋骨每次还剩下的肋骨上的数字都组成一个质数。举例来说7 3 3 1 全部肋骨上的数字 7331 是质数三根肋骨 733 是质数二根肋骨 73 是质数当然最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。写一个程序对给定的肋骨的数目n求出所有的特殊质数。1 不是质数。【输入】一行一个正整数n。【输出】按顺序输出长度为n的特殊质数每行一个。【输入样例】4【输出样例】2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393【核心思想】问题分析给定长度n nn要求找出所有长度为n nn的特殊质数——从最高位到最低位逐位截断后得到的每个前缀都是质数。例如7331 73317331是特殊质数因为7 77、73 7373、733 733733、7331 73317331均为质数。这是一个DFS 逐位构造 质数剪枝问题。算法选择逐位 DFS 构造从最高位开始每次在已有前缀后添加一位数字1 ∼ 9 1 \sim 91∼9形成新数后判断是否为质数质数剪枝若当前前缀不是质数则直接剪枝不再向下扩展因为任何以该前缀开头的数都不可能是特殊质数试除法判质对每个构造出的数用n \sqrt{n}n​范围内的试除法判断质数关键步骤读入n nn目标长度DFS 函数dfs(cnt, num)cnt当前已构造的位数num当前前缀数值遍历i ii从1 11到9 99tmp num * 10 i构造新数若isPrime(tmp)为真若cnt n已到达目标长度输出tmp否则dfs(cnt 1, tmp)继续向下构造启动搜索dfs(1, 0)从 1 位数字、前缀 0 开始时间/空间复杂度时间复杂度O ( 9 n ⋅ 10 n ) O(9^n \cdot \sqrt{10^n})O(9n⋅10n​)实际因大量剪枝远小于此值空间复杂度O ( n ) O(n)O(n)递归深度为n nnDFS 逐位构造的核心思想前缀保持性特殊质数的任意前缀也必须是特殊质数因此可以从高位到低位逐位构造每步验证强剪枝效果一位数质数只有2 , 3 , 5 , 7 2, 3, 5, 72,3,5,7四个以此为前缀的二位数质数更少搜索树分支极少逐层筛选每深入一层就过滤掉大量非质数分支n nn较大时依然高效无后效性当前前缀是否为质数只取决于前缀本身与后续添加的数字无关适用于逐位构造、前缀约束、强剪枝搜索类问题【解题思路】【算法标签】#普及- #DFS-一维【代码详解】#includebits/stdc.husingnamespacestd;intn,st1,ed9,t,tmp;boolisPrime(intn)// 定义质数模板{if(n2)returnfalse;for(inti2;isqrt(n);i){if(n%i0)returnfalse;}returntrue;}voiddfs(intcnt,intnum)// 定义深搜函数{for(inti1;i9;i){// 遍历1-9inttmpnum*10i;// 使用临时变量tmp记录进位后的数字if(isPrime(tmp)){// 判断这个数字是否是质数if(cntn){// 判断此时的cnt是否为ncouttmpendl;// 如果是则输出tmp}else{// 如果cnt还不是n但因为当前数字已经是质数所以要进一步搜索dfs(cnt1,tmp);// cnt自增1使用tmp继续搜索}}}}intmain(){cinn;// 输入ndfs(1,0);// 使用深搜1表示1位数字0表示起始数字为0return0;}【运行结果】4 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393