【ARC080F】Prime Flip 差分+二分图匹配

Description

有无穷个硬币，初始有n个正面向上，其余均正面向下。你每次可以选择一个奇质数p，并将连续p个硬币都翻转。问最小操作次数使得所有硬币均正面向下。

Input

第一行一个正整数NN

第二行NN个正整数，第ii个数表示xixi

Output

一个整数表示最小操作步数

Sample Input

Sample #1

2

4 5

Sample #2

9

1 2 3 4 5 6 7 8 9

Sample #3

2

1 10000000

Sample Output

Sample #1

2

Sample #2

3

Sample #3

4

HINT

样例一可以先选择55，并翻转1,2,3,4,51,2,3,4,5。然后选择33，并翻转1,2,31,2,3

1≤N≤1001≤N≤100

1≤x1≤x2≤...≤xN≤10^{71≤x1≤x2≤...≤xN≤10}7

Sol

很妙啊。

首先我们发现，如果将这个区间差分，即\(if(s[i]!s[i-1])c[i]=1;\)

然后就可以转化成每次选择两个点并且进行翻转啦（差分边界1-n+1）。

我们发现如果区间长度是俩奇质数就只要一次，偶数要两次（哥德巴赫猜想），非质数奇数要三次（分解成一个质数和一个偶数，1显然也是3次），我们先二分图匹配奇质数，剩下的匹配差为偶数，如果还剩俩就再+3即可。

Code

#include <bits/stdc++.h>

using namespace std;

int n,x,pri[10000005],np[10000005],s[10000005],cnt1,cnt2,a[105],b[105],vis[205],mch[205],tot,ans;vector<int>e[105];

bool dfs(int x)

{

    for(int i=0;i<e[x].size();i++) if(!vis[e[x][i]])

    {

        vis[e[x][i]]=1;

        if(!mch[e[x][i]]||dfs(mch[e[x][i]])){mch[e[x][i]]=x;return 1;}

    }

    return 0;

}

int main()

{

    for(int i=2;i<=1e7;i++)

    {

        if(!np[i]) pri[++tot]=i;

        for(int j=1;j<=tot&&i*pri[j]<=1e7;j++){np[i*pri[j]]=1;if(i%pri[j]==0) break;}

    }

    scanf("%d",&n);np[1]=1;

    for(int i=1;i<=n;i++) scanf("%d",&x),s[x]=1;

    for(int i=1;i<=10000001;i++) if(s[i]!=s[i-1]) (i&1)?a[++cnt1]=i:b[++cnt2]=i;

    for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2;j++) if(!np[abs(a[i]-b[j])]) e[i].push_back(j);

    for(int i=1;i<=cnt1;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i);

    printf("%d\n",ans+(cnt1-ans)/2*2+(cnt2-ans)/2*2+((cnt1-ans)&1)*3);

}

秒客网