#5463. 「eJOI2025」收集钻石 题解

问题分析

我们需要在图中找到一条长度为 $K$ 的路径，使得路径的钻石序列字典序最大，并求总钻石数。

关键约束：

• $K$ 可达 $10^9$，不能直接模拟
• 内存限制只有 4MB
• 需要高效处理极大 $K$

核心观察

字典序贪心选择

对于第 $i$ 步，我们选择当前能走的边中钻石值最大的：

1. 如果有多个相同最大值，考虑下一步能得到的最大值
2. 这需要向前看多步来决定当前选择

状态周期性

由于图大小有限 ($N \leq 2000$)，路径选择会出现循环：

• 经过足够多步后，路径会进入一个循环
• 循环长度不超过 $N$

算法思路

步骤1：预处理最优转移

对于每个节点 $u$，我们想知道：

• 从 $u$ 出发走 $t$ 步能得到的最大字典序路径
• 由于 $K$ 很大，需要快速幂思想

定义 $next[u][t]$ = 从 $u$ 出发走 $2^t$ 步后到达的节点
定义 $sum[u][t]$ = 从 $u$ 出发走 $2^t$ 步获得的总钻石

步骤2：逐位确定路径

使用二进制拆分处理 $K$：

• 从高位到低位考虑 $K$ 的二进制位
• 对于每个二进制位，决定这一步走多远

步骤3：字典序比较

比较两条路径的字典序时：

• 比较第一步的钻石值
• 如果相同，比较第二步，依此类推
• 这需要能快速查询路径上任一步的值

具体实现

数据结构设计

由于内存限制，不能存储所有 $next[u][t]$ 和 $sum[u][t]$。 需要更节省内存的方法：

#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
const int LOGK = 31; // 2^30 > 10^9

struct Edge {
    int to, diamonds;
};

vector<Edge> graph[MAXN];

// 倍增数组
int nxt[MAXN][LOGK];
long long total[MAXN][LOGK];

void preprocess(int N, int K) {
    // 初始化第一步
    for (int u = 0; u < N; u++) {
        // 选择钻石值最大的边
        int best_v = -1, best_d = -1;
        for (auto& e : graph[u]) {
            if (e.diamonds > best_d || 
               (e.diamonds == best_d && compare_paths(e.to, best_v, K-1) > 0)) {
                best_d = e.diamonds;
                best_v = e.to;
            }
        }
        nxt[u][0] = best_v;
        total[u][0] = best_d;
    }
    
    // 倍增预处理
    for (int t = 1; t < LOGK; t++) {
        for (int u = 0; u < N; u++) {
            int mid = nxt[u][t-1];
            nxt[u][t] = nxt[mid][t-1];
            total[u][t] = total[u][t-1] + total[mid][t-1];
        }
    }
}

字典序比较函数

// 比较从u和v出发走len步的路径字典序
int compare_paths(int u, int v, int len) {
    if (len == 0) return 0;
    
    // 比较第一步
    int d1 = get_first_diamond(u);
    int d2 = get_first_diamond(v);
    if (d1 != d2) return d1 - d2;
    
    // 第一步相同，比较剩余路径
    return compare_paths(nxt[u][0], nxt[v][0], len-1);
}

int get_first_diamond(int u) {
    int best = 0;
    for (auto& e : graph[u]) {
        best = max(best, e.diamonds);
    }
    return best;
}

主计算函数

long long calculate_diamonds(int N, int M, int K,
    vector<int> u, vector<int> v, vector<int> d) {
    
    // 建图
    for (int i = 0; i < M; i++) {
        graph[u[i]].push_back({v[i], d[i]});
    }
    
    // 预处理倍增数组
    preprocess(N, K);
    
    // 寻找最佳起点
    int start = find_best_start(N, K);
    
    // 计算总钻石数
    long long ans = 0;
    int current = start;
    int remaining = K;
    
    for (int t = LOGK-1; t >= 0; t--) {
        if (remaining >= (1 << t)) {
            ans += total[current][t];
            current = nxt[current][t];
            remaining -= (1 << t);
        }
    }
    
    return ans;
}

寻找最佳起点

int find_best_start(int N, int K) {
    int best_start = 0;
    for (int u = 1; u < N; u++) {
        if (compare_paths(u, best_start, K) > 0) {
            best_start = u;
        }
    }
    return best_start;
}

复杂度分析

• 预处理：$O(N \cdot M \cdot \log K)$
• 查询：$O(\log K)$
• 空间：$O(N \log K)$，对于 $N=2000$ 约 $2000 \times 31 \times 16 \approx 1MB$