[建模] [二分图] [贪心] [ARC080F] Prime Flip | noip模拟赛 疯癫兄弟

· · 题解

注：当初 noip 模拟赛的题，赛后听完评讲觉得挺好，遂记之。恰好夏令营时 lby 学长讲到了这道题，所以翻出来水一发题解回顾一下。

巧妙的建模，还需结合贪心。

思路

首先用 0/1 表示状态，那么每次操作等价于给区间异或 1，可以考虑差分在首尾打上标记。这样就将区间操作转化为对数对操作。

既然考虑了差分，那么不妨把输入也看成差分操作，即 f_{x_i} \bigoplus1,f_{x_{i+1}} \bigoplus1。

注意到对 0 端点操作一定不优，那么首先对操作数对的距离进行讨论。

  1. 为奇质数：花费 1。
  2. 为偶数：由哥德巴赫猜想知可拆为两个奇质数操作，花费 2。
  3. 为非质奇数：花费 3。

（注意保证有解）

然后可以由奇偶性建二分图，显然有个贪心，先进行操作 1，然后是操作 2，最后实在不行再用操作 3。

因此可以按如下步骤操作：

  1. 优先连奇质数边，即跑一边二分图最大匹配。
  2. 剩下的未匹配点内部连偶数边。
  3. 显然左右部都至多剩下 1 个点，对它们连非质奇数边即可。

怎么严谨证明呢？我们设 A,B,x 分别为二分图左右部顶点数，以及操作 1 的个数（即匹配边数量）。

令 G(x) 表示此时花费，有 G(x)=x+2\lfloor \frac {A-x}2 \rfloor+2\lfloor \frac {B-x}2\rfloor+3((A-x)\bmod 2) 。

然后对 x 分奇偶讨论，容易发现 G(x) 是单调的，所以取 x 最大值即可。

时间开销最大的是二分图最大匹配部分，当初考场的毒瘤出题人卡了匈牙利算法，所以用的是 \rm dinic。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5, M = 1e6 + 2e3 + 5, C = 1e7, inf = 1e9; 
int k, n, x, a[N], s, t, L, R;
int head[N], now[N], tot = 1;
int dep[N], ans;
bool yfz[C + 5];
struct edge{int v, nxt, w;}e[M << 1];

inline void add(int u, int v, int w) {e[++tot] = {v, head[u], w}, head[u] = tot;}
inline bool bfs(){
    for(int i = s; i <= t;++i) dep[i] = inf, now[i] = head[i];
    queue<int>q;
    q.push(s), dep[s] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u], v; v = e[i].v, i; i = e[i].nxt)
            if(e[i].w && dep[v] == inf){
                dep[v] = dep[u] + 1;
                q.push(v);
                if(v == t) return true;
            }
    }
    return false;
}
inline int dfs(int u, int sum){
    if(u == t) return sum;
    int k, res = 0;
    for(int i = now[u], v; v = e[i].v, i && sum; now[u] = i, i = e[i].nxt)
        if(e[i].w && dep[u] + 1 == dep[v]){
            k = dfs(v, min(sum, e[i].w));
            if(!k) dep[v] = inf;
            e[i].w -= k, e[i ^ 1].w += k;
            sum -= k, res += k;
        }
    return res; 
}
inline bool check(int p){
    if(p <= 2 || p % 2 == 0) return false;
    for(int i = 2; i * i <= p;++i)
        if(p % i == 0) return false;
    return true;
}
inline void build(){
    cin >> k;
    for(int i = 1; i <= k; ++i) scanf("%d", &x), yfz[x] ^= 1, yfz[x + 1] ^= 1;
    for(int i = 0; i <= C + 1; ++i) if(yfz[i]) a[++n] = i;
    s = 0, t = n + 1;
    for(int i = 1; i <= n; ++i){
        if(a[i] & 1) add(s, i, 1), add(i, s, 0), ++L;
        else add(i, t, 1), add(t, i, 0), ++R;
        for(int j = i + 1; j <= n; ++j)
            if(check(a[j] - a[i]))
                if(a[i] & 1) add(i, j, 1), add(j, i, 0);
                else add(j, i, 1), add(i, j, 0);
    }
}
inline void solve(){
    while(bfs()) ans += dfs(s, inf); 
    int pipei = ans;
    ans += (L - pipei) / 2 * 2 + (R - pipei) / 2 * 2;
    if((L - pipei) & 1) ans += 3;
}
signed main(){
    build();
    solve();
    cout << ans;
    return 0;
}