AT2689 [ARC080D] Prime Flip解题报告

解题报告

AT2689 [ARC080D] Prime Flip解题报告：

更好的阅读体验

题意

• 无限枚硬币，有$n$枚硬币$a_1\cdots a_n$正面朝上，其他的都是背面朝上；
• 可以进行若干次区间翻转操作，满足区间长度为一个奇质数；
• 求最少进行多少次操作让所有硬币背面朝上。
• $1\leqslant n\leqslant 100,1\leqslant a_i\leqslant a_{i+1}\leqslant 10^7$，保证$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$为奇素数，那么区间长度也是奇素数，只需要$1$次操作。
• $b_i-b_j$为偶数，那么区间长度为偶数，需要$2$次操作，解释如下：
• • 若$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$非奇素数也非偶数，那么区间长度为奇合数，需要进行$3$次操作，解释如下：
• • 若$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;
}