coeforces 665D D. Simple Subset(最大团orsb题)

题目链接：

D. Simple Subset

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

A tuple of positive integers {x1, x2, ..., xk} is called simple if for all pairs of positive integers (i,  j) (1  ≤ i  <  j ≤ k), xi  +  xj is a prime.

You are given an array a with n positive integers a1,  a2,  ...,  an (not necessary distinct). You want to find a simple subset of the array awith the maximum size.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it.

 

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

 

Output

On the first line print integer m — the maximum possible size of simple subset of a.

On the second line print m integers bl — the elements of the simple subset of the array a with the maximum size.

If there is more than one solution you can print any of them. You can print the elements of the subset in any order.

 

Examples input 2
2 3 output 2
3 2 input 2
2 2 output 1
2 input 3
2 1 1 output 3
1 1 2 input 2
83 14 output 2
14 83


题意：

选一个最大的子序列,满足这个序列里的任意两个数的和是素数;

思路：

可以是一个最大完全数的题,也可以是水题,因为奇数+奇数=偶数,偶数+偶数=偶数,(1除外);所以最多有一个奇数和一个偶数;
我写的分情况讨论的代码真是跟翔一样;

AC代码：

#include <bits/stdc++.h> using namespace std; const int N=2e6+6; typedef long long ll; int n,a[1010],flag[N]; int get_prime() {for(int i=2;i<N;i++){if(!flag[i]){for(int j=2*i;j<N;j+=i){flag[j]=1;}}} } queue<int>qu; void print() {printf("%d\n",qu.size());while(!qu.empty()){printf("%d ",qu.front());qu.pop();} }int main() {get_prime();int f=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==1){f++;qu.push(1);}}if(f>1){for(int i=1;i<=n;i++){if(a[i]>1&&!flag[a[i]+1]){for(int j=i+1;j<=n;j++){if(a[j]>1&&!flag[a[i]+a[j]]&&!flag[a[j]+1]){qu.push(a[i]);qu.push(a[j]);print();return 0;}}}}for(int i=1;i<=n;i++){if(a[i]>1&&!flag[a[i]+1]){qu.push(a[i]);print();return 0;}}print();}else if(f==1){for(int i=1;i<=n;i++){if(a[i]>1&&!flag[a[i]+1]){for(int j=i+1;j<=n;j++){if(a[j]>1&&!flag[a[i]+a[j]]&&!flag[a[j]+1]){qu.push(a[i]);qu.push(a[j]);print();return 0;}}}}for(int i=1;i<=n;i++){if(a[i]>1){for(int j=i+1;j<=n;j++){if(a[j]>1&&!flag[a[i]+a[j]]){printf("2\n");printf("%d %d",a[i],a[j]);return 0;}}}}for(int i=1;i<=n;i++){if(a[i]>1&&!flag[a[i]+1]){qu.push(a[i]);print();return 0;}}print();}else{for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(!flag[a[i]+a[j]]){qu.push(a[i]);qu.push(a[j]);print();return 0;}}}printf("1\n");printf("%d",a[1]);}return 0; }

 

转载于:https://www.cnblogs.com/zhangchengc919/p/5421033.html

总结

以上是生活随笔为你收集整理的coeforces 665D D. Simple Subset(最大团orsb题)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。