A. [USACO22DEC] Breakdown P
给定一个\(n\) 个点 \(n^2\) 条边的有向完全图，边有边权 \(w_{i,j}\)。\(n^2\) 次操作，每次操作删去一条边，每次操作后询问从 \(1\) 到 \(n\) 可以重复经过点边的恰好 \(k\) 条边的最短路长度。
\(n \leq 300\)，\(k \leq 8\)，\(w_i \leq 10^8\)。
显然考虑倒过来加边。
注意到单次询问可以 \(\mathcal{O}(n)\) 解决，于是可以考虑 meet-in-middle，需要维护 \(f_{i,u},g_{i,u}(1 \leq i \leq 4)\) 分别表示从 \(1\) 到 \(u\) 和从 \(u\) 到 \(n\) 经过 \(i\) 条边的最短路，这样就能拼起来了。
接下来的问题就变成了如何维护 \(f,g\)。\(4\) 条边还是有点多，我们考虑再做一次折半，维护 \(h_{i,u,v}(1 \leq i \leq 2)\) 表示从 \(u\) 到 \(v\) 经过 \(i\) 条边的最短路，这两者都容易在 \(\mathcal{O}(n)\) 的时间复杂度内更新。
以 \(f\) 为例：当 \(x \neq 1\) 时，\(f\) 的路径一定会被分成长度不超过 \(2\) 的两段，可以直接利用 \(f\) 和 \(h\) 拼出来。只有当 \(x=1\) 时且 \(i = 4\) 时，我们需要确定长度为 \(3\) 的路径的形态，枚举中间点即可。虽然这部分时间复杂度为 \(\mathcal{O}(n^2)\)，但 \(x=1\) 的边只有 \(\mathcal{O}(n)\) 条，因此总时间复杂度为 \(\mathcal{O}(n^3)\)，可以通过本题。
code
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pi;
const int N = 3e2 + 5, inf = 1e9;
int n, k, f[5][N], g[5][N], h[3][N][N], e[N][N];
pi q[N * N];
int ans[N * N];
void chk(int &x, int y) {
if (x > y) x = y;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
int l = k / 2, r = k - l;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> e[i][j];
for (int i = 1, x, y; i <= n * n; i++) {
cin >> x >> y;
q[i] = {x, y};
}
for (int j = 1; j <= 4; j++)
for (int i = 1; i <= n; i++)
f[j][i] = g[j][i] = inf;
for (int k = 1; k <= 2; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
h[k][i][j] = inf;
for (int t = n * n, x, y, z; t >= 1; t--) {
tie(x, y) = q[t], z = e[x][y];
chk(h[1][x][y], z);
for (int i = 1; i <= n; i++) {
chk(h[2][x][i], z + h[1][y][i]), chk(h[2][i][y], h[1][i][x] + z);
}
for (int j = 1; j <= 2; j++)
for (int i = 1; i <= n; i++)
chk(f[j][i], h[j][1][i]), chk(g[j][i], h[j][i][n]);
if (x == 1) {
for (int i = 1; i <= n; i++)
chk(f[3][i], z + h[2][y][i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
chk(f[4][j], z + h[2][y][i] + h[1][i][j]);
}
if (y == n) {
for (int i = 1; i <= n; i++)
chk(g[3][i], h[2][i][x] + z);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
chk(g[4][j], h[1][j][i] + h[2][i][x] + z);
}
for (int i = 1; i <= n; i++) {
chk(f[3][i], f[1][x] + z + h[1][y][i]);
chk(g[3][i], h[1][i][x] + z + g[1][y]);
chk(f[4][i], f[1][x] + z + h[2][y][i]);
chk(f[4][i], f[2][x] + z + h[1][y][i]);
chk(g[4][i], h[2][i][x] + z + g[1][y]);
chk(g[4][i], h[1][i][x] + z + g[2][y]);
}
chk(f[3][y], f[2][x] + z);
chk(g[3][x], z + g[2][y]);
chk(f[4][y], f[3][x] + z);
chk(g[4][x], z + g[3][y]);
int ret = inf;
for (int i = 1; i <= n; i++)
ret = min(ret, f[l][i] + g[r][i]);
ans[t] = ret;
}
for (int i = 2; i <= n * n; i++) {
if (ans[i] == inf) {
cout << -1 << "\n";
} else {
cout << ans[i] << "\n";
}
}
if (n == 1) {
cout << 0 << "\n";
} else {
cout << -1 << "\n";
}
return 0;
}
B. [USACO22DEC] Making Friends P
给定一个 \(n\) 个点 \(m\) 条边的无向图，按照从 \(1\) 到 \(n\) 的顺序依次删点，删掉 \(i\) 时把所有与 \(i\) 相邻的点两两之间连边（若已经有边则不再连）。求最终会新连多少条边。
\(n,m \leq 2 \times 10^5\)。
我们给所有边定一个方向：对于边 \((u,v)(u < v)\)，规定其方向为 \(u \to v\)。
考虑换一种方式统计答案：只在删除 \(i\) 时统计 \(i\) 的出边数量，其正确性显然。
接下来考虑如何维护操作过程。我们对于每个点 \(i\) 维护其出边集合 \(e_i\)，由于我们只需要在删除 \(i\) 时统计 \(i\) 的出边数量，因此我们可以将一些边 “延迟加入”，以达到减少复杂度的目的。具体来说是这样的：删除点 \(i\) 时，我们取出 \(e_i\) 中的最小元素 \(v\)，然后将 \(e_i\) 内的其他元素并入 \(e_v\) 即可。
该做法的正确性不难验证。使用 set 启发式合并容易维护上述过程，时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
int n, m;
set <int> e[N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
if (x > y) swap(x, y);
e[x].insert(y);
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
if (e[i].size() == 0)
continue;
ans += e[i].size();
int u = *e[i].begin(), v = i; e[v].erase(e[v].begin());
if (e[u].size() < e[v].size()) {
swap(e[u], e[v]);
}
for (auto x : e[v]) {
e[u].insert(x);
}
}
ans -= m;
cout << ans << "\n";
return 0;
}
C. [USACO22DEC] Palindromes P
给定一个 \(01\) 串 \(S\)，定义一个 \(01\) 串的权值为通过交换相邻元素到达回文串需要的最小操作次数，如果无法到达则定义为 \(-1\)。求 \(S\) 的所有子串的权值之和。
\(n \leq 7500\)。
先考虑如果给定一个 \(01\) 串，如何求其权值。
不妨只考虑 \(\tt 1\) 的对称。显然，我们不会交换两个 \(\tt 1\) 的位置，因此所有 \(\tt 1\) 的相对位置不会发生改变。另一个显然的事实是无解当且仅当 \(\tt 1\) 有奇数个，且总长度为偶数。
考虑找到每一对对应的 \(\tt 1\)（如果存在中间的 \(\tt 1\) 则单独考虑），对于第 \(i\) 对 \(\tt 1\)，设左边的 \(\tt 1\) 是从左数第 \(l_i\) 个，右边的是从右数第 \(r_i\) 个，使它们对应所需要的操作次数为 \(|l_i-r_i|\)。因此答案即为所有 \(|l_i - r_i|\) 之和。
直接计算是 \(\mathcal{O}(n^3)\) 的，考虑优化。由于我们要求的东西是一个对称的形式，考虑枚举中点（可能是一个 \(\tt 1\) 或在两个 \(\tt 1\) 之间），然后往两边拓展，途中计算每一对 \(l_i,r_i\) 的贡献。
对于一对 \(\tt 1\)，设其从左至右的编号为 \(l_i,r_i\)，那么对于区间 \([l,r](l < l_i,r > r_i)\)，它的贡献为 \(|(l_i - l + 1) + (r - r_i + 1)| = |l_i + r_i - (l+r)|\)。注意到其中的变量只有 \(l+r\)，我们不妨设 \(f_i(s) = |l_i + r_i - s|\)。则对于区间 \([l,r]\)，其答案为 \(\sum \limits_{i=1}^k f_i(l+r)\)，其中 \(k\) 为这个区间内的 \(\tt 1\) 的对数。我们将其记为 \(F(l+r)\)。
我们可以将 \(k\) 相同的区间一起考虑，即把 \(l,r\) 分别固定在区间 \((l_{i+1},l_i],[r_i,r_{i+1})\) 内。接下来我们需要解决的问题是 \(l,r\) 移动时 \(F(l+r)\) 的变化。
具体来说，以 \(F(s) \to F(s+1)\) 为例，当 \(s \gets s+1\) 时，对于所有 \(l_i+r_i \geq s+1\) 的 \(f_i(s)\) 要 \(-1\)，其余则要 \(+1\)。不难发现 \(F(l+r)\) 可以按照 \(l_i + r_i\) 分成若干段，每一段内都是一个一次函数，因此我们只需要维护差分 \(d(s) = F(s+1) - F(s)\) 即可。易知 \(d(s+1) - d(s) = 2c_{s+1}\)，其中 \(c_s\) 表示 \(l_i + r_i = s\) 的对数。
虽然看起来共有 \(\mathcal{O}(n)\) 个中心，每个中心最高会有 \(\mathcal{O}(n^2)\) 复杂度的计算，但因为我们只是枚举了所有的子串，所以复杂度是 \(\mathcal{O}(n^2)\) 的，可以通过本题。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 8e3 + 5;
typedef long long LL;
int n, m, p[N], c[N << 1];
string s;
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> s;
n = s.length();
for (int i = 1; i <= n; i++) {
if (s[i - 1] == 'G') p[++m] = i;
}
p[0] = 0, p[m + 1] = n + 1;
LL ans = 0;
for (int L = 1; L <= m; L++) {
for (int R = L; R <= L + 1 && R <= m; R++) {
int d = 0, f = 0;
memset(c, 0, sizeof(c));
for (int i = 0; L - i >= 1 && R + i <= m; i++) {
int l1 = p[L - i], l2 = p[L - i - 1];
int r1 = p[R + i], r2 = p[R + i + 1];
if (l1 < r1) {
c[l1 + r1] += 1, d += 1;
}
for (int l = l1; l > l2; l--) {
for (int r = r1; r < r2; r++) {
if (L == R) {
if ((r - l + 1) % 2 == 1) {
ans += (f + abs((l + r) / 2 - p[L]));
} else {
ans -= 1;
}
} else {
ans += f;
}
f += d, d += 2 * c[l + r + 1];
}
for (int r = r2; r >= r1; r--) {
d -= 2 * c[l + r];
f -= d;
}
}
for (int r = r1; r < r2; r++) {
f += d;
d += 2 * c[l2 + r + 1];
}
}
}
}
cout << ans << "\n";
return 0;
}