Problem B: 故障电灯(light)

• 考虑对电灯进行差分：若第i个电灯和第i + 1个电灯状态不同，则在第i个位置上放一个球
  
  这样我们就放置了不超过2n个球，且必然是偶数个
  
  于是问题转化为：有m个球，每一步可以把一个球平移奇质数个位置，两个球位于相同位置则同时被消除，计算至
  
  少多少步能消除所有球
• 然后我们发现， 假如两个东西距离为奇质数cost为1， 偶数cost为二（哥德巴赫猜想）， 其余奇数的话cost为3
• 然后发现一种贪心方法， 是尽量匹配cost为1的， 然后分奇偶性各自用2覆盖，看看最后剩下的那个直接判断即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define mmp make_pair

#define M

using namespace std;

int read() {

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

struct Edge{

    int v, c, nxt;

}e[200010];

int head[10010], tot = 1;

void build(int u, int v, int c)

{

    e[++tot] = (Edge){v, c, head[u]};

    head[u] = tot;

    return ;

}

void insert(int u, int v, int c)

{

    build(u, v, c);

    build(v, u, 0);

    return ;

}

int dep[10010];

int S, T;

queue<int> q;

bool bfs()

{

    memset(dep, 0, sizeof(dep));

    dep[S] = 1;

    q.push(S);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        for(int i = head[u]; i; i = e[i].nxt)

            if(!dep[e[i].v]&&e[i].c)

            {

                dep[e[i].v] = dep[u] + 1;

                q.push(e[i].v);

            }

    }

    if(dep[T])return true;

    return false;

}

int cur[10010];

int dfs(int u, int flow)

{

    if(u == T)return flow;

    for(int &i = cur[u]; i; i = e[i].nxt)

        if(e[i].c&&dep[e[i].v] == dep[u] + 1)

        {

            int d = dfs(e[i].v, min(e[i].c, flow));

            if(d){

                e[i].c -= d;

                e[i^1].c += d;

                return d;

            }

        }

    return 0;

}

int dinic()

{

    int ans = 0;

    while(bfs())

    {

        for(int i = S; i <= T; i++)

            cur[i] = head[i];

        int d;

        while(d = dfs(S, 1e9))ans += d;

    }

    return ans;

}

int prime[1000010], cnt;

bool vis[10000010];

int x[1010];

int posx[1010], posy[1010];

int cnt1, cnt2;

void push(int x)

{

    if(x&1)posx[++cnt1] = x;

    else posy[++cnt2] = x;

}

int main(){

    int N = 10000000;

    vis[1] = true;

    for(int i = 2; i <= N; i++)

    {

        if(!vis[i])prime[++cnt] = i;

        for(int j = 1; j <= cnt&&i * prime[j] <= N; j++)

        {

            vis[i * prime[j]] = true;

            if(i%prime[j] == 0)break;

        }

    }

    vis[2] = true;

    int t = read();

    while(t--)

    {

        memset(head, 0, sizeof(head));

        cnt1 = cnt2 = 0; tot = 1;

        int n = read();

        for(int i = 1; i <= n; i++)

        {

			x[i] = read();

            if(i == 1||x[i - 1] != x[i] - 1)push(x[i]);

            if(i> 1&&x[i - 1] != x[i] - 1)push(x[i - 1] + 1);

        }

        push(x[n] + 1);

        S = 0, T = cnt1 + cnt2 + 1;

        for(int i = 1; i <= cnt1; i++)

            insert(S, i, 1);

        for(int i = 1; i <= cnt1; i++)

            for(int j = 1; j <= cnt2; j++)

                if(!vis[max(posx[i] - posy[j], posy[j] - posx[i])])

                    insert(i, cnt1 + j, 1);

        for(int i = 1; i <= cnt2; i++)

            insert(cnt1 + i, T, 1);

        int ans = dinic();

        printf("%d\n", ans + (cnt1 - ans)/2 * 2 + (cnt2 - ans)/2 * 2 + (cnt1 - ans)%2 * 3);

    }

    return 0;

}