JZOJ4725 质数序列

Description

　　由于去NOI的火车“堵”了数不清时间，小Z和小D打完ETG，闲着无聊开始看今年的JSOI省选题，并尝试着修改题目：
　　对于一个长度为L ≥ 2的序列，X：x1,x2,...,xL ，如果满足对于任意的1 ≤ i < j ≤ L，均有 xi+xj为质数，则他们把X称为一个“质数序列”。
　　现在有一个长度为N的序列，A：a1,a2,...,aN ，他希望从中选取一个包含元素最多的子序列，使得这个子序列是一个质数序列。如果元素个数相同，则使子序列之和最大（在此意义下，保证有唯一解）。
　　因为他们还要xx，所以这个任务就交给你了。

Input

　　输入第一行包含一个正整数 N。
　　接下来一行包含N个正整数，依次描述 a1,a2,...,aN。

Output

　　输出两行，第一行一个整数L，表示最长质数子序列的长度，第二行L个整数从小到大输出，表示最长质数子序列（元素个数相同，则使子序列之和最大）。

Sample Input

3
2 3 4

Sample Output

2
3 4

Data Constraint

对于30%的数据满足N<=100 。
对于60%的数据满足N<=1000 ，ai<=5,000,000 。
对于100%的数据满足N<=1000 ，1<=ai<=15,000,000 。

Solution

　　　　分类讨论，首先没有1的最长质数序列为2。

　　　　1：当1的个数大于2时，可以再寻找一个加1为质数的偶数，没有则输出1的个数

　　　　2: 1的个数等于2时，最优方案就是在序列中寻找两个相加为质数的最大的数字，没有这输出2个1

　　　　3：1的个数小于2时，在序列中寻找两个相加为质数的最大的数字即可

 1 #include<cstdio>
 2 #define N 30000007
 3 #define M 10000000
 4 #define fo(a,b,c) for(int a=b;a<=c;a++)
 5 #define max(a,b) (a)>(b)?(a):(b)
 6 using namespace std;
 7 int n,m,ma,tt,a[2000],z[M],f[N];
 8 int main(){
 9     scanf("%d",&n);
10     fo(i,1,n){
11         scanf("%d",&a[i]);
12         ma=max(a[i],ma);
13         if (a[i]==1) tt++;
14     }
15     fo(i,2,ma*2) f[i]=true;
16     fo(i,1,ma*2){
17         if (f[i]) z[++m]=i;
18         fo(j,1,m){
19             if (i*z[j]>ma*2) break;
20             f[i*z[j]]=false;
21         }
22     }
23     if (tt>2){
24         int x=0;
25         fo(i,1,n)
26             if (a[i]!=1&&f[a[i]+1])
27                 x=max(x,a[i]);
28         if (x==0){
29             printf("%d
",tt);
30             fo(i,1,tt)
31                 printf("1 ");
32             printf("
");
33         }
34         else{
35             printf("%d
",tt+1);
36             fo(i,1,tt)
37                 printf("1 ");
38             printf("%d
",x);
39         }
40     }
41     if (tt==2){
42         int x=0,y=0,w=0;
43         fo(i,1,n)
44             if (a[i]!=1&&f[a[i]+1])
45                 x=max(x,a[i]);
46         if (x)
47             printf("3
1 1 %d
",x);
48         else{
49             fo(i,1,n-1)
50                 fo(j,i+1,n)
51                     if (f[a[i]+a[j]]&&a[i]+a[j]>w)
52                     {
53                         w=a[i]+a[j];
54                         x=a[i];y=a[j];
55                     }
56             if (x>y){
57                 int z=x;x=y;y=z;    
58             }
59             printf("2
%d %d
",x,y);
60         }
61     }
62     if (tt<2)
63     {
64         int x=0,y=0,w=0;
65         fo(i,1,n-1)
66             fo(j,i+1,n)
67                 if (f[a[i]+a[j]]&&a[i]+a[j]>w){
68                     w=a[i]+a[j];
69                     x=a[i];y=a[j];
70                 }
71         if (x>y){
72             int z=x;x=y;y=z;    
73         }
74         printf("2
%d %d
",x,y);
75     }
76 }

View Code