首页 > 代码库 > 【质数序列】
【质数序列】
先把原题贴一下
质数序列
【问题描述】
由于去NOI的火车“堵”了数不清时间，小Z和小D打完ETG，闲着无聊开始看今年的JSOI省选题，并尝试着修改题目：
对于一个长度为L ≥ 2的序列，，如果满足对于任意的1 ≤ i < j ≤ L，均有为质数，则他们把X称为一个“质数序列”。
现在有一个长度为N的序列，，他希望从中选取一个包含元素最多的子序列，使得这个子序列是一个质数序列。如果元素个数相同，则使子序列之和最大（在此意义下，保证有唯一解）。
因为他们还要xx，所以这个任务就交给你了。
【输入格式】
从文件 prime.in 中读入数据。
输入第一行包含一个正整数 N。
接下来一行包含N个正整数，依次描述。
【输出格式】
输出到文件 prime.out 中。
输出两行，第一行一个整数L，表示最长质数子序列的长度，第二行L个整数从小到大输出，表示最长质数子序列（元素个数相同，则使子序列之和最大）。
【样例输入】
3
2 3 4
【样例输出】
2
3 4
【数据规模与约定】
对于30%的数据满足N≤100。
对于60%的数据满足N≤1000，ai≤5,000,000。
对于100%的数据满足N≤1000，1≤ai≤15,000,000。
以下是题解
对于＞1的整数有以下特点
奇数+奇数不是质数
偶数+偶数不是质数
所以一个质数序列里最多只能有一个奇数(>1的奇数)与一个偶数
这时我们就可以将数据分为奇偶两部分然后枚举求解
以上是在ai>1时的情况，序列中只能有两个解
当数据里有1时，序列里可以有多个1，但是就不可以再有其他的奇数了，但是这并不影响偶数的选择(因为1不是偶数233)
我们可以根据序列里1的个数分为3种情况
1:1的数量>2
2:1的数量<2
3:1的数量=2
对于这三种情况的解法
1:这时含1的序列的序列长一定大于你枚举出的序列的序列长，寻找一遍是否有符合条件(+1是质数)的偶数输出即可
2:这时含1的序列的序列长≤2，子序列之和一定小于等于你枚举出的序列，枚举即可
3:这种情况又分为两种情况：
3.1有符合条件的偶数
3.2无符合条件的偶数
3.1:含1的序列的序列长=3，一定大于枚举的序列的序列长，输出含1的序列
3.2:含1的序列的序列长=2,子序列之和小于枚举出的序列，输出枚举的序列
复杂度为n2+n㏒n
以下是代码
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define MAXN 1005 5 #define MAXP 10005 6 #define MAXM 30000005 7 using namespace std;bool I[MAXM]; 8 int A[MAXN],B[MAXN],prim[MAXM]; 9 int N,Al=0,Bl=0,ans=0,ax=0,bx=0,len=0; 10 bool Y(int com){ 11 if(!I[com])return true; 12 return false; 13 } 14 int main(){ 15 int a,b,c,i,j,n; 16 freopen("prime.in","r",stdin); 17 freopen("prime.out","w",stdout); 18 for(i=2;i<=MAXM;i++){ 19 if(!I[i]){prim[++len]=i;} 20 for(j=1;j<=len;j++){ 21 if(prim[j]*i>MAXM)break; 22 I[prim[j]*i]=1; 23 } 24 } 25 scanf("%d",&N); 26 for(i=1;i<=N;i++){ 27 scanf("%d",&a); 28 if(a%2==0)A[++Al]=a; 29 else B[++Bl]=a; 30 }c=0; 31 if(Al!=0)sort(A+1,A+1+Al); 32 if(Bl!=0)sort(B+1,B+1+Bl); 33 while(B[c+1]==1)c++; 34 if(c>=3){b=0; 35 for(i=Al;i>=1;i--) 36 if(Y(A[i]+1)){b=A[i];break;} 37 if(b!=0)printf("%d\n",c+1); 38 else printf("%d\n",c); 39 for(j=1;j<=c;j++)printf("1 "); 40 if(b!=0)printf("%d",b); 41 return 0; 42 } 43 if(c==2){b=0; 44 for(i=Al;i>=1;i--) 45 if(Y(A[i]+1)){b=A[i];break;} 46 if(b!=0){printf("%d\n",c+1); 47 for(j=1;j<=c;j++)printf("1 "); 48 printf("%d",b);return 0; 49 } 50 } 51 for(i=Al;i>=1;i--){ 52 if(A[i]+B[Bl]<=ans)break; 53 for(j=Bl;j>=1;j--){ 54 if(Y(A[i]+B[j])){ 55 if(ans<A[i]+B[j]){ 56 ax=A[i];bx=B[j]; 57 ans=ax+bx; 58 }break; 59 } 60 } 61 } 62 if(ax+bx==0) 63 {printf("2\n1 1");return 0;} 64 if(ax>bx)swap(ax,bx); 65 printf("2\n%d %d",ax,bx); 66 }
【质数序列】