题解 AT2689 【[ARC080D] Prime Flip】

这种区间反转的题，套路就是差分。 设 $a_i$ 表示第 $i$ 枚硬币是否正面朝上，显然只有 $a_{x_1},a_{x_2},\cdots,a_{x_n}$ 等于 $1$，其他都是 $0$。那么我们的目标是把 $a$ 数组全部变成 $0$。 设 $b_i$ 表示第 $i$ 枚硬币和第 $i-1$ 枚硬币是否不同，即 $b_i=a_i\operatorname{xor} a_{i-1}$。那么我们的目标就变成了把 $b$ 数组全部变成 $0$，即让每个数都相同。 设 $\textit{prime}$ 为所有**奇数质数**的集合，$p\in \textit{prime}$，那么一次反转可以看做将 $a_i\sim a_{i+p-1}$ 全部取反。 发现将 $a_i\sim a_{i+p-1}$ 取反后其实等价于 $b_i$ 和 $b_{i+p}$ 两个数取反。 所以现在操作就变成了：任意选择两个正整数 $i,j$，且满足 $j-i\in\textit{prime}$，然后将 $b_i$ 和 $b_j$ 取反。 然后在所有值为枚举满足 $b_i=b_j=1$ 的任意一对 $i,j$（$i<j$），考虑如何操作才能将 $b_i$ 和 $b_j$ 都变为 $0$ 且操作数最少，分情况讨论： 1. $j-i\in\textit{prime}$。此时我们可以直接将 $b_i$ 和 $b_j$ 变为 $0$，共 $1$ 次操作。 1. $j-i$ 为正偶数。 那么当 $j-i=2$ 时，我们可以对 $b_i$、$b_{i+5}$ 取反，然后再对 $b_{i+2}$、$b_{i+5}$ 取反，共 $2$ 次操作； 当 $j-i=4$ 时，我们可以对 $b_i$、$b_{i+7}$ 取反，然后再对 $b_{i+4}$、$b_{i+7}$ 取反，共 $2$ 次操作； 当 $j-i$ 为其他正偶数时，由哥德巴赫猜想在 $10^7$ 范围内的正确性，可知 $j-i$ 可以分为两个奇质数的和。即存在 $p_1+p_2=j-i$，且 $p_1,p_2\in\textit{prime}$。那么我们可以对 $b_i$、$b_{i+p_1}$ 取反，然后再对 $b_{i+p_1}$、$b_{i+p_1+p_2}$ 取反，共 $2$ 次操作。 综述，当 $j-i$ 为正偶数时，最小的操作数都是 $2$ 次。$(2)$ 1. $j-i$ 为除 $\textit{prime}$ 以外的正奇数。 当 $j-i=1$ 时，我们可以对 $b_i$、$b_{i+7}$ 取反，然后对 $b_{i+4}$、$b_{i+7}$ 取反，对 $b_{i+1}$、$b_{i+4}$ 取反，共 $3$ 次操作。 类似地，可知当 $j-i=3$ 时，也存在一种方案且最小操作数为 $3$。 当 $j-i$ 为其他正奇数时，即 $j-i>3$ 且 $j-i$ 为奇数时，我们可以将 $j-i$ 分解成 “$3+\text{正偶数}$” 的形式，然后再由 $(2)$ 得此时最少的操作数为 $3$ 次。 综述，当 $j-i$ 为除 $\textit{prime}$ 以外的正奇数时，最小的操作数都是 $3$ 次。 所以为了使得操作数最少，我们应该优先使用第 $1$ 种情况。 设有 $k$ 个 $b_i=1$，并且将他们的下标用集合 $S=\{c_1,c_2,\cdots,c_k\}$ 表示。 那么 $k$ 肯定是偶数，因为考虑将 $a_i$ 中连续的 $1$ 当做一个块。那么对于每个块 $a_{\textit{head}}\sim a_{\textit{tail}}$，块头贡献一个 $b_{\textit{head}}=1$，块尾贡献一个 $b_{\textit{tail}+1}$，所以总贡献就是偶数个。 发现如果有 $c_i-c_j\in\textit{prime}$，那么 $c_i$ 和 $c_j$ 的奇偶性必定不同。 于是想到将 $c_i$ 奇偶分类，并对于所有的 $c_i-c_j\in\textit{prime}$，连边 $(i,j)$，那么这就是一个二分图的形式。 显然对这个二分图跑最大匹配就是第 $1$ 种情况的最多使用数。 将这些点取反之后，还剩下一些点需要取反，于是考虑使用第 $2$ 种情况。 显然，若 $c_i-c_j$ 为正偶数，那么 $c_i$ 和 $c_j$ 的奇偶性相同。 所以将奇类中剩下的 $c_i$ 进行两两取反，将偶类中剩下的 $c_i$ 进行两两取反。 然后再考虑第 $3$ 种情况，此时奇类和偶类肯定要么都剩下 $0$ 个未取反、要么都剩下 $1$ 个未取反，因为 $k$ 为偶数。然后对于各剩下 $1$ 个未取反的情况下，将他们两个按第 $3$ 种情况处理。 将 $3$ 种情况的总操作数加起来，就是最后的答案了。 代码如下： ```cpp #include<bits/stdc++.h> #define N 110 #define INF 0x7fffffff using namespace std; int n,a[N]; int tot,odd,b[N<<1]; int cnt=1,head[N<<1],cur[N<<1],nxt[N*N*8+N*4],to[N*N*8+N*4],c[N*N*8+N*4]; int s,t,num[N<<1]; queue<int>q; void adde(int u,int v,int ci) { to[++cnt]=v; c[cnt]=ci; nxt[cnt]=head[u]; head[u]=cnt; to[++cnt]=u; c[cnt]=0; nxt[cnt]=head[v]; head[v]=cnt; } bool check(int x)//判断一个数是否属于prime { if(x<=2) return false; if(!(x&1)) return false; for(int i=2,maxn=sqrt(x);i<=maxn;i++) if(!(x%i)) return false; return true; } bool bfs() { memcpy(cur,head,sizeof(cur)); memset(num,-1,sizeof(num)); q.push(s); num[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(c[i]&&num[v]==-1) { num[v]=num[u]+1; q.push(v); } } } return num[t]!=-1; } int dfs(int u,int minflow) { if(u==t||!minflow) return minflow; int preflow=0,nowflow; for(int i=cur[u];i;i=nxt[i]) { cur[u]=i; int v=to[i]; if(num[v]==num[u]+1&&(nowflow=dfs(v,min(c[i],minflow-preflow)))) { preflow+=nowflow; c[i]-=nowflow; c[i^1]+=nowflow; if(!(minflow-preflow)) break; } } return preflow; } int dinic()//用dinic跑最大匹配 { int maxflow=0; while(bfs()) maxflow+=dfs(s,INF); return maxflow; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); b[++tot]=a[1]; for(int i=2;i<=n;i++) { if(a[i]-a[i-1]>1) { b[++tot]=a[i-1]+1;//块尾贡献 b[++tot]=a[i];//块头贡献 } } b[++tot]=a[n]+1; s=1,t=1+tot+1; for(int i=1;i<=tot;i++) { if(b[i]&1) { odd++; adde(s,1+i,1); for(int j=1;j<=tot;j++) if(check(abs(b[i]-b[j]))) adde(1+i,1+j,1); } else adde(1+i,t,1); } int sum1=dinic(); printf("%d\n",sum1+(odd-sum1)/2*2+((tot-odd)-sum1)/2*2+((odd-sum1)&1)*3); return 0; } ```