题目大意

你现在有一个无限长的数组 每个数组的取值为 0 或 1。初始有 $n$ 个地方的位置是 $1$ 。你每次可以将长度为奇数的连续段翻转 求至少翻转几次可以全部变成 0。

$n \leq 100,x \leq 10^7$

题解

Atcoder 的题还是好啊。。就是我都不会

首先我们看到区间操作+大值域 第一时间应该想到的是将其差分后转化成单调操作。转化后原本对 $[l,r]$ 的操作现在就变成了修改 $l$ 和 $r+1$ 位置的数了。

我们现在如果想修改两个位置 $x,y$ 我们来找一下有什么好的性质：

1. $|x-y|$ 为质数 那么答案为 $1$。
2. $|x-y|$ 为偶合数 那么答案为 $2$。（根据哥德巴赫猜想拆分成两个质数 中间正好重叠一块状态不变）
3. $|x-y|$ 为奇合数 那么答案为 $3$。（只能拆分成偶数-质数的形式了）

发现所有的情况都被最优地讨论到了。

我们肯定想尽量让 $1$ 操作多。于是我们按照套路把奇数放在左边 偶数放在右边 差是质数的连边 跑一个二分图最大匹配。

那么剩下的数 首先先用 $2$ 解决（相同奇偶性剩下的点两两配对），如果还有多余的就凑个 $3$ 好了。

Code：

const int MAXN = 1e5 + 5;
const int MAXM = 1e7+5;

namespace Flow{
    struct Edge{
        int to,w,nxt;
    }e[MAXN<<1];
    int head[MAXN],cur[MAXN],cnt=1;
    int dep[MAXN];
    int S,T,N;

    inline void add(int u,int v,int w){
        e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
        e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
    }

    inline bool bfs(){
        FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
        std::queue<int> q;q.push(S);dep[S] = 1;
        while(!q.empty()){
            int v = q.front();q.pop();
            for(int i = head[v];i;i = e[i].nxt){
                if(e[i].w > 0 && !dep[e[i].to]){
                    dep[e[i].to] = dep[v] + 1;
                    if(e[i].to == T) return true;
                    q.push(e[i].to);
                }
            }
        }
        return dep[T];
    }

    inline int dfs(int v,int flow=1e9){
        if(v == T) return flow;
        if(!flow) return 0;
        int ans = 0;
        for(int &i = cur[v];i;i = e[i].nxt){
            if(e[i].w > 0 && dep[e[i].to] == dep[v] + 1){
                int t = dfs(e[i].to,std::min(flow,e[i].w));
                if(t>0){
                    ans += t;flow -= t;
                    e[i].w -= t;e[i^1].w += t;
                    if(!flow) break;
                }
            }
        }
        return ans;
    }

    inline int Dinic(){
        int ans = 0,t = 0;
        while(bfs()) while((t=dfs(S))) ans += t;
        return ans;
    }
};
using namespace Flow;

inline bool isprime(int x){
    if(x == 1) return 0;
    int q = std::sqrt(1.0*x);
    FOR(i,2,q){
        if(!(x%i)) return 0;
    }
    return 1;
}
std::vector<int> s,t;
int a[MAXM];

int main(){
    int n;scanf("%d",&n);
    FOR(i,1,n){
        int x;scanf("%d",&x);a[x] = 1;
    }
    FOR(i,1,MAXM-1){
        if(a[i]^a[i-1]){
            if(i&1) s.pb(i);
            else t.pb(i);
        }
    }
    N = s.size()+t.size();S = ++N;T = ++N;
    FOR(i,0,(int)s.size()-1) add(S,i+1,1);
    FOR(i,0,(int)t.size()-1) add(s.size()+i+1,T,1);
    FOR(i,0,(int)s.size()-1){
        FOR(j,0,(int)t.size()-1){
            if(isprime(std::abs(s[i]-t[j]))){
                add(i+1,j+s.size()+1,1);
            }
        }
    }
    int ans = Dinic();
    printf("%d\n",ans+(((int)s.size()-ans)/2)*2+(((int)t.size()-ans)/2)*2+3*(((int)s.size()-ans)&1));
    return 0;
}