前

刚学农回来。唯一的复习是学农前打的一把 CF（而且打得不怎么样）

T1

题意

把 $n$ 个人安排进 $m$ 个位置，每个位置最多放 $\left\lceil \dfrac{n}{2} \right\rceil$ 个人。

第 $i$ 个人安排进第 $j$ 个位置的收益是 $a_{i,j}$，求最大收益。

反悔贪心，之前没看到最多放 $\left\lceil \dfrac{n}{2} \right\rceil$，还在想多重反悔的问题。但其实不用。

在安排过程中，最多只有一个位置安排满（且这个满的位置不会变），这就可以简单地反悔贪心。

由于没审好题，目前时间：$40\ \mathrm{min}$。

代码由 AI 根据思路生成

#include <bits/stdc++.h>
using namespace std;

struct Person {
    int a[3];
    int best_dept;   // 当前分配的部门 0,1,2
    int second_dept; // 次优部门
    int loss;        // 离开 best_dept 的损失 = a[best_dept] - a[second_dept]
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<Person> persons(n);
        vector<int> cnt(3, 0);
        int total = 0;

        // 读入并初始化分配
        for (int i = 0; i < n; i++) {
            cin >> persons[i].a[0] >> persons[i].a[1] >> persons[i].a[2];
            // 找出最大值和次大值的部门
            int best = 0, second = -1;
            for (int j = 1; j < 3; j++) {
                if (persons[i].a[j] > persons[i].a[best]) {
                    second = best;
                    best = j;
                } else if (second == -1 || persons[i].a[j] > persons[i].a[second]) {
                    second = j;
                }
            }
            // 如果次大还没确定（比如有两个相同最大值）
            if (second == -1) {
                // 找除了best外最大的
                second = (best == 0) ? 1 : 0;
                for (int j = 0; j < 3; j++) {
                    if (j != best && persons[i].a[j] > persons[i].a[second]) {
                        second = j;
                    }
                }
            }
            persons[i].best_dept = best;
            persons[i].second_dept = second;
            persons[i].loss = persons[i].a[best] - persons[i].a[second];
            cnt[best]++;
            total += persons[i].a[best];
        }

        // 每个部门一个最小堆，存 (loss, index)
        vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> heaps(3);

        for (int i = 0; i < n; i++) {
            int dept = persons[i].best_dept;
            heaps[dept].push({persons[i].loss, i});
        }

        // 调整超额部门
        for (int dept = 0; dept < 3; dept++) {
            while (cnt[dept] > n / 2) {
                auto [loss, idx] = heaps[dept].top();
                heaps[dept].pop();
                // 将这个人调整到次优部门
                int old_dept = persons[idx].best_dept;
                int new_dept = persons[idx].second_dept;
                // 如果新部门也满了，需要递归调整？但题目最多一个部门满，所以新部门不会满
                // 直接调整
                cnt[old_dept]--;
                cnt[new_dept]++;
                total -= loss;
                // 更新这个人的 best_dept 和 second_dept
                persons[idx].best_dept = new_dept;
                // 需要更新其次优部门：在剩下的两个部门里选最大的
                int sec = -1;
                for (int j = 0; j < 3; j++) {
                    if (j != new_dept) {
                        if (sec == -1 || persons[idx].a[j] > persons[idx].a[sec]) {
                            sec = j;
                        }
                    }
                }
                persons[idx].second_dept = sec;
                persons[idx].loss = persons[idx].a[new_dept] - persons[idx].a[sec];
                // 加入新部门的堆
                heaps[new_dept].push({persons[idx].loss, idx});
            }
        }

        cout << total << '\n';
    }
    return 0;
}

T2

题意

有一个 $|V|=n \le 10^4, |E|=m \le 10^6$ 的连通图，有 $k \le 10$ 个结点是额外结点。额外结点的启用是可选的，启用第 $i$ 个额外结点的代价为 $c_i$。

求 最小生成树大小 $+$ 总启用代价 的最小可能值。

看见额外结点 $\le 10$ 就知道要枚举所有启用情况。首先给非额外结点跑一遍最小生成树，把边规模压缩到 $O(n)$。

然后？我只知道在最小生成树加一条边的解法。加很多条边就不知道了。

直接 Kruskal（或 Prim）是 $O(m \log m + 2^k kn \log n)$ 的。

这个解法大概率会在大测试点 $\color{#052242}\textbf{TLE}$，考场上想了一会儿（其实还挺久的）没想到更好的，于是打了。

犹豫了很久，目前时间：$2 \mathrm{h}$。然后去上了个厕所中场休息。

代码由 AI 根据思路生成

#include <bit/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].u--; edges[i].v--;
    }

    // 原图 MST
    sort(edges.begin(), edges.end());
    DSU dsu0(n);
    vector<Edge> mstEdges;
    long long baseCost = 0;
    for (const auto& e : edges) {
        if (dsu0.unite(e.u, e.v)) {
            mstEdges.push_back(e);
            baseCost += e.w;
        }
    }
    // mstEdges 现在有 n-1 条边

    vector<long long> c(k);
    vector<vector<long long>> a(k, vector<long long>(n));
    for (int j = 0; j < k; j++) {
        cin >> c[j];
        for (int i = 0; i < n; i++) {
            cin >> a[j][i];
        }
    }

    long long ans = baseCost; // 不使用任何乡镇的情况

    // 枚举乡镇选择
    for (int mask = 1; mask < (1 << k); mask++) {
        int townCount = __builtin_popcount(mask);
        int totalNodes = n + townCount;
        vector<Edge> allEdges = mstEdges; // 原 MST 边

        // 分配乡镇编号: n, n+1, ...
        vector<int> townId;
        long long activateCost = 0;
        for (int j = 0; j < k; j++) {
            if (mask >> j & 1) {
                townId.push_back(j);
                activateCost += c[j];
            }
        }

        // 加入乡镇到城市的边
        for (int idx = 0; idx < townId.size(); idx++) {
            int j = townId[idx];
            int townNode = n + idx;
            for (int city = 0; city < n; city++) {
                allEdges.push_back({townNode, city, a[j][city]});
            }
        }

        // 跑新图的 MST
        sort(allEdges.begin(), allEdges.end());
        DSU dsu(totalNodes);
        long long mstCost = 0;
        int connected = 0;
        for (const auto& e : allEdges) {
            if (dsu.unite(e.u, e.v)) {
                mstCost += e.w;
                connected++;
                if (connected == totalNodes - 1) break;
            }
        }

        ans = min(ans, activateCost + mstCost);
    }

    cout << ans << '\n';
    return 0;
}

洛谷 $\color{orange}\text{80 pts}$。

赛时唐

其实可以用归并把时间复杂度变成 $O(m \log m + 2^k kn \alpha(n))$。

我赛时没用归并应该是因为比较难回溯。但其实根本不用回溯，从头归并的时间复杂度不会更高，瓶颈在 Kruskal。

归并解法（AI 生成，100 pts）

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].u--; edges[i].v--;
    }

    // 原图 MST
    sort(edges.begin(), edges.end());
    DSU dsu0(n);
    vector<Edge> mstEdges;
    long long baseCost = 0;
    for (const auto& e : edges) {
        if (dsu0.unite(e.u, e.v)) {
            mstEdges.push_back(e);
            baseCost += e.w;
        }
    }

    vector<long long> c(k);
    vector<vector<Edge>> townEdges(k); // 每个乡镇到城市的边（已排序）
    for (int j = 0; j < k; j++) {
        cin >> c[j];
        for (int i = 0; i < n; i++) {
            long long cost;
            cin >> cost;
            townEdges[j].push_back({n + j, i, cost});
        }
        sort(townEdges[j].begin(), townEdges[j].end());
    }

    long long ans = baseCost;

    // 枚举乡镇选择
    for (int mask = 1; mask < (1 << k); mask++) {
        vector<int> selected;
        long long activateCost = 0;
        for (int j = 0; j < k; j++) {
            if (mask >> j & 1) {
                selected.push_back(j);
                activateCost += c[j];
            }
        }
        int totalNodes = n + selected.size();

        // 多路归并 Kruskal
        DSU dsu(totalNodes);
        // 每个列表的当前指针
        vector<int> ptr(selected.size() + 1, 0);
        // 堆： (weight, list_type, list_index)
        // list_type: 0 原MST边，1~selected.size() 乡镇边
        priority_queue<tuple<long long, int, int>, 
                       vector<tuple<long long, int, int>>, 
                       greater<tuple<long long, int, int>>> pq;

        // 初始加入原MST边的最小边
        if (!mstEdges.empty()) {
            pq.push({mstEdges[0].w, 0, 0});
        }
        // 加入每个乡镇的最小边
        for (int idx = 0; idx < selected.size(); idx++) {
            int j = selected[idx];
            if (!townEdges[j].empty()) {
                pq.push({townEdges[j][0].w, idx + 1, 0});
            }
        }

        long long mstCost = 0;
        int connected = 0;

        while (!pq.empty() && connected < totalNodes - 1) {
            auto [weight, type, pos] = pq.top();
            pq.pop();

            Edge e;
            if (type == 0) {
                // 原MST边
                e = mstEdges[pos];
                // 加入下一条原MST边
                if (pos + 1 < mstEdges.size()) {
                    pq.push({mstEdges[pos + 1].w, 0, pos + 1});
                }
            } else {
                // 乡镇边
                int j = selected[type - 1];
                e = townEdges[j][pos];
                // 加入下一条这个乡镇的边
                if (pos + 1 < townEdges[j].size()) {
                    pq.push({townEdges[j][pos + 1].w, type, pos + 1});
                }
            }

            // 调整节点编号：乡镇编号从 n 开始连续分配
            int u = e.u, v = e.v;
            if (u >= n) {
                // 映射乡镇编号
                int townIndex = -1;
                for (int idx = 0; idx < selected.size(); idx++) {
                    if (selected[idx] == u - n) {
                        townIndex = idx;
                        break;
                    }
                }
                u = n + townIndex;
            }
            if (v >= n) {
                int townIndex = -1;
                for (int idx = 0; idx < selected.size(); idx++) {
                    if (selected[idx] == v - n) {
                        townIndex = idx;
                        break;
                    }
                }
                v = n + townIndex;
            }

            if (dsu.unite(u, v)) {
                mstCost += weight;
                connected++;
            }
        }

        ans = min(ans, activateCost + mstCost);
    }

    cout << ans << '\n';
    return 0;
}

T3

题意

给定 $n$ 对字符串 $|s_{i,1}| = |s_{i,2}|$，有 $q$ 次询问，每次询问给出 $t_1, t_2$

定义

若 $|s_1|=|s_2|$，定义 $(d_1, d_2, l, r) = \mathrm{diff}(s_1, s_2)$：

• $l$ 是 $s_1, s_2$ 的最长公共前缀；
• $r$ 是 $s_1, s_2$ 的最长公共后缀；
• $s_i = l + d_i + r$。

不难发现可以替换等价于

• $d_{1s} = d_{1t}, d_{2s} = d_{2t}$
• $l_t \in \operatorname{suffix}(l_s)$
• $r_t \in \operatorname{prefix}(r_s)$

打了个四层的超大字典树，是 $O(q(n+\mathrm{ans}))$ 的，虽然大样例的 $\mathrm{ans}$ 都不大，但是可能被别有用心的构造卡掉。

然后发现查前缀的时候忘记找边界情况了。改了。

但是最后发现最后一个大样例错了。目前时间：$3 \mathrm{h}\ 30 \mathrm{min}$，于是赶紧做第四题去了。

AI 很傻，生成不出对应的代码，所以不贴了。

赛时唐

实际上只需构造字符串 $l \# d_1 \# d_2 \# r$ 即可变成字符串匹配问题。

鉴定为字符串问题做少了。

T4

用 next_permutation 打了个暴力。最后剩 $15\ \mathrm{min}$。

后

城市套路深，我要回农村……

唱首歌罢。

你愿相信什么 就把世界 看成什么样

偶尔难题 加点重量 越要轻轻的旋转

所以无论如何 记得保管 小小的光环

笑就好 哭也好 今天就是明天最好的陪伴

晚上堵车。晕车。复活之后 8 点半吃了晚饭。