P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib 题解
本蒟蒻第一篇题解，如果有问题请提出
我看见题解里没有发dfs的，于是就发一个
题意
找出所有题目所说长度为n的特殊质数
思路
使用dfs搜索一个n位数，再判断是否符合长度为n的特殊质数
最暴力做法CODE
#include<iostream>
#include<cmath>
using namespace std;
int n;
//判断是否是质数，这里不多说
bool p(int x){
if (x == 1 || x == 0){
return 0;
}
for (int i = 2; i <= sqrt(x); i++){
if (x % i == 0){
return 0;
}
}
return 1;
}
//注意dfs
//sum是用来保存n位数，x是用来表示第几位数
void dfs(int x, int sum){
if (x > n){
int s = sum;
while (s){
//判断是否符合长度为n的特殊质数
if (!p(s)){
return;
}
s /= 10;
}
cout << sum << endl;
return; //注意退出
}
//枚举每一位数
for (int i = 1; i <= 9; i++){
dfs(x + 1, sum * 10 + i);
}
}
int main(){
cin >> n;
dfs(1, 0);
return 0;
}请勿抄本代码，因为这个只有60分
为什么呢？ 因为会爆TLE
时间复杂度足以达到O(n^{13}) ，大于两秒
所以这里要用剪枝
剪枝做法CODE
#include<iostream>
#include<cmath>
using namespace std;
int n;
bool p(int x){
if (x == 1 || x == 0){
return 0;
}
for (int i = 2; i <= sqrt(x); i++){
if (x % i == 0){
return 0;
}
}
return 1;
}
void dfs(int x, int sum){
if (x > n){
int s = sum;
while (s){
if (!p(s)){
return;
}
s /= 10;
}
cout << sum << endl;
return;
}
//直接筛掉不必要的，但要确保sum是有值的
if (sum){
if (!p(sum)){
return;
}
}
for (int i = 1; i <= 9; i++){
dfs(x + 1, sum * 10 + i);
}
}
int main(){
cin >> n;
dfs(1, 0);
return 0;
}