洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib 使用四种算法

洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib

水题一道……

题目描述

农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。

输入格式

单独的一行包含N。

输出格式

按顺序输出长度为 N 的特殊质数,每行一个。

输入输出样例

输入 #1

输出 #1

说明/提示

题目翻译来自NOCOW。

USACO Training Section 1.5

Solution

Algorithm1

可以枚举10^n-1~10ⁿ之间所有的数，再依次把这个数除以10，判断其是否为质数。

一旦不是就跳出循环。O（n）

Code1

 1 #include<iostream>//不想OI一场空，千万别用万能头
 2 #include<algorithm>//快排sort()
 3 #include<cstdio>//能不用cin就不用
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<vector>
 8 #include<queue>
 9 #define IL inline
10 using namespace std;
11 int n;
12 bool flag;
13 IL bool prime(int num)
14 {
15     if(num<=1) return 0;
16     for(int i=2;i<=sqrt(num);i++)
17     if(num%i==0) return 0;
18     return 1;
19 }
20 int main()
21 {
22     cin>>n;
23     for(int i=pow(10,n-1);i<pow(10,n);i++)
24     {
25         flag=1;
26         for(int j=i;j>0;j/=10)
27         if(!prime(j)){
28             flag=0;
29             break;
30         }
31         if(flag) cout<<i<<endl;
32     }
33     
34     return 0;
35 }

Code1

Algorithm2

事实证明，在$n = 6$时，计算速度太慢了。于是我想到了可以把prime表先打出来。

为了节省空间，使用bool型数组table。table[i]表示i是否为质数。

Code2

1 //504……
2 //若需查看，请复制下面的链接
3 https://files-cdn.cnblogs.com/files/send-off-a-friend/%E6%B4%9B%E8%B0%B7P1218%E6%89%93%E8%A1%A8%E7%A8%8B%E5%BA%8F%E5%92%8C%E6%8F%90%E4%BA%A4%E7%A8%8B%E5%BA%8F%E4%B8%8E%E6%BA%90%E4%BB%A3%E7%A0%81.rar

Code2

Algorithm3

但是数组的空间的有限的，没法开那么大的数组。

考虑使用map<int,bool>table

这样就可以多存一点了

STL大法好……

Code3

这里就不给出代码了，因为没有很大的意义。

如需代码请在下方评论

好吧……我还是上传了

（使用了记忆化）

 1 #include<iostream>//不想OI一场空，千万别用万能头
 2 #include<algorithm>//快排sort()
 3 #include<cstdio>//能不用cin就不用
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<vector>
 8 #include<queue>
 9 #define IL inline
10 using namespace std;
11 int n;
12 bool flag;
13 map<int,bool>table,vis;
14 IL bool prime(int num)
15 {
16     if(num<=1) return 0;
17     if(vis[num]) return table[num];
18     vis[num]=1;
19     for(int i=2;i<=sqrt(num);i++)
20     if(num%i==0) return table[num]=0;
21     return table[num]=1;
22 }
23 int main()
24 {
25     cin>>n;
26     for(int i=pow(10,n-1);i<pow(10,n);i++)
27     {
28         flag=1;
29         for(int j=i;j>0;j/=10)
30         if(!prime(j)){
31             flag=0;
32             break;
33         }
34         if(flag) cout<<i<<endl;
35     }
36     return 0;
37 }

Code3

Algorithm4

类似于枚举每一位数的想法

使用dfs决定某一位数能放什么。

从0位开始，到n位时输出答案。

Code4

 1 #include<iostream>//不想OI一场空，千万别用万能头
 2 #include<algorithm>//快排sort()
 3 #include<cstdio>//能不用cin就不用
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<vector>
 8 #include<queue>
 9 #define IL inline
10 using namespace std;
11 int n;
12 bool flag;
13 IL bool prime(int num)
14 {
15     if(num<=1) return 0;
16     for(int i=2;i<=sqrt(num);i++)
17     if(num%i==0) return 0;
18     return 1;
19 }
20 IL void dfs(int depth,int num)
21 {
22     if(depth==n){
23         cout<<num<<endl;
24         return;
25     }
26     num*=10;
27     for(int i=0;i<=9;i++)
28     if(prime(num+i))
29     dfs(depth+1,num+i);
30 }
31 int main()
32 {
33     cin>>n;
34     dfs(0,0);
35     return 0;
36 }

Attention

无……

水题一道……