[图论记录]AT2689 [ARC080D] Prime Flip
command_block
2021-05-09 15:30:00
**题意** ：有无限枚硬币，其中有 $n$ 枚硬币 $x_{1\ldots n}$ 初始时正面朝上，其余均为背面朝上。
每次可以选择一段区间 $[l,r]$ ，将区间内所有硬币翻转，其中 $r-l+1$ 为奇质数。
问最少多少次操作能使得所有硬币全部为背面朝上。可以证明一定有解。
$n\leq 100,x\leq 10^7$ ，时限$\texttt{2s}$。
------------
先将原序列差分，问题变为可以在两个差为奇质数的位置 $\rm xor\ 1$ ，多少次能使得整个序列变为全 $0$。
考虑将 $1$ 成对解决。对于两个位置 $x,y$ :
- 若 $|x-y|$ 为奇质数 ： $1$ 次操作。
- 若 $|x-y|$ 为偶数 ： 由哥德巴赫猜想，$2$ 次操作。
- 若 $|x-y|$ 为奇合数 ： 先随便整一个质数，然后转化为偶数的情况，$3$ 次操作。
（不难发现 $1$ 有偶数个，故一定有解）
于是，问题就被转化为了特殊的一般图最大权匹配。
由于权值的特殊性，可以贪心。
先尽量添加价值为 $1$ 的匹配，这似乎也是一个一般图最大匹配，不过由于位置的差值是奇（质）数，可以黑白染色变为二分图匹配。
（若拆掉一个价值为 $1$ 的匹配，利用剩余的 $2,3$ 边只会得到更劣的方案）
将被匹配掉的点取出。剩余的图中，也可以贪心地添加价值为 $2$ 的匹配。
将所有点按照奇偶性分为两部分，每一部分内部都充满了 $2$ 边，尽量配对即可。
使用 Dinic 求解二分图匹配，复杂度 $O(n^{2.5}+x)$。
```cpp
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define INF 1000000000
#define MaxS 10005000
#define Maxn 205
using namespace std;
struct Line{int t,cap,b;};
vector<Line> g[Maxn];
void adl(int f,int t,int cap){
g[f].pb((Line){t,cap,g[t].size()});
g[t].pb((Line){f,0,g[f].size()-1});
}
int S,T,dis[Maxn],cur[Maxn];
bool bfs()
{
static queue<int> q;
for (int i=1;i<=T;i++){cur[i]=dis[i]=0;}
q.push(S);dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0,v;i<g[u].size();i++)
if (g[u][i].cap&&!dis[v=g[u][i].t]){
dis[v]=dis[u]+1;
if (v==T){
while(!q.empty())q.pop();
return 1;
}
q.push(v);
}
}return dis[T];
}
int dfs(int u,int flow)
{
if (u==T)return flow;
int sum=0;
for (int &i=cur[u],v;i<g[u].size();i++)
if (dis[v=g[u][i].t]==dis[u]+1&&g[u][i].cap){
int sav=dfs(v,min(flow,g[u][i].cap));
if (sav){
g[u][i].cap-=sav;
g[v][g[u][i].b].cap+=sav;
sum+=sav;flow-=sav;
if (!flow)return sum;
}else dis[v]=-1;
}
return sum;
}
bool e[MaxS];
void sieve(int n)
{
e[1]=1;
for (int i=2;i<=n;i+=2)e[i]=1;
for (int i=3;i*i<=n;i++)
for (int j=i*i;j<=n;j+=i+i)
e[j]=1;
}
int n,x[Maxn],tn;
int main()
{
scanf("%d",&n);sieve(10000000);
for (int i=1,xx;i<=n;i++){
scanf("%d",&xx);
x[i*2-1]=xx;x[i*2]=xx+1;
}
for (int i=1;i<=n+n;i++)
if (x[i]==x[i+1])i++;
else x[++tn]=x[i];
S=tn+1;T=tn+2;int c0=0,c1=0;
for (int i=1;i<=tn;i++){
if (x[i]&1){adl(S,i,1);c1++;}
else {adl(i,T,1);c0++;}
for (int j=i+1;j<=tn;j++)
if (!e[x[j]-x[i]])
if (x[i]&1)adl(i,j,1);
else adl(j,i,1);
}
int ans=0;
while(bfs())ans+=dfs(S,INF);
c0-=ans;c1-=ans;
printf("%d",ans+c0/2*2+c1/2*2+(c0&1)*3);
return 0;
}
```