JZOJ 4725. 质数序列

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 。

 

做法：思考一下就会发现，本体其实只有3种情况

{

　　若序列中不存在1或只有1个1，那么最长的长度一定为2，此时只要找两个最大的就好

　　若序列中存在2个1，那么寻找序列中最大的一个能和1组成质数的数，若找不到，视作情况1

　　若序列中存在3个及以上的1，那么参考情况2，若找不到，输出1的个数和所有的1即可

}

 

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#define N 1007
#define M 30000007
#define LL long long
using namespace std;
int n,zs[M/2],T1;
LL a[N],sum,q,p;
bool b[M + 20];

void Pre_work(){
    for(int i=2;i<=M;i++){
        if(!b[i])    zs[++zs[0]]=i;
        for(int j=1;j<=zs[0];j++)
            if((LL)i*zs[j]<=M-5)    b[i*zs[j]]=1;
            else break;
    }
}

int main(){
    Pre_work();
    memset(a,0,sizeof(a));
    q=0,p=0,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if (a[i]==1) T1++;
    }
    if (T1>2){
        for (int i=1;i<=n;i++)
            if (!b[a[i]+1])    q=max(q,a[i]);
        if (q!=0 && q!=1){
            printf("%d
",T1+1);
            for (int i=1;i<=T1;i++)    printf("1 ");
            printf("%lld",q);
        }
        else{
            printf("%d
",T1);
            for (int i=1;i<=T1;i++)    printf("1 ");
        }
        return 0;
    }
    else if (T1==2){
        for (int i=1;i<=n;i++)
            if (!b[a[i]+1])    q=max(q,a[i]);
        if (q!=0 && q!=1){
            printf("%d
",T1+1);
            for (int i=1;i<=T1;i++)    printf("1 ");
            printf("%lld",q);
            return 0;
        }
    }
    else{
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
                if (!b[a[i]+a[j]]){
                    if(a[i]+a[j]>sum){
                        q=a[i],p=a[j];
                        sum=q+p;
                    }
                }
        printf("2
");
        if (q>p) swap(q,p);
        printf("%lld %lld", q, p);
    }
}