首页 > 试题广场 >

素数伴侣

[编程题]素数伴侣
  • 热度指数：188052 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义两个正整数 a 和 b 是“素数伴侣”，当且仅当 a + b 是一个素数。
\hspace{15pt}现在，密码学会邀请你设计一个程序，从给定的 n 个正整数 \left\{a_1, a_2, \dots, a_n\right\} 中，挑选出最多的“素数伴侣”，你只需要输出挑选出的“素数伴侣”对数。保证 n 为偶数，一个数字只能使用一次。

输入描述:
\hspace{15pt}第一行输入一个正偶数 n \left(2 \leqq n \leqq 100\right) 代表数字个数。
\hspace{15pt}第二行输入 n 个正整数 a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 3 \times 10^4 \right) 代表给定的数字。


输出描述:
\hspace{15pt}输出一个整数，代表最多可以挑选出的“素数伴侣”的数量。
示例1

输入

4
2 5 6 13

输出

2

说明

\hspace{15pt}在这个样例中，2 和 5 可以组成一对素数伴侣，6 和 13 也可以组成一对素数伴侣。因此，最多可以挑选出 2 对素数伴侣。
示例2

输入

4
1 2 2 2

输出

1

说明

\hspace{15pt}在这个样例中，1 只能使用一次，与任意一个 2 组合均是“素数伴侣”。
示例3

输入

2
3 6

输出

0
算法知识视频讲解
查看答案及解析
添加回答
推荐
toraoh头像 toraoh
OK，我们把这个话题终结一下。

所有想着动态规划的，你们放弃吧，不是这么玩的。

考虑使用图论的方法来给这个题建模。
100个数看成100个点，如果这两个数加起来的和是素数，给这两个数中间连一条边。
之后，我们要选择尽可能多的边，要求这些边不共享端点。
——这个东西呢，叫做一般无向图的最大匹配。

但是，一般无向图的最大匹配，这个算法的难度，有点，大……
这个问题，合适的算法叫，带花树开花算法。
现场推完这么多，写一个正确的，有点不科学……

我们考虑再分析一下这个题
注意到，每个数的取值范围是[2,30000]
素数，除了2是偶数，其他是奇数——而现在不可能出现2了，所以我们只考虑奇数的素数
2个数的和是奇数，有什么情况呢？
只有奇数+偶数
所以，我们把这些数分成2堆——奇数和偶数，然后在他们中间，和是素数的，连上一条边，然后做匹配。
——肯定有人会说，你这个和前面的建图有什么本质不同的地方吗？
——是没有，但是我们说明了得到的图一定是二分图，这是有意义的。
因为对二分图的最大匹配，有一个简单很多的算法，匈牙利算法。

我们先说明一下，什么是二分图。
二分图就是，你可以把图上的点分成2堆，每堆之内的点不会有边，2堆之间，才可能连边。换句话说，一条边，必定连2个来自不同堆的点。
现在，对每条边，一定连一个奇数，一个偶数，点能按奇数和偶数分成两部分，刚好就是二分图嘛！

有关二分图匹配的匈牙利算法，具体请自行搜索，这里扯一下我个人对这个算法的理解。

外层，暴力考虑左边每个点
对枚举的每个左边的点，要找右边一个点来匹配。
那就是对左边的点，我们看他连出去的边，或者说，能连到的右边的点
有2种情况：
1、右边的点没人匹配——我直接贪心匹配上去
2、右边的点有人匹配——考虑把目前与这个右边的点 x 匹配的左边的点 pre[x]，重新匹配一个其他的点，如果成功了，那pre[x]原来匹配的点x就释放开了，我可以直接占领上去。
最后统计匹配成功多少个左边的点就行了。

匈牙利算法真的还是很短的，比你写一个红黑树轻松多了： 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> G[105];

bool flag[105];
int pre[105];

bool dfs(int k){
    int x;
    for(int i=0;i<G[k].size();i++){
        x=G[k][i];
        if (flag[x]) continue;
        flag[x]=true;
        if((pre[x]==0)||dfs(pre[x])){
            pre[x]=k;
            return true;
        }
    }
    return false;
}

bool isprime[80000];
int nums[105];

int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(isprime[nums[i]+nums[j]]){
                    (nums[i]&1)?G[i].push_back(j):G[j].push_back(i);
                }
            }
        }

        memset(pre,0,sizeof(pre));
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(flag,false,sizeof(flag));
            if (dfs(i)) ans++;
        }
        printf("%d\n",ans);
        
        for(int i=1;i<=n;++i){
            G[i].clear();
        }
    }
    return 0;
}

（当然，你用网络流做二分图最大匹配，没人拦你。）

最后，给好学的人：
一般图匹配（牛刀）来做这个题（杀鸡）的代码：
带花树开花的模板 CopyRight Claris（http://www.lydsy.com/JudgeOnline/userinfo.php?user=Claris） 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=510;
int n,m,x,y;vector<int>g[N];
namespace Blossom{
    int mate[N],n,ret,nxt[N],f[N],mark[N],vis[N];queue<int>Q;
    int F(int x){return x==f[x]?x:f[x]=F(f[x]);}
    void merge(int a, int b){f[F(a)]=F(b);}
    int lca(int x, int y){
        static int t=0;t++;
        for(;;swap(x,y)) if(~x){
            if(vis[x=F(x)]==t) return x;vis[x]=t;
            x=mate[x]!=-1?nxt[mate[x]]:-1;
        }
    }
    void group(int a, int p){
        for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){
            b=mate[a],c=nxt[b];
            if(F(c)!=p)nxt[c]=b;
            if(mark[b]==2)mark[b]=1,Q.push(b);
            if(mark[c]==2)mark[c]=1,Q.push(c);
        }
    }
    void aug(int s, const vector<int>G[]){
        for(int i=0;i<n;++i)nxt[i]=vis[i]=-1,f[i]=i,mark[i]=0;
        while(!Q.empty())Q.pop();Q.push(s);mark[s]=1;
        while(mate[s]==-1&&!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0,y;i<(int)G[x].size();++i){
                if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){
                    if(mark[y]==1){
                        int p=lca(x,y);
                        if(F(x)!=p)nxt[x]=y;
                        if(F(y)!=p)nxt[y]=x;
                        group(x,p),group(y,p);
                    }else if(mate[y]==-1){
                        nxt[y]=x;
                        for(int j=y,k,l;~j;j=l)k=nxt[j],l=mate[k],mate[j]=k,mate[k]=j;
                        break;
                    }else nxt[y]=x,Q.push(mate[y]),mark[mate[y]]=1,mark[y]=2;
                }
            }
        }
    }
    int solve(int _n, const vector<int>G[]){
        n=_n;memset(mate, -1, sizeof mate);
        for(int i=0;i<n;++i) if(mate[i]==-1)aug(i,G);
        for(int i=ret=0;i<n;++i)ret+=mate[i]>i;
        printf("%d\n",ret);
        //for(int i=0;i<n;i++)printf("%d %d\n",i+1,mate[i]+1);
        return ret;
    }
}
bool isprime[80000];
int nums[105];
int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(isprime[nums[i]+nums[j]]){
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        Blossom::solve(n,g);
        for(int i=0;i<n;++i){
            g[i].clear();
        }
    }
}

最后吐槽：华为这题出得都快和微软一个尿性了，二分图匹配和DAG上求支配者树，这个都不怎么好想出来的，硬生生想出来的，这个值得膜一膜，但是做出这个题的人，更多情况是，学过这个东西吧？
（你看这题的讨论区，多少人跳进了dp的大坑爬不出来？）
于是这是笔试题/面试题从一个极端走向另一个极端（从语言和库知多少，走向算法知识知多少 ） ？
编辑于 2016-09-10 13:03:39 回复(48)
提交观点

问题信息

查找 排序
难度：
0条回答 57814浏览

热门推荐

通过挑战的用户

查看代码

相关试题

素数伴侣

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号