LibreOJ526. 「LibreOJ β Round #4」子集

简要题意

给出一个长度为 \(n\) 的序列 \(a\)。你需要选出它的一个子集 \(S\)。使其满足对于任意两个元素 \(i,j\)。满足：

输出满足条件的子集大小的最大值。

\(1 \leq n \leq 500,1 \leq a_i \leq 10^{18}\)

思路

这道题比 Codeforces Gym 104059B - Breeding Bugs 更为简单。

首先对于选出一个子集两两满足特定约束的问题，有一个经典思路就是将满足条件转换为不满足条件，然后对于不满足条件的两个点连一条边，答案就是最大独立集。

但是一般图最大独立集是 NPC 问题。考虑发掘这张图的特殊性质。

引理：若 \(i\equiv j\pmod{2}\)，则 \(\gcd(i,j)\cdot\gcd(i+1,j+1)\neq1\)。（但是这个命题的逆命题不成立）。

Proof：若 \(i\equiv j\pmod{2}\)，则 \(\gcd(i,j)\equiv0\pmod{2}\)，所以上式必定不为 \(1\)。得证。

于是我们可以按照奇偶性黑白染色，就可以把原图变成二分图了。

然后用匈牙利即可。

代码

#include<bits/stdc++.h>
#define gcd __gcd
#define int long long
using namespace std;

const int N = 505;
int n;

struct edge{
	int nxt,to;
} g[N*N];
int head[N],ec,a[N],mch[N],vist[N];

void add(int u,int v){
	g[++ec].nxt=head[u];
	g[ec].to=v;head[u]=ec;
}

bool dfs(int u,int tag){
	if(vist[u]==tag) return 0;
	vist[u]=tag;
	for(int i=head[u];i;i=g[i].nxt){
		int v=g[i].to;
		if(!mch[v] || dfs(mch[v],tag)){
			mch[v]=u;
			return 1;
		}
	}
	return 0;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(!(a[i]&1)) continue;
		for(int j=1;j<=n;j++){
			if(a[j]&1) continue;
			if(gcd(a[i],a[j])*gcd(a[i]+1,a[j]+1)==1){
				add(i,j);
			}
		}
	}
	int ans=n;
	for(int i=1;i<=n;i++){
		if(dfs(i,i)) ans--;
	}
	cout<<ans;
	return 0;
}