题意：有一个无限序列，其中有(n)个位置上的数为(1)，其余都是(0)。你可以进行若干次操作，每次选取序列上的一个区间([l,r))，满足(r-l)为奇质数，将在这个区间上的数都异或上(1)。问最少进行多少次操作，使得序列上所有数都变为(0)。
(n leq 100)
这类自己决定操作来让数列变为全零的问题，在atcoder上是挺常见的。
一般对于这种问题，要用差分或类似的操作，来让区间修改变为单点修改。例如，对于区间加的操作，就用差分将其变为两个单点加。至于这个问题，我们设原序列为数列({a})，则构建数列({b})满足(b_n=a_{n-1} \,{ m xor} \,a_n)。这样，题目中的([l,r))区间异或(1)就变成了将(b_l)和(b_r)都异或上(1)。
接下来，我们考虑操作可以被分为几个部分，每一个部分就是把两个为(1)的元素变为(0)，其余元素均不改变状态。于是，问题就变成了对({b})中为(1)的元素进行匹配。（可以发现，为(1)的元素的总数为偶数）
我们考虑两个位置的距离为(d)的元素，将他们都变为(0)，需要多少次操作。这等价于把(d)表示为最少数量的质数的和或差。
- (d)为奇质数。那么，显然一次操作就可以了。
- (d)为偶数。首先，从奇偶性上看，只用一次操作是不可能的。故至少需要两次操作。考虑(d=2)时，可以由(2=5-3)两次操作完成（存在位置离其中一个元素为(5)，另一个为(3)）。而若(d geq 4)，由于哥德巴赫猜想在本题数据范围内是成立的，故一定能表示为两个质数的和，即可以用两次操作实现。
- (d)为奇合数。显然一次操作或两次操作都是不可能的。而(d)加上一个奇质数后是一个偶数，故也最多需要三次操作。
剩下的就是匹配的问题了。这里不能拆点做二分图带权最大匹配，很容易能举出反例。但是，我们可以用贪心来把所有元素分为两组。（此处瞄了题解）设(k)为所有匹配中(d)为奇质数的组数。那么，显然是(k)组奇数位置和偶数位置匹配。设奇数的位置上有(n_1)个元素，偶数的位置上有(n_2)个元素。那么，显然要让奇偶性相同的元素匹配到一起，操作总数最小。于是，我们可以得出，总操作数为$$k+2 imes (lfloor frac {n_0-k} {2} floor+lfloor frac {n_1-k} {2} floor) + 3 imes ((n_0 - k) mod 2)$$
由于元素总数为偶数，(n_0)和(n_1)同奇偶，我们分奇偶讨论一下就能得到对于所有合法的(k)和(k+1)，(f(k+1) leq f(k))。因此，我们只要最大化(k)就可以了。我们根据奇偶性对元素分组，然后做二分图最大匹配就可以了。
时间复杂度(O(n^2 + m))。(m)为权值大小。
#include <bits/stdc++.h>
using namespace std;
const int N = 610, INF = 0x3f3f3f3f;
int p[N],n,cnt,st,en,x[N];
struct edge {
int la,b,cap;
} con[N * N * 2];
int tot=1,fir[N];
void add(int from,int to,int capc) {
con[++tot] = (edge) {fir[from],to,capc};
fir[from] = tot;
con[++tot] = (edge) {fir[to],from,0};
fir[to] = tot;
}
int cur[N], dis[N];
int dfs(int pos,int imp) {
if (pos == en || (!imp)) return imp;
int expo = 0, tmp;
for (int &i = cur[pos] ; i ; i = con[i].la) {
if (dis[con[i].b] == dis[pos] + 1) {
tmp = dfs(con[i].b,min(imp,con[i].cap));
con[i].cap -= tmp;
con[i^1].cap += tmp;
expo += tmp;
imp -= tmp;
if (!imp) break;
}
}
return expo;
}
bool bfs() {
static queue<int> q;
while (!q.empty()) q.pop();
memset(dis,0,sizeof dis);
for (int i = 1 ; i <= n ; ++ i)
cur[i] = fir[i];
dis[st] = 1;
q.push(st);
for (int pos ; !q.empty() ; q.pop()) {
pos = q.front();
for (int i = fir[pos] ; i ; i = con[i].la) {
if (con[i].cap && (!dis[con[i].b])) {
dis[con[i].b] = dis[pos] + 1;
q.push(con[i].b);
}
}
}
if (!dis[en]) return 0;
return 1;
}
const int MAX = 10000010;
int isp[MAX + 10], pri[MAX / 10], pcnt, num[2];
set<int> prime;
void prework() {
for (int i = 2 ; i <= MAX ; ++ i) {
if (!isp[i]) pri[++pcnt] = i;
for (int j = 1 ; j <= pcnt && pri[j] * i <= MAX ; ++ j) {
isp[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
for (int i = 2 ; i <= pcnt ; ++ i)
prime.insert(pri[i]);
}
int main() {
prework();
scanf("%d",&n);
for (int i = 1 ; i <= n ; ++ i) {
scanf("%d",&x[i]);
if (x[i] == 1 || x[i] != x[i-1] + 1)
p[++cnt] = x[i];
if (i > 1 && x[i] != x[i-1] + 1)
p[++cnt] = x[i-1] + 1;
}
p[++cnt] = x[n] + 1;
n = cnt;
st = ++n;
en = ++n;
for (int i = 1 ; i <= cnt ; ++ i) {
++ num[p[i]&1];
if (p[i]&1) {
add(st,i,1);
for (int j = 1 ; j <= cnt ; ++ j) {
int d = abs(p[i] - p[j]);
if (prime.count(d))
add(i,j,1);
}
} else add(i,en,1);
}
int ans = 0;
while (bfs())
ans += dfs(st,INF);
printf("%d
",ans + 2 * ((num[0] - ans) / 2 + (num[1] - ans) / 2) + ((num[1] - ans)&1) * 3);
return 0;
}
小结：又看了一道思维题的题解……感觉表算高妙的同时，自己还深有不足。