D. Simple Subset

題目連接：

http://www.codeforces.com/contest/665/problem/D

Description

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 a with 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.

Sample Input

2
2 3

Sample Output

2
3 2

Hint

題意

給你n個數，你需要找到一個最大的子集，使得這個子集中的任何兩個數加起來都是質數。

題解：

無視掉1的話，我們最多選擇一個奇數和一個偶數，因為奇數+奇數=偶數，偶數加偶數=偶數
所以直接暴力枚舉就好了。
另外這道題如果建邊的話，跑dfs直接莽一波最大團也可以……

我是一個智障，我就跑了最大團 QAQ

代碼

#include<bits/stdc++.h> using namespace std; const int maxn = 1005; int pri[2000005]; bool flag[maxn], a[maxn][maxn]; int ans, cnt[maxn], group[maxn], n, vis[maxn]; // 最大團： V中取K個頂點，兩點間相互連接 // 最大獨立集： V中取K個頂點，兩點間不連接 // 最大團數量 = 補圖中最大獨立集數bool dfs( int u, int pos ){int i, j;for( i = u+1; i <= n; i++){if( cnt[i]+pos <= ans ) return 0;if( a[u][i] ){// 與目前團中元素比較，取 Non-N(i)for( j = 0; j < pos; j++ ) if( !a[i][ vis[j] ] ) break;if( j == pos ){ // 若為空，則皆與 i 相鄰，則此時將i加入到 最大團中vis[pos] = i;if( dfs( i, pos+1 ) ) return 1;}}}if( pos > ans ){for( i = 0; i < pos; i++ )group[i] = vis[i]; // 最大團 元素ans = pos;return 1;}return 0; } void maxclique() {ans=-1;for(int i=n;i>0;i--){vis[0]=i;dfs(i,1);cnt[i]=ans;} } void pre() {pri[1]=1;pri[0]=1;for(int i=2;i<2000005;i++){if(pri[i])continue;for(int j=i+i;j<2000005;j+=i)pri[j]=1;} } int aa[maxn]; int main() {pre();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&aa[i]);for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(!pri[aa[i]+aa[j]])a[i][j]=1,a[j][i]=1;maxclique();cout<<ans<<endl;for(int i=0;i<ans;i++)cout<<aa[group[i]]<<" ";cout<<endl; }

轉載于:https://www.cnblogs.com/qscqesze/p/5419069.html

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 12 D. Simple Subset 最大团的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。