2023 Hubei Provincial Collegiate Programming Contest
A Prime Magic
Walk Alone has a sequence \(a_1,a_2,...,a_n\), and he can use a magic on it:
- Choose an odd prime number \(p\) and an interval \([l,r]⊆[1,n]\) satisfying \(r−l+1=p\), and then add \(1\) or \(−1\) to every \(a_i\) in this interval. That is, choose \(x∈{1,−1}\), then \(∀i∈[l,r],ai←ai+x\).
Remind that odd prime is numbers that are odd greater than \(1\) and can only be divided by \(1\) and itself.
Walk Alone likes growing things, so he wants to use this magic to make this sequence non-decreasing. Besides, Walk Alone doesn't like negative numbers, so during the whole operations any number cannot be negative.
He wants to accomplish this idea with minimal number of magic usage. Although Walk Alone has this magic, he doesn't know in which order to use it, so he asks you for help.
For each test case, output a single integer in a line denoting the minimum number of magic usage to accomplish the task.
\(1\le T\le100,10\le n\le2e3,1\le a_i\le1e5,\sum n\le2e4\)
中文题意（参考官方题解）
给定一长度为 $n$ 的序列 ${a_n}$，每次可以选取一段长度为奇质数的连续子序列 $[l, r]$ 整体加一或减一，要求操作过程中序列中不得出现负数，问将整个序列转化为非严格递增序列的最少操作次数。Solution
操作可以转化为在差分数组上使一个点加一，同时另一个点减一，这两个点的距离是奇质数这样就转化为了费用流问题，每个正的 \(diff_i\) 可以为一个负的 \(diff_j\) 提供 \(diff_i\) 次操作，最终使差分数组非负
朴素想法是按照 \(diff\) 的正负分类建二分图，连 \(n^2\) 条边。
- 对于距离为奇质数的点对，单位流量费用为 \(1\)
- 对于距离为偶合数的点对，根据哥德巴赫猜想，一定可以表示为两个素数之和，单位流量费用为 \(2\)；特别地，距离为 \(2\) 的点对费用也是 \(2\)
- 对于距离为奇合数的点对，一定可以表示为 \(3+prime_a+prime_b\) 的形式（\(n\ge10\)是为了保证这个有解），单位流量费用为 3
然而边太多了，而且费用流比较慢无法通过此题
观察到费用只有 1，2，3；而且主要是 2 和 3，想办法转化为最大流问题
官方题解提供了一种优化方法：
- 首先对费用为 \(1\) 的边进行匹配
- 费用为 \(2\) 的边：二分图左右部点在 \(1\) 操作后的残量图中直接两两尝试匹配
- 剩下无法匹配的边只能按照费用为 \(3\) 的费用匹配
贪心的正确性来自于费用为 \(1, 3\) 的边只会对奇偶性不同的点连接，而费用为 \(2\) 的边只会对奇偶性相同的点连接；
二者是独立的，而奇偶性不同（代价可 \(1\) 可 \(3\)）的情况下当然优先选择 \(1\) qaq
最大流dinic算法在二分图中复杂度为 \(O(n\sqrt m)\)，\(m\approx \frac{n^2}{logn}\)，故一组测试复杂度 \(O(\frac{n^{2.5}}{logn})\)，取上界的时候最多 10 组，可以通过
Code
const int maxn = 2e4 + 5, maxm = 6e6 + 6;
const int INF = 0x3f3f3f3f;
//const ll INF = 0x3f3f3f3f3f3f3f3f;
struct MaxFlow {
struct edge {
int u, v, cap, flow;
edge() {}
edge(int u, int v, int cap, int flow) :u(u), v(v), cap(cap), flow(flow) {}
}eg[maxm << 1];
int n;
int tot, dis[maxn << 1], cur[maxn << 1];
vector<int> tab[maxn << 1];
void init(int _n) {
tot = 0; n = _n;
for (int i = 0; i <= n; ++i) tab[i].clear();
}
void addedge(int u, int v, int cap) {
tab[u].push_back(tot);
eg[tot++] = edge(u, v, cap, 0);
tab[v].push_back(tot);
eg[tot++] = edge(v, u, 0, 0);
}
int bfs(int s, int t) {
queue<int> q;
q.push(s);
//memset(dis, INF, sizeof dis);
for (int i = 0; i <= n; ++i) dis[i] = INF;
dis[s] = 0;
while (!q.empty()) {
int h = q.front(), i;
q.pop();
for (i = 0; i < tab[h].size(); ++i) {
edge& e = eg[tab[h][i]];
if (e.cap > e.flow && dis[e.v] == INF) {
dis[e.v] = dis[h] + 1;
q.push(e.v);
}
}
}
return dis[t] < INF;
}
int dfs(int x, int maxflow, int s, int t) {
if (x == t || maxflow == 0) return maxflow;
int flow = 0, i, f;
for (i = cur[x]; i < tab[x].size(); ++i) {
cur[x] = i;
edge& e = eg[tab[x][i]];
if (dis[e.v] == dis[x] + 1 && (f = dfs(e.v, min(maxflow, e.cap - e.flow), s, t)) > 0) {
e.flow += f;
eg[tab[x][i] ^ 1].flow -= f;
flow += f;
maxflow -= f;
if (maxflow == 0) break;
}
}
return flow;
}
int dinic(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
//memset(cur, 0, sizeof(cur));
for (int i = 0; i <= n; ++i) cur[i] = 0;
flow += dfs(s, INF, s, t);
}
return flow;
}
}F;
const int M = 2e4 + 5;
bitset<M + 5> is_prime;
int prime[M + 5];
void get_prime() {
is_prime.set(); is_prime[0] = is_prime[1] = 0;
int cnt = 0;
for (int i = 2; i <= M; ++i) {
if (is_prime[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt; ++j) {
if (i * prime[j] > M) break;
is_prime[i * prime[j]] = 0;
if (i % prime[j] == 0) break;
}
}
prime[0] = cnt;
}
void AC() {
int n; cin >> n;
vector<int> A(n + 1);
for (int i = 1; i <= n; ++i) cin >> A[i];
for (int i = n; i >= 1; --i) A[i] = A[i] - A[i - 1];
A[n + 1] = INF;
vector<pii> pos, neg;
for (int i = 1; i <= n + 1; ++i) {
if (A[i] > 0) pos.push_back(make_pair(A[i], i));
if (A[i] < 0) neg.push_back(make_pair(-A[i], i));
}
int s = n + 2, t = n + 3;
F.init(n + 3);
for (auto& x : pos) {//(n/2)^2/logn 条边
for (auto& y : neg) {
int dis = abs(x.second - y.second);
if (dis != 2 && is_prime[dis]) {
F.addedge(x.second, y.second, x.first);
}
}
}
for (auto& x : pos) F.addedge(s, x.second, x.first);
for (auto& x : neg) F.addedge(x.second, t, x.first);
int ans = F.dinic(s, t);
pos.clear(); neg.clear();
for (int i = 0; i < F.tot; i += 2) {
int rest = F.eg[i].cap - F.eg[i].flow;
if (F.eg[i].u == s && rest) pos.push_back(make_pair(rest, F.eg[i].v));
if (F.eg[i].v == t && rest) neg.push_back(make_pair(rest, F.eg[i].u));
}
for (auto& y : neg) {
for (auto& x : pos) {
if ((x.second & 1) == (y.second & 1)) {
int dec = min(y.first, x.first);
y.first -= dec;
ans += dec * 2;
if (!y.first) break;
}
}
}
for (auto& y : neg) {
if (!y.first) continue;
ans += y.first * 3;
}
cout << ans << endl;
}
signed main() {
ios; int o_o = 1;
get_prime();
cin >> o_o;
while (o_o--) AC();
return 0;
}