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

水题一道……

题目描述

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

输入格式

单独的一行包含N。

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

2333233923932399293931193137373337393793379759397193733173337393

说明/提示

题目翻译来自NOCOW。

USACO Training Section 1.5

Solution

Algorithm1

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

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

Code1

1 #include
      
       //不想OI一场空，千万别用万能头 2 #include
       
        //快排sort() 3 #include
        
         //能不用cin就不用 4 #include
         
           5 #include
          
            6 #include
            7 #include
            
              8 #include
             
               9 #define IL inline10 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
              
               0;j/=10)27 if(!prime(j)){28 flag=0;29 break;30 }31 if(flag) cout<
               <

Code1

Algorithm2

事实证明，在$n \req 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
      
       //不想OI一场空，千万别用万能头 2 #include
       
        //快排sort() 3 #include
        
         //能不用cin就不用 4 #include
         
           5 #include
          
            6 #include
            7 #include
            
              8 #include
             
               9 #define IL inline10 using namespace std;11 int n;12 bool flag;13 map
              
               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
               
                0;j/=10)30 if(!prime(j)){31 flag=0;32 break;33 }34 if(flag) cout<
                <

Code3

Algorithm4

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

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

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

Code4

1 #include
     
      //不想OI一场空，千万别用万能头 2 #include
      
       //快排sort() 3 #include
       
        //能不用cin就不用 4 #include
        
          5 #include
         
           6 #include
           7 #include
           
             8 #include
            
              9 #define IL inline10 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<
             
              <
              
               >n;34 dfs(0,0);35 return 0;36 }

Attention

无……

水题一道……

转载于:https://www.cnblogs.com/send-off-a-friend/p/11377785.html

你可能感兴趣的文章