官方题解 | 巅峰赛#32

巅峰赛32题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	返程拼车	普及-
T2	星港远航	普及/提高-
T3	霓虹线路	普及/提高-
T4	雾港灯串	普及-
T5	星灯选址	普及-
T6	分裂晶体	提高+/省选-

T1 返程拼车

题目大意

给定 $n$ 个同学在数轴上的位置 $x_i$，每辆车最多载 $2$ 人，且两人之间距离满足 $|x_i-x_j|\le D$ 才能拼车。求最少需要多少辆车使所有同学都能回家。

题解思路

要让车辆数最少，就要让“拼车的对数”尽量多，因为每拼成一对就比两人各自打车少用一辆车。

把所有位置 $x_i$ 排序为 $p_1\le p_2\le \dots \le p_n$。在有序序列上从左到右扫描：

• 如果 $p_{i+1}-p_i\le D$，就把这两位同学配成一对，然后跳过这两人；
• 否则 $p_i$ 无法与任何更右侧的人拼车（更右只会更远），只能单独一辆车。

这是最大化不相交配对数的典型贪心：能配就立刻配相邻元素。设配对数为 pairs，答案为

$$\text{cars}=n-\text{pairs}.$$

复杂度：排序 $O(n\log n)$，扫描 $O(n)$。

参考代码

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

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

    int n;
    long long D;
    cin >> n >> D;

    vector<long long> x(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    sort(x.begin(), x.end());

    int pairs = 0;
    int i = 0;
    while (i + 1 < n) {
        if (x[i + 1] - x[i] <= D) {
            pairs++;
            i += 2;
        } else {
            i += 1;
        }
    }

    cout << (n - pairs) << "\n";
    return 0;
}

T2 星港远航

题目大意

从位置 $0$ 出发，要到达位置 $L$。初始有能量 $P$，每走 $1$ 单位距离消耗 $1$ 能量。沿途有若干补给站，第 $i$ 个补给站在位置 $x_i$，可以提供 $a_i$ 的能量，每个站最多使用一次。求最少需要使用多少个补给站才能到达终点，若无法到达输出 $-1$。

题解思路

这是一个典型的贪心问题。关键在于：当当前能量不足以继续前进时，应该从之前经过的所有补给站中选择补给量最大的那个来使用。

先将所有补给站按位置排序，并把终点看成一个位置为 $L$、补给量为 $0$ 的虚拟站。设当前最远能到达的位置为 $reach$，初始为 $P$，同时用一个大根堆维护所有已经经过的补给站的补给量。

从左到右扫描每个站：
如果当前站的位置 $x_i \le reach$，说明可以到达，就把该站的补给量加入堆中；如果 $x_i > reach$，说明当前无法到达这个站，此时必须从堆中取出最大补给量来补充能量，使 $reach$ 增大，并统计一次补给操作。重复这个过程，直到可以到达当前站或者堆为空。

如果堆为空仍无法前进，说明无法到达终点，输出 $-1$。否则最终成功走到终点，补给次数就是答案。

这个贪心策略的核心在于：每次必须补给时，选择补给量最大的站，可以让当前可达距离尽可能远，从而减少后续补给次数，是最优选择。

参考代码

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

using ll = long long;

struct Node {
    ll x;
    ll a;
};

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

    int n;
    ll L, P;
    cin >> n >> L >> P;

    vector<Node> s(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> s[i].x >> s[i].a;
    }

    s[n] = {L, 0};
    sort(s.begin(), s.end(), [](const Node& u, const Node& v) {
        return u.x < v.x;
    });

    priority_queue<ll> q;
    ll reach = P;
    int ans = 0;

    for (int i = 0; i <= n; ++i) {
        while (reach < s[i].x) {
            if (q.empty()) {
                cout << -1 << '\n';
                return 0;
            }
            reach += q.top();
            q.pop();
            ++ans;
        }
        q.push(s[i].a);
    }

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

T3 霓虹线路

题目大意

给定一棵有 $n$ 个点的树，需要给每条边染色，颜色编号为 $1\sim k$。要求对于任意一个点，与它相连的所有边颜色必须两两不同。判断是否存在合法方案，若存在输出任意一种。

题解思路

树的边染色要求“每个点相邻边颜色两两不同”，这就是树上的proper edge coloring。设树的最大度数为 $\Delta$。必要条件是 $k\ge \Delta$：因为度为 $\Delta$ 的点周围 $\Delta$ 条边必须用不同颜色。

对树而言这也是充分条件：当 $k\ge\Delta$ 时一定能染色。构造方法用一次 DFS 从根向下分配颜色即可。

把树以 1 为根。对每个点 $u$，设与父边的颜色为 parColor[u]（根为 0）。我们给 $u$ 的所有子边依次分配颜色 1..k，但跳过 parColor[u]，并且同一节点内部不重复。因为 $u$ 的子边数是 deg(u)-1（根是 deg(u)），而 $deg(u)\le k$，所以总能分配完且不会用到第 $k+1$ 种颜色。

实现上先用栈/队列求出父子关系，再按父到子的顺序给边赋色，复杂度 $O(n)$。

若 $k<\Delta$，直接输出 NO。

参考代码

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

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

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

    vector<int> eu(n), ev(n);
    vector<vector<pair<int,int>>> g(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        eu[i] = u;
        ev[i] = v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        deg[u]++; deg[v]++;
    }

    int mx = 0;
    for (int i = 1; i <= n; i++) mx = max(mx, deg[i]);
    if (mx > k) {
        cout << "NO\n";
        return 0;
    }

    vector<int> parent(n + 1, 0);
    vector<int> parColor(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    // iterative DFS to get parent and order
    vector<int> st;
    st.reserve(n);
    st.push_back(1);
    parent[1] = -1;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);
        for (auto [v, id] : g[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            st.push_back(v);
        }
    }

    vector<int> color(n); // 1..n-1 used
    for (int u : order) {
        int c = 1;
        for (auto [v, id] : g[u]) {
            if (v == parent[u]) continue;

            while (c == parColor[u]) c++;
            color[id] = c;
            parColor[v] = c;
            c++;
        }
    }

    cout << "YES\n";
    for (int i = 1; i <= n - 1; i++) {
        if (i > 1) cout << ' ';
        cout << color[i];
    }
    cout << "\n";
    return 0;
}

T4 雾港灯串

题目大意

给定一个长度为 $n$ 的 01 串，可以通过翻转某一位（$0 \leftrightarrow 1$）来修改它。要求最终得到的新串满足：任意连续长度为 $4$ 的子串中，$1$ 的个数不能恰好为 $3$。求最少需要翻转多少次。

题解思路

本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 $b$，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。

用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 $i$ 位时，尝试把 $b_i$ 取为 0 或 1：

• 若 $i\ge 4$，则长度为 4 的窗口正好是“上一状态的 3 位 + 当前选择的 1 位”，对应一个 4 位数 w=(mask<<1)|b_i，若 popcount(w)==3 则该选择非法；
• 否则（前 3 位）没有形成长度为 4 的窗口，不需要检查。

代价增加为 [s_i\ne b_i]，新状态为 ((mask<<1)&7)|b_i。每步转移常数只有 16 次，整体复杂度为 $O(n)$，空间为 $O(1)$。

最终答案是处理完全部位置后所有 dp[mask] 的最小值。

参考代码

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

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

    int n;
    string s;
    cin >> n;
    cin >> s;

    const int INF = 1e9;
    vector<int> dp(8, INF), ndp(8, INF);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        fill(ndp.begin(), ndp.end(), INF);
        int a = s[i] - '0';

        for (int mask = 0; mask < 8; mask++) {
            if (dp[mask] >= INF) continue;

            for (int b = 0; b <= 1; b++) {
                if (i >= 3) {
                    int w = (mask << 1) | b; // 4 bits: last3 + b
                    if (__builtin_popcount((unsigned)w) == 3) continue;
                }
                int cost = dp[mask] + (b != a);
                int nmask = ((mask << 1) & 7) | b;
                if (cost < ndp[nmask]) ndp[nmask] = cost;
            }
        }

        dp.swap(ndp);
    }

    int ans = *min_element(dp.begin(), dp.end());
    cout << ans << "\n";
    return 0;
}

T5 星灯选址

题目大意

给定一个长度为 $n$ 的数组 $a_i$，表示在第 $i$ 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。

题解思路

这是经典的线性 DP。设 dp[i] 表示只考虑前 i 个位置能得到的最大收益，则第 i 个位置要么不选，要么选：

• 不选 i：收益 dp[i-1]
• 选 i：则 i-1 不能选，收益 dp[i-2] + a_i

所以递推为

$$dp[i]=\max(dp[i-1], dp[i-2]+a_i).$$

边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。

参考代码

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> dp(n + 1, 0);
    vector<char> take(n + 1, 0);

    if (n >= 1) {
        if (a[1] > 0) {
            dp[1] = a[1];
            take[1] = 1;
        } else {
            dp[1] = 0;
            take[1] = 0;
        }
    }

    for (int i = 2; i <= n; i++) {
        long long v1 = dp[i - 1];
        long long v2 = dp[i - 2] + a[i];
        if (v2 > v1) {
            dp[i] = v2;
            take[i] = 1;
        } else {
            dp[i] = v1;
            take[i] = 0;
        }
    }

    vector<int> ans;
    int i = n;
    while (i >= 1) {
        if (take[i]) {
            ans.push_back(i);
            i -= 2;
        } else {
            i -= 1;
        }
    }
    reverse(ans.begin(), ans.end());

    cout << dp[n] << "\n";
    cout << ans.size() << "\n";
    for (int j = 0; j < (int)ans.size(); j++) {
        if (j) cout << ' ';
        cout << ans[j];
    }
    cout << "\n";
    return 0;
}

T6 分裂晶体

题目大意

给定一棵以 1 号节点为根的树，每个节点有一个整数能量值。要求通过任意重排每个节点的子树顺序，生成字典序最小的先序遍历序列。

题解思路

对任意节点 u，设它的“最稳定子序列” S(u) 是在允许重排 u 的孩子后，u 的子树先序序列中字典序最小的那条。显然整棵树的答案就是 S(1)。

如果 u 的孩子子树最稳定子序列分别是 S(v1),S(v2),…，那么 S(u) 一定形如：
S(u) = [a_u] + S(按某顺序排列的孩子 1) + S(孩子 2) + …
为了让拼接后的整体字典序最小，只需把孩子按各自的 S(v) 的字典序从小到大排序后依次拼接即可：因为先序序列在进入第一个孩子子树前已经固定为 a_u，之后最先产生差异的位置一定落在“第一个不同孩子的子序列”里，所以把最小的子序列放在最前是最优的。

因此问题变成：需要能高效比较两个子树的 S(u) 与 S(v)。直接把 S(u) 展开成数组会导致总长度平方级。

做法是把每个 S(u) 当成一条“序列对象”，用一棵隐式 Treap 维护：

• 长度 len；
• 两个模数下的多项式哈希值；
• 支持 O(log n) 取第 k 个元素、取前缀哈希。

比较两个序列时，用二分 + 前缀哈希求它们的最长公共前缀 LCP，再比较下一位元素即可完成字典序比较。对子树排序后，用 Treap 进行序列拼接（merge）即可得到父节点的序列对象。

整体流程：先把树以 1 为根，得到父子关系与后序顺序；按后序从叶到根处理，每个节点对孩子排序并合并生成自己的序列对象，同时把排序结果存下来。最后按存下来的孩子顺序做一次先序遍历输出能量值。

复杂度：设比较一次序列为 O(log^2 n)，则总复杂度约为 O((n + 总排序比较次数)·log^2 n)，在本题规模内可通过；空间 O(n)。

参考代码

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

static const long long MOD1 = 1000000007LL;
static const long long MOD2 = 1000000009LL;
static const long long BASE = 911382323LL;

long long add_mod(long long a, long long b, long long mod) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}
long long mul_mod(long long a, long long b, long long mod) {
    return (long long)((__int128)a * b % mod);
}

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

    int n;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<long long> all;
    all.reserve(n);
    for (int i = 1; i <= n; i++) all.push_back(a[i]);
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());

    vector<int> tok(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int id = (int)(lower_bound(all.begin(), all.end(), a[i]) - all.begin());
        tok[i] = id + 1;
    }

    vector<int> parent(n + 1, 0);
    vector<vector<int>> child(n + 1);
    vector<int> order;
    order.reserve(n);

    vector<int> st;
    st.reserve(n);
    st.push_back(1);
    parent[1] = -1;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            st.push_back(v);
        }
    }

    for (int v = 2; v <= n; v++) {
        child[parent[v]].push_back(v);
    }

    vector<long long> pw1(n + 2, 1), pw2(n + 2, 1);
    for (int i = 1; i <= n + 1; i++) {
        pw1[i] = mul_mod(pw1[i - 1], BASE, MOD1);
        pw2[i] = mul_mod(pw2[i - 1], BASE, MOD2);
    }

    vector<int> L(n + 2, 0), R(n + 2, 0), SZ(n + 2, 0), VAL(n + 2, 0);
    vector<unsigned int> PRI(n + 2, 0);
    vector<long long> H1(n + 2, 0), H2(n + 2, 0);
    int node_cnt = 0;

    auto rng_next = [&]() -> unsigned int {
        static unsigned long long x = 88172645463325252ull;
        x ^= x << 7;
        x ^= x >> 9;
        return (unsigned int)(x & 0xffffffffu);
    };

    auto pull = [&](int x) {
        int ls = L[x], rs = R[x];
        int lenL = ls ? SZ[ls] : 0;
        int lenR = rs ? SZ[rs] : 0;
        SZ[x] = lenL + 1 + lenR;

        long long left1 = ls ? H1[ls] : 0;
        long long right1 = rs ? H1[rs] : 0;
        long long left2 = ls ? H2[ls] : 0;
        long long right2 = rs ? H2[rs] : 0;

        long long t1 = mul_mod(left1, pw1[1 + lenR], MOD1);
        t1 = add_mod(t1, mul_mod((long long)VAL[x], pw1[lenR], MOD1), MOD1);
        t1 = add_mod(t1, right1, MOD1);
        H1[x] = t1;

        long long t2 = mul_mod(left2, pw2[1 + lenR], MOD2);
        t2 = add_mod(t2, mul_mod((long long)VAL[x], pw2[lenR], MOD2), MOD2);
        t2 = add_mod(t2, right2, MOD2);
        H2[x] = t2;
    };

    function<int(int,int)> merge = [&](int a, int b) -> int {
        if (!a) return b;
        if (!b) return a;
        if (PRI[a] < PRI[b]) {
            R[a] = merge(R[a], b);
            pull(a);
            return a;
        } else {
            L[b] = merge(a, L[b]);
            pull(b);
            return b;
        }
    };

    auto new_node = [&](int v) -> int {
        ++node_cnt;
        VAL[node_cnt] = v;
        PRI[node_cnt] = rng_next();
        L[node_cnt] = R[node_cnt] = 0;
        SZ[node_cnt] = 1;
        H1[node_cnt] = v % MOD1;
        H2[node_cnt] = v % MOD2;
        return node_cnt;
    };

    function<pair<long long,long long>(int,int)> prefix_hash = [&](int x, int len) -> pair<long long,long long> {
        if (!x || len <= 0) return {0, 0};
        int ls = L[x], rs = R[x];
        int lenL = ls ? SZ[ls] : 0;
        if (len <= lenL) return prefix_hash(ls, len);
        if (len == lenL + 1) {
            long long left1 = ls ? H1[ls] : 0;
            long long left2 = ls ? H2[ls] : 0;
            long long h1 = add_mod(mul_mod(left1, pw1[1], MOD1), VAL[x] % MOD1, MOD1);
            long long h2 = add_mod(mul_mod(left2, pw2[1], MOD2), VAL[x] % MOD2, MOD2);
            return {h1, h2};
        }
        int takeR = len - lenL - 1;
        auto rightPref = prefix_hash(rs, takeR);
        long long left1 = ls ? H1[ls] : 0;
        long long left2 = ls ? H2[ls] : 0;

        long long h1 = mul_mod(left1, pw1[1 + takeR], MOD1);
        h1 = add_mod(h1, mul_mod((long long)VAL[x], pw1[takeR], MOD1), MOD1);
        h1 = add_mod(h1, rightPref.first, MOD1);

        long long h2 = mul_mod(left2, pw2[1 + takeR], MOD2);
        h2 = add_mod(h2, mul_mod((long long)VAL[x], pw2[takeR], MOD2), MOD2);
        h2 = add_mod(h2, rightPref.second, MOD2);

        return {h1, h2};
    };

    function<int(int,int)> kth = [&](int x, int k) -> int {
        int ls = L[x];
        int lenL = ls ? SZ[ls] : 0;
        if (k < lenL) return kth(ls, k);
        if (k == lenL) return VAL[x];
        return kth(R[x], k - lenL - 1);
    };

    auto less_seq = [&](int ra, int rb, int firstA, int firstB) -> bool {
        if (firstA != firstB) return firstA < firstB;
        int la = ra ? SZ[ra] : 0;
        int lb = rb ? SZ[rb] : 0;
        int lim = min(la, lb);
        int lo = 0, hi = lim;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            auto ha = prefix_hash(ra, mid);
            auto hb = prefix_hash(rb, mid);
            if (ha == hb) lo = mid;
            else hi = mid - 1;
        }
        int lcp = lo;
        if (lcp == lim) return la < lb;
        int va = kth(ra, lcp);
        int vb = kth(rb, lcp);
        return va < vb;
    };

    vector<int> root_id(n + 1, 0);
    vector<int> first_tok(n + 1, 0);
    for (int i = 1; i <= n; i++) first_tok[i] = tok[i];

    for (int idx = n - 1; idx >= 0; idx--) {
        int u = order[idx];

        auto &ch = child[u];
        if (!ch.empty()) {
            sort(ch.begin(), ch.end(), [&](int x, int y) {
                return less_seq(root_id[x], root_id[y], first_tok[x], first_tok[y]);
            });
        }

        int cur = new_node(tok[u]);
        for (int v : ch) {
            cur = merge(cur, root_id[v]);
        }
        root_id[u] = cur;
    }

    vector<long long> ans;
    ans.reserve(n);
    vector<int> stack2;
    stack2.reserve(n);
    stack2.push_back(1);
    while (!stack2.empty()) {
        int u = stack2.back();
        stack2.pop_back();
        ans.push_back(a[u]);
        auto &ch = child[u];
        for (int i = (int)ch.size() - 1; i >= 0; i--) stack2.push_back(ch[i]);
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}