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

时间:2021-07-05 15:25:00

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≤1071≤x1≤x2≤...≤xN≤107

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);
}