Atcoder Beginner Contest 416

打的很炸裂啊。

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;
}

G