简要题意
Virtual Judge 传送门 | Codeforces Gym 传送门
给出一个长度为 \(n\) 的序列 \(a\),你需要从中选出一些数,使其两两相加不为质数。输出最大可以选择多少个数。
\(1 \leq n \lt 750,1 \leq a_i \lt 10^7\)
思路
Imakf 学长推荐的题。
首先我们发现,如果对于任意两个数 \(a_i,a_j\),如果 \((a_i+a_j)\in\mathbb{P}\),连边 \((i,j)\)。然后答案就是图的最大独立集。但是一般图最大独立集是 NP-Complete 问题,目前没有多项式时间复杂度解法。
考虑到若 \(a_i,a_j\neq 1\),那么若 \((a_i+a_j)\in\mathbb{P}\),则 \(a_i\bmod 2\neq b_i\bmod 2\)。则若满足上述条件连边,就一定得到的是二分图。
好,然后跑二分图最大匹配,最后将二分图最大匹配转换成二分图最大独立集即可。
等一下,\(a_i=a_j=1\) 的问题我们没有解决,由于如果独立集中有两个及以上 \(1\) 就一定会有质数和出现(\(1+1=2,2\in\mathbb{P}\)),所以我们对值为 \(1\) 的 \(a_i\) 去重即可。
使用匈牙利算法求解二分图最大匹配,时间复杂度均摊 \(O(\max a+n\cdot\frac{n^2}{\log n})\)(这个复杂度是我用素数定理乱算的),理论复杂度上界 \(O(\max a+n^3)\)。可以通过本题。
(思路不难,细节贼多)
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int pri[20000005];
bool vis[20000005];
int tot;
int n,p[800];
struct edge{
int nxt,to;
} g[10000005];
int head[800],ec;
void add(int u,int v){
g[++ec].nxt=head[u];
g[ec].to=v;
head[u]=ec;
}
int vist[800],mch[800];
bool hungry(int u,int tag){
if(vist[u]==tag) return false;
vist[u]=tag;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(mch[v]==0||hungry(mch[v],tag)){
mch[v]=u;
return true;
}
}
return false;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
vis[1]=1;vis[0]=1;
for(int i=2;i<=(2e7);i++){
if(!vis[i]){
pri[++tot]=i;
}
for(int j=1;j<=tot&&i*pri[j]<=(2e7);j++){
vis[i*pri[j]]=1;
if(!(i%pri[j]))break;
}
}
for(int i=1;i<=n;i++) cin>>p[i];
sort(p+1,p+n+1, greater<int>());
if(p[n]==1){
while(p[n]==1) n--;
n++;
}
for(int i=1;i<=n;i++){
if(!(p[i]&1)) continue;
for(int j=1;j<=n;j++){
if((p[j]&1)) continue;
if(!vis[p[i]+p[j]]) {
add(i,j);
}
}
}
int ret=0;
for(int i=1;i<=n;i++){
if(hungry(i,i)) ret++;
}
cout<<(n-ret);
}
AC Record on Virtual Judge | Codeforces Gym AC 记录 ID:\(188853866\)