题解 AT2689 【[ARC080D] Prime Flip】

whiteqwq · 2020-11-20 16:40:47 · 题解

AT2689 [ARC080D] Prime Flip解题报告：

更好的阅读体验

题意

• 无限枚硬币，有n枚硬币a_1\cdots a_n正面朝上，其他的都是背面朝上；
• 可以进行若干次区间翻转操作，满足区间长度为一个奇质数；
• 求最少进行多少次操作让所有硬币背面朝上。

分析

神仙题，调了一下午/kk。

首先有一个套路的想法，设b_i为第i个硬币是否与第i+1个硬币不同，这样我们的区间反转操作[l,r]会变为b_{l-1}和b_r反转，我们的目标会变为让所有的b_i变为0。

然后，我们可以很简单的求出来所有b_i为1的位置，然后题目便转化为了如何用最少的操作让这些b_i全部为0。

考虑抵消b_i和b_j（b_i\geqslant b_j）的条件：

• • 若b_i-b_j=2，那么可以进行2次操作：[b_i,b_{i+5}],[b_{i+2,b_{i+5}}]；
• • 若b_i-b_j>2，那么根据哥徳巴赫猜想，我们一定可以把这个偶数分成两个奇素数，那么就只需要2次操作；
• • 因为一次不能对两个差为偶数的数进行操作，所以2次操作为操作数量最小值。
• • 若b_i-b_j=1，那么可以进行3次操作：[b_i,b_{i+7}],[b_{i+4},b_{i+7}],[b_{i+1},b_{i+4}]，这样就进行了消除。
• • 若b_i-b_j=3，那么可以进行3次操作：[b_i,b_{i+11}],[b_{i+8},b_{i+11}],[b_{i+3},b_{i+8}]，同样可以进行消除。
• • 若b_i-b_j>3，那么可以进行一次操作[b_i,b_{i+3}]把b_i的1转移到b_{i+3}上，然后进行偶数的操作，一共3步。
• • 因为一次不能消掉，两次只能消掉偶数，所以至少需要3步，即3步为最优解。

对于知道了上面的结论后，我们有一个贪心的想法：尽量多的消除b_i-b_j为奇素数的情况，然后尽量多的消除b_i-b_j为偶数的情况，其他的进行第三种情况，这个贪心策略显然是正确的。

考虑把所有差为奇素数的数连边，这样这个新图一定是一个二分图，原因是奇数只会和偶数连边，而且很显然这个新图的最大匹配为第一种情况的最多情况。

消除完所有能进行操作1的情况后，剩下来可以进行操作2的两个数一定奇偶性相同，这样我们分奇偶消除一下就好了。

最后有可能剩下两个奇偶性不相同的数（原因是n为偶数，如果剩下两个奇偶性相同的一定可以继续消除，所以要么一个不剩，要么剩两个奇偶性不同的数），这一对数我们运用操作3消除就好了。

代码

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int maxn=205,maxk=10000005,maxm=maxn*maxn;
int n,stp,cnt,fir,e,ans,vs;
int start[maxn],to[maxm],then[maxm],match[maxn],vis[maxn],a[maxk],p[maxk],flg[maxn],x[maxn],tot[2];
vector<int>v;
inline int abs(int x){
    return x<0? -x:x;
}
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int Hungary(int x){
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y]==stp)
            continue;
        vis[y]=stp;
        if(match[y]==-1||Hungary(match[y])){
            match[y]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    memset(match,-1,sizeof(match));
    for(int i=2;i<maxk;i++){
        if(p[i]==0)
            a[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            if(i*a[j]>=maxk)
                break;
            p[i*a[j]]=1;
            if(i%a[j]==0)
                break;
        }
    }
    p[0]=p[1]=p[2]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    v.push_back(x[1]-1);
    for(int i=1;i<n;i++)
        if(x[i]+1<x[i+1])
            v.push_back(x[i]),v.push_back(x[i+1]-1);
    v.push_back(x[n]),vs=v.size();
    for(int i=0;i<vs;i++)
        for(int j=0;j<vs;j++)
            if(v[i]%2==0&&p[abs(v[i]-v[j])]==0)
                add(i,j);
    for(int i=0;i<vs;i++){
        if(v[i]%2==0)
            stp++,fir+=Hungary(i);
        tot[v[i]%2]++;
    }
    ans=fir+((tot[1]-fir)/2+(tot[0]-fir)/2)*2;
    if((tot[0]-fir)%2==1)
        ans+=3;
    printf("%d\n",ans);
    return 0;
}