洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib 使用四种算法
2024-10-08 07:57:03
洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
水题一道……
题目描述
农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。
输入格式
单独的一行包含N。
输出格式
按顺序输出长度为 N 的特殊质数,每行一个。
输入输出样例
输入 #1复制
4
输出 #1复制
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
说明/提示
题目翻译来自NOCOW。
USACO Training Section 1.5
Solution
Algorithm1
可以枚举10n-1~10n之间所有的数，再依次把这个数除以10，判断其是否为质数。
一旦不是就跳出循环。O（n）
Code1
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#define IL inline
using namespace std;
int n;
bool flag;
IL bool prime(int num)
{
if(num<=) return ;
for(int i=;i<=sqrt(num);i++)
if(num%i==) return ;
return ;
}
int main()
{
cin>>n;
for(int i=pow(,n-);i<pow(,n);i++)
{
flag=;
for(int j=i;j>;j/=)
if(!prime(j)){
flag=;
break;
}
if(flag) cout<<i<<endl;
} return ;
}
Code1
Algorithm2
事实证明，在$n = 6$时，计算速度太慢了。于是我想到了可以把prime表先打出来。
为了节省空间，使用bool型数组table。table[i]表示i是否为质数。
Code2
//504……
//若需查看，请复制下面的链接
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
这里就不给出代码了，因为没有很大的意义。
如需代码请在下方评论
好吧……我还是上传了
（使用了记忆化）
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#define IL inline
using namespace std;
int n;
bool flag;
map<int,bool>table,vis;
IL bool prime(int num)
{
if(num<=) return ;
if(vis[num]) return table[num];
vis[num]=;
for(int i=;i<=sqrt(num);i++)
if(num%i==) return table[num]=;
return table[num]=;
}
int main()
{
cin>>n;
for(int i=pow(,n-);i<pow(,n);i++)
{
flag=;
for(int j=i;j>;j/=)
if(!prime(j)){
flag=;
break;
}
if(flag) cout<<i<<endl;
}
return ;
}
Code3
Algorithm4
类似于枚举每一位数的想法
使用dfs决定某一位数能放什么。
从0位开始，到n位时输出答案。
Code4
#include<iostream>//不想OI一场空，千万别用万能头
#include<algorithm>//快排sort()
#include<cstdio>//能不用cin就不用
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#define IL inline
using namespace std;
int n;
bool flag;
IL bool prime(int num)
{
if(num<=) return ;
for(int i=;i<=sqrt(num);i++)
if(num%i==) return ;
return ;
}
IL void dfs(int depth,int num)
{
if(depth==n){
cout<<num<<endl;
return;
}
num*=;
for(int i=;i<=;i++)
if(prime(num+i))
dfs(depth+,num+i);
}
int main()
{
cin>>n;
dfs(,);
return ;
}
Attention
无……
水题一道……
最新文章
- 【iOS atomic、nonatomic、assign、copy、retain、weak、strong】的定义和区别详解
- Nginx安装与使用
- BC68(HD5606) 并查集+求集合元素
- Sails 关闭自动路由 Automatic Routes 功能。
- Makefile中指示符“include”、“-include”和“sinclude”的区别
- 表情键盘及文字表情识别简单demo
- 最新首发Eclipse+CDT+android-ndk写纯c++安卓应用（附openGL Es）
- docker 创建镜像
- Mockito简介（转）
- 修改node来增加自定义工具命令
- 2.sublime设置本地远程代码同步
- KnockOut 绑定之foreach绑定
- selenium处理元素定位到了点击无效问题
- [转]IISExpress配置使其能通过IP访问方法
- 【异常记录(九)】 System.Threading.ThreadAbortException: 正在中止线程
- 微信分享 apicloud方式 中遇到的坎
- 表格边框重复合并属性: border-collapse:collapse;
- HDU 3179 二叉搜索树（树的建立）
- 以图文解锁 HTTPS原理***
- 51Nod - 1242 斐波那契（快速幂）