专栏文章

题解：P14372 [JOISC 2018] 比太郎的聚会 / Bitaro's Party

LLostKeyToReach
P14372题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindd8d9
此快照首次捕获于
2025/12/02 00:34
3 个月前
此快照最后确认于
2025/12/02 00:34
3 个月前
查看原文
由于 Si<EiS_i < E_i，所以说这是一张拓扑序为 1∼N1 \sim N 的 DAG，那么就不用跑拓扑排序了。设 fxf_x 为以 xx 为终点，所有空闲点里面到终点距离的最大值，有转移方程：
fx=max⁡y∈pre(x){fy}+1.f_x = \max_{y \in \text{pre}(x)} \{ f_y \} + 1.
这样太慢了。由于 ∑Yi≤105\sum Y_i \le 10^5，考虑根号分治。对于 Yi≥BY_i \ge B 的部分跑上述 dp，对于 Yi<BY_i < B 的部分，我们提前预处理出 SxS_x 表示终点为 xx，到 xx 的距离前 BB 大的点集，每次询问的时候直接在里面找就行了。
CPP
void merge(int y, int x) {
    // merge y, x + 1
    std::vector<pii> fin, t = ok[x];
    std::vector<int> u;
    for (auto& [a, b] : t) a += 1;
#define try(x) if (!vis[x.se]) { \
    vis[x.se] = 1, fin.eb(x), u.eb(x.se); \
    }
    int i = 0, j = 0;
    while (i < sz(ok[y]) && j < sz(t) && sz(fin) < B) {
        if (ok[y][i] <= t[j]) {try(t[j]); ++j;}
        else {try(ok[y][i]); ++i;}
    }
    while (i < sz(ok[y]) && sz(fin) < B) {
        try(ok[y][i]); ++i;
    }
    while (j < sz(t) && sz(fin) < B) {
        try(t[j]); ++j;
    }
    ok[y].swap(fin);
    for (auto& v : u) vis[v] = 0;
}

for (int i = 1; i <= n; ++i) { 
    for (auto& y : adj[i]) merge(i, y);
    if (sz(ok[i]) < B) ok[i].eb(0, i);
}
时间复杂度 O((N+M+Q)B+(N+M)×VB)\mathcal O((N + M + Q)B + (N + M) \times \frac{V}{B})，空间复杂度 O(NB+M)\mathcal O(NB + M)。我建议 BB 取 100∼128100 \sim 128 的样子，因为取到 n\sqrt n 会 MLE。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...