打的很炸裂啊。
D
贪心一下，一个 \(a_i\) 如果不能吃 \(b_j\) 超过 \(m\) 的话分配给它最小的 \(b\)。否则越小的 \(a_i\) 应当分配越大的 \(b_j\)，排序一下处理即可。
const int N = 300010;
int T, n, m;
int a[N], b[N];void solve() {n = read(), m = read();rep(i, 1, n) a[i] = read();rep(i, 1, n) b[i] = read();sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);LL ans = 0;for (int i = 1, l = 1, r = n; i <= n; i ++) {if (a[i] + b[r] < m) ans += (a[i] + b[l]) % m, l ++;else ans += (a[i] + b[r]) % m, r --; }printf("%lld\n", ans);
}int main() {T = read();while (T --) solve();return 0;
}
E
和官解不一样，感觉没啥技术，就是代码挺长。
显然 \(\Theta(QN^2)\) 能过，所以考虑 floyd。
加一条边 \((a, b, c)\)，就 f[i][j] = min(f[i][j], f[i][a] + c + f[b][j]) 更新一下即可（注意这里是双向边，另一种情况也要更新）。
如果一个点变成了机场，那相当于直接连了 \(K\) 条边，直接更新会超时。
但你注意到这里所有边都类似于 f[i][u] + c + f[x][j]，其中 f[x][j] 是固定的，所以只要预处理一下 f[i][u] 的最小值来更新即可。
const int N = 510;
int n, m, k, T, q, d[N];
int g[N][N], minv[N], minv2[N];signed main() {n = read(), m = read();for (int i = 0; i <= n; i ++)for (int j = 0; j <= n; j ++) g[i][j] = 1e18;while (m --) {int a = read(), b = read(), c = read();g[a][b] = min(g[a][b], c);g[b][a] = min(g[b][a], c);}k = read(), T = read();for (int i = 1; i <= k; i ++) d[i] = read();for (int i = 1; i <= k; i ++)for (int j = i + 1; j <= k; j ++)g[d[i]][d[j]] = min(g[d[i]][d[j]], T), g[d[j]][d[i]] = min(g[d[j]][d[i]], T); for (int i = 1; i <= n; i ++) g[i][i] = 0;for (int k = 1; k <= n; k ++)for (int i = 1; i <= n; i ++)for (int j = 1; j <= n; j ++)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);for (int i = 1; i <= n; i ++) {minv[i] = minv2[i] = 1e18;for (int j = 1; j <= k; j ++) minv[i] = min(minv[i], g[i][d[j]]), minv2[i] = min(minv2[i], g[d[j]][i]);}int q = read();while (q --) {int op = read();if (op == 1) {int a = read(), b = read(), c = read();g[a][b] = min(g[a][b], c); g[b][a] = min(g[b][a], c);for (int i = 1; i <= n; i ++)for (int j = 1; j <= n; j ++) {g[i][j] = min(g[i][j], g[i][a] + c + g[b][j]);g[i][j] = min(g[i][j], g[i][b] + c + g[a][j]);}for (int i = 1; i <= n; i ++) {minv[i] = minv2[i] = 1e18;for (int j = 1; j <= k; j ++) minv[i] = min(minv[i], g[i][d[j]]), minv2[i] = min(minv2[i], g[d[j]][i]);}} else if (op == 2) {int x = read();for (int i = 1; i <= k; i ++) {g[d[i]][x] = min(g[d[i]][x], T), g[x][d[i]] = min(g[x][d[i]], T);minv[d[i]] = min(minv[d[i]], T), minv[x] = min(minv[x], T);}d[++ k] = x;for (int i = 1; i <= n; i ++)for (int j = 1; j <= n; j ++) {g[i][j] = min(g[i][j], minv[i] + T + g[x][j]);g[i][j] = min(g[i][j], g[i][x] + T + minv2[j]);}for (int i = 1; i <= n; i ++) {minv[i] = minv2[i] = 1e18;for (int j = 1; j <= k; j ++) minv[i] = min(minv[i], g[i][d[j]]), minv2[i] = min(minv2[i], g[d[j]][i]);}} else {int ans = 0;for (int i = 1; i <= n; i ++)for (int j = 1; j <= n; j ++)ans += g[i][j] > 1e17 ? 0 : g[i][j];printf("%lld\n", ans);}}return 0;
}
F
想是比较好想，但写对挺难的。
显然树形背包，设 \(f_{u, i, 0/1/2}\) 分别表示 \(u\) 子树内选 \(i\) 条路径，其中 \(u\) 不在路径上/是路径的端点/是路径的中间点。
转移有点魔怔可以看代码。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }return x * f;
}const int N = 200010, M = 6;
int n, k, a[N];
vector<int> G[N];
int f[N][M][3], g[M][3];void dfs(int u, int fa) {f[u][1][1] = a[u]; f[u][0][0] = 0;for (auto v : G[u]) if (v != fa) {dfs(v, u); for (int i = 0; i <= k; i ++) for (int s = 0; s < 3; s ++) g[i][s] = -1e18;for (int i = 0; i <= k; i ++)for (int j = 0; i + j - 1 <= k; j ++) { // 小细节，如果 i + j 就错了if (i + j - 1 <= k && i + j - 1 >= 0) g[i + j - 1][2] = max(g[i + j - 1][2], f[u][i][1] + f[v][j][1]);if (i + j > k) continue;g[i + j][0] = max(g[i + j][0], f[u][i][0] + max({f[v][j][0], f[v][j][1], f[v][j][2]}));g[i + j][1] = max(g[i + j][1], f[u][i][0] + f[v][j][1] + a[u]);rep(t, 0, 2) g[i + j][1] = max(g[i + j][1], f[u][i][1] + f[v][j][t]);rep(t, 0, 2) g[i + j][2] = max(g[i + j][2], f[u][i][2] + f[v][j][t]);} for (int i = 0; i <= k; i ++)for (int s = 0; s < 3; s ++) f[u][i][s] = max(f[u][i][s], g[i][s]);}
}signed main() {memset(f, -0x3f, sizeof f);n = read(), k = read();rep(i, 1, n) a[i] = read();for (int i = 1; i < n; i ++) {int a = read(), b = read();G[a].push_back(b), G[b].push_back(a);}dfs(1, 0); int ans = 0;for (int i = 0; i <= k; i ++)for (int j = 0; j < 3; j ++)ans = max(ans, f[1][i][j]);printf("%lld\n", ans);return 0;
}