题意

有一个无限长的01序列，其中n个位置上是1，其余都是0。每次可以选择一个长度为奇素数的区间，然后将这个区间内的元素取反。问最少多少步后可以将整个序列变为0。 n<=100,ai<=10^7

分析

首先差分一下，不难发现1的个数一定是偶数，那么操作就变成了每次可以把两个位置[l-1,r]同时取反。 现在问题就变成了让这偶数个1两两配对，使得总操作数最小。 对于两个数x和y 若|x-y|是奇素数，则需要一步操作。 若|x-y|是偶数，根据哥德巴赫猜想可知需要两步操作。 若|x-y|是奇合数，则可以先减掉一个3，然后就变成了偶数的情况，总共需要三步。 贪心地想肯定是步数越少的配对越多越好。 可以把位置按照下标奇偶性建二分图，然后跑匈牙利，最后不行的话再强行补后两种情况即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=205; const int inf=10000001; int n,prime[inf+5],match[N],a[N],b[N],a1,b1,tot; bool s[inf+5],not_prime[inf+5],vis[N],ma[N][N]; void get_prime(int n) { not_prime[1]=1; for (int i=2;i<=n;i++) { if (!not_prime[i]) prime[++tot]=i; for (int j=1;j<=tot&&i*prime[j]<=n;j++) { not_prime[i*prime[j]]=1; if (i%prime[j]==0) break; } } } bool find(int x) { for (int i=1;i<=b1;i++) if (ma[x][i]&&!vis[i]) { vis[i]=1; if (!match[i]||find(match[i])) { match[i]=x; return 1; } } return 0; } int main() { get_prime(inf); scanf("%d",&n); for (int i=1;i<=n;i++) { int x;scanf("%d",&x); s[x]=1; } for (int i=1;i<=inf;i++) if (s[i]!=s[i-1]) { if (i&1) a[++a1]=i; else b[++b1]=i; } for (int i=1;i<=a1;i++) for (int j=1;j<=b1;j++) if (!not_prime[abs(a[i]-b[j])]) ma[i][j]=1; int ans=0,tmp=0; for (int i=1;i<=a1;i++) { memset(vis,0,sizeof(vis)); if (find(i)) tmp++,ans++; } ans+=(a1-tmp)/2*2+(b1-tmp)/2*2; if (a1%2!=tmp%2) ans+=3; printf("%d",ans); return 0; }