[Arc080F]Prime Flip
Description
你有无限多的“给给全”,编号为1,2,3,...。开始时,第x1,x2,...,xN个“给给全”是躺着的,其它的“给给全”是趴着的 你可以进行一些操作,每个操作大概是这样的: 选择一个不小于3的质数p,然后将连续的p个“给给全”翻过来 你希望让所有“给给全”趴下。请计算完成这一任务所需的最少操作次数
Input
第一行一个正整数N
第二行N个正整数,第i个数表示xi
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
样例一可以先选择5,并翻转1,2,3,4,5。然后选择3,并翻转1,2,3
\(1\leq N \leq 100\)
\(1\leq x_1\leq x_2\leq ... \leq x_N\leq 10^7\)
试题分析
首先遇到这种翻转的问题,进行差分,因为这样可以把一段区间的操作看成简单的翻转\(i\)和\(i+p\)个状态的操作。
那么我们希望用最小的步骤使其最优,要怎么办呢?
首先列一个表出来,可以得出结论:1格需要翻转3遍,奇质数需要翻转1遍,偶数需要翻转2遍,奇合数需要翻转3遍。
其中结论1为手推,结论2为题目标准操作,结论3是哥德巴赫猜想,结论4是奇合数可以通过减去一个奇质数得到偶数长度。
于是我们就希望尽量先选翻转1遍的奇质数情况,一定是一奇一偶配对,使其配对数最大。
那么到这里做法就很显然了,直接二分图匹配,然后剩下的单算,注意最后剩1格的情况。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 2147483600;
const int MAXN = 10000010;
bool vis[MAXN+1];int pri[MAXN+1],cnt;
int flo[MAXN+1]; int N;
int sta[2][20010],top[2];
int Next[20010],Node[20010],Root[20010];
inline void init(){
vis[1]=true;
for(int i=2;i<=MAXN;i++){
if(!vis[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i*1LL<=MAXN;j++){
vis[i*pri[j]]=true; if(i%pri[j]==0) break;
}
} return ;
}
int fa[200010];
inline bool dfs(int k){
for(int x=Root[k];x;x=Next[x]){
int v=Node[x];
if(!vis[v]){
vis[v]=true;
if(fa[v]==-1||dfs(fa[v])){
fa[v]=k; return true;
}
}
} return false;
}
inline void insert(int u,int v){
Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt; return ;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
for(int i=0;i<=MAXN;i++) flo[i]=1; N=read();
for(int i=1;i<=N;i++){
int x=read(); flo[x]=0;
} init(); for(int i=MAXN;i>=1;i--) {
flo[i]=flo[i]-flo[i-1];
if(flo[i]){
sta[i&1][++top[i&1]]=i;
}
}
for(int i=1;i<=top[0];i++){
for(int j=1;j<=top[1];j++){
if(!vis[abs(sta[0][i]-sta[1][j])]){
insert(i,j+top[0]);
//insert(j+top[0],i);
}
}
} int ans=0;
memset(fa,-1,sizeof(fa));
for(int i=1;i<=top[0];i++){
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
printf("%d\n",ans+(top[0]-ans)/2*2+(top[1]-ans)/2*2+((top[0]-ans)&1)*3LL);
return 0;
}