【AtCoder Regular Contest 080 F】Prime Flip | Mrsrz's blog

二分图匹配，哥德巴赫猜想。

题目大意：

给定一个长度为 $10^7$ 的 01 序列 $a$，有 $n$ 个位置为 1，其余位置为 0。

每次可以将一段长度为奇质数的区间的 0 变成 1，1 变成 0。

问至少操作多少次，才能使这个序列变为全 0。

题解：

我们令 $b_i=a_i\mathrm{\ xor\ }a_{i-1}$，然后对 $a_i$ 的区间反转，就变成了对 $b_i$ 的两个间隔为奇质数的位置进行反转。

由于题目强调了奇质数，所以我们将 1 出现的位置按照奇偶分类。

然后考虑两点的距离，令其为 $d$。

• $d$ 为奇质数。那么我们只需要一次操作就可以让这两个点反转。
• $d$ 为偶数。根据哥德巴赫猜想，当 $d\gt 4$ 时，一定能表示为两个奇质数相加（$10^7$ 以内没有反例）。而 $4=7-3,2=5-3$，所以 $d$ 为偶数时需要 $2$ 次。
• $d$ 为奇合数。根据哥德巴赫猜想，当 $d\geq 9$ 时，一定能表示为三个奇质数的和。所以 $d$ 为奇合数需要 $3$ 次。

我们需要操作次数尽可能少，那么让奇质数距离匹配最多，剩下的偶数距离匹配。最后如果奇数、偶数各剩下一个，则奇合数匹配。

这里不用考虑拿一个奇质数和一个奇合数换两个合数匹配，因为代价是相等的。

奇质数匹配的部分，连边跑二分图最大匹配即可。偶数匹配的部分，对剩余的奇数个数和偶数个数直接计算即可。奇合数匹配部分，看最后是否还有剩余即可。

Code：

#include<iostream>
#include<cstdlib>
#include<vector>
#include<cstring>
using namespace std;
const int N=205,M=1e7+10;
int n,a[N],pri[M/10],tot,ans;
bool vis[M],b[M],ur[N];
int ld[N],rd[N],cl,cr,even,odd;
int lf[N];
vector<int>G[N];
void sieve(int n){
    vis[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i])pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<=n;++j){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}
bool dfs(int u){
    for(int to:G[u])
    if(!ur[to]){
        ur[to]=1;
        if(!lf[to]||dfs(lf[to])){
            lf[to]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[a[i]]=1;
    }
    for(int i=10000001;i;--i)if(b[i]^=b[i-1]){
        if(i&1)ld[++cl]=i;else rd[++cr]=i;
    }
    sieve(10000000);
    for(int i=1;i<=cl;++i)
    for(int j=1;j<=cr;++j)if(!vis[abs(ld[i]-rd[j])])G[i].push_back(j);
    memset(lf,0,sizeof lf);
    for(int i=1;i<=cl;++i){
        memset(ur,0,sizeof ur);
        ans+=dfs(i);
    }
    memset(ur,0,sizeof ur);
    for(int i=1;i<=cr;++i)ur[lf[i]]=1;
    for(int i=1;i<=cl;++i)if(!ur[i])++odd;
    for(int i=1;i<=cr;++i)if(!lf[i])++even;
    ans+=(odd>>1<<1)+(even>>1<<1)+(odd&1)*3;
    cout<<ans<<'\n';
    return 0;
}