[暑假集训--数论]poj2034 Anti-prime Sequences
2024-09-08 10:57:02
Given a sequence of consecutive integers n,n+1,n+2,...,m, an anti-prime sequence is a rearrangement of these integers so that each adjacent pair of integers sums to a composite (non-prime) number. For example, if n = 1 and m = 10, one such anti-prime sequence is 1,3,5,4,2,6,9,7,8,10. This is also the lexicographically first such sequence.
We can extend the definition by defining a degree danti-prime sequence as one where all consecutive subsequences of length 2,3,...,d sum to a composite number. The sequence above is a degree 2 anti-prime sequence, but not a degree 3, since the subsequence 5, 4, 2 sums to 11. The lexicographically .rst degree 3 anti-prime sequence for these numbers is 1,3,5,4,6,2,10,8,7,9.
Input
Input will consist of multiple input sets. Each set will consist of three integers, n, m, and d on a single line. The values of n, m and d will satisfy 1 <= n < m <= 1000, and 2 <= d <= 10. The line 0 0 0 will indicate end of input and should not be processed.
Output
For each input set, output a single line consisting of a comma-separated list of integers forming a degree danti-prime sequence (do not insert any spaces and do not split the output over multiple lines). In the case where more than one anti-prime sequence exists, print the lexicographically first one (i.e., output the one with the lowest first value; in case of a tie, the lowest second value, etc.). In the case where no anti-prime sequence exists, output
No anti-prime sequence exists.
Sample Input
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0
Sample Output
1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
需要一个 l 到 r 的排列,使得任意一个长度是2,3,...,k的子串当中子串和都不是质数
直接搜就是了
#include<cstdio>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int l,r,d,haveans=;
bool mk[];
bool mrk[];
int s[];
int p[],len;
inline void getp()
{
for (int i=;i<=;i++)
{
if (!mk[i])
{
p[++len]=i;
for (int j=*i;j<=;j+=i)mk[j]=;
}
}
}
inline void dfs(int now)
{
if (now==r+)
{
for (int i=l;i<r;i++)printf("%d,",s[i]);
printf("%d\n",s[r]);
haveans=;
return;
}
for (int i=l;i<=r;i++)
{
if (mrk[i])continue;
int sum=i,mrk2=;
for (int j=now-;j>=max(l,now-d+);j--)
{
sum+=s[j];
if(!mk[sum]){mrk2=;break;}
}
if (!mrk2)continue;
mrk[i]=;
s[now]=i;
dfs(now+);
if (haveans)return;
s[now]=;
mrk[i]=;
}
}
int main()
{
getp();
while (~scanf("%d%d%d",&l,&r,&d)&&l+r+d)
{
memset(mrk,,sizeof(mrk));
haveans=;
dfs(l);
if (!haveans)puts("No anti-prime sequence exists.");
}
}
poj 2034
最新文章
- jQuery插件中的this指的是什么
- JS中generater和箭头函数
- 一个php的爬虫,将笔趣阁的书可以都下载下来。
- JAVA NIO概述(一):I/O模型
- Windows下Apache+mod_python+Django配置
- HDU 5428 The Factor
- uva 10205 模拟
- Delphi捕捉DLL执行所抛出的异常。
- Label设置行间距--b
- C++的三大特性:封装、继承和多态性的详解
- 知识小罐头07(tomcat8请求源码分析 下)
- JupyterLab绘制:柱状图,饼状图,直方图,散点图,折线图
- hMailServer SSL 配置
- 标准差(Standard Deviation) 和 标准误差(Standard Error)
- 本地缓存之GUAVA
- Unreal Engine 4 反射机制的实现
- Software Scalability with MapReduce
- lombok入门
- PHP中对用户身份认证实现两种方法
- ubuntu16下面 redis 无法链接到客户端问题
热门文章
- Redis学习记录(三)
- 学习sqlserver的函数方法
- AJAXA进行分页(2)
- C#的接口基础教程之三 定义接口成员
- 01_14_Struts2_结果类型_result_type
- SpringBoot学习1:创建第一个SpringBoot项目
- 51nod——1640 天气晴朗的魔法 有边权限制的最大生成树
- 1143: [CTSC2008]祭祀river
- 1048: [HAOI2007]分割矩阵
- ZJOI2019Round#1