VP 2024 江西省赛

比赛链接

Problems	Status	Notes
A. Maliang Learning Painting	○
B. Magic Leeks
C. Liar	○
D. Magic LCM	○	数论
E. Magic Subsequence
F. The Ropeways
G. Multiples of 5	○
H. Convolution	○
I. Neuvillette Circling
J. Magic Mahjong	○
K. Magic Tree	○
L. Campus	○	最短路

D

题意
给你一个长 $n$ 的序列 $v_i$ ，每次可以选择两个位置，把其中一个位置变为它们的最大公约数，另一个变为最小公倍数，求无限次操作后最大的序列之和。

题解
对于两个数 $x<y$ ，若它们存在公因子 $k$ ，那么有 $\frac{x}{k}+y \times k>y \times(k-1)+y>x+y$ ，因此操作一定是优的。
考虑操作的本质，对于某个 $x$ 和 $y$ 的共同质因子 $p$ ，假设 $p^c$ 和 $p^d$ 分别是这两个数拥有的最大 $p$ 的次幂的因子，那么操作本质上是令最小公倍数拥有 $p^{\max (c, d)}$ ，最大公约数拥有 $p^{\min (c, d)}$ 。
那么本题独立考虑每个质因子的次幂，将它们排序，并把更大的次幂放在更右端即可。
实现时使用筛法筛出每个数的最小质因子进行分解，单次分解复杂度是 $\log$ 的。考虑每个数最终最多分解出 7 个质因子，那么最多有 $7 n$ 个数可能参与排序，由于非常不满因此排序可以使用 sort，也可以使用桶排序次幂。

L

题意
一个 $n$ 个点 $m$ 条边的无向图，每个节点上有 $a_i$ 个人。 $n$ 个节点中有 $k$ 个节点为出口，每个出口有一个开放时间 $\left[l_i, r_i\right]$ 。求第 $1 \sim T$ 时刻所有人到最近的开放出口的路径长度之和。

解法
首先考虑一个简单版本，所有出口的开放时间无限。
那么就是一个简单的多源最短路的问题，可以建一个超级源点，超级源点到 $k$ 个出口节点连长度为 0 的边。
对于开放时间这个限制，一个朴素的做法就是，对于每个时刻找出对应开放的出口节点来做多源最短路。把 $k$ 个出口节点的开放时间看作时间轴上的 $k$ 条线段，容易发现不同覆盖情况的时间点不超过 $2 \times k$ 。对这不超过 $2 \times k$ 种情况做多源最短路即可。
时间复杂度：$O(k n \log n)$

关键点在于对线段覆盖的观察。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

struct Node {
    int d, id;
    bool friend operator< (Node a, Node b) {
        return a.d > b.d;
    }
};

void solve() {
    int n = read();
    int m = read();
    int k = read();
    int T = read();

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

    vector<vector<pii>> g(n + 1);
    vector<vector<int>> st(T + 2), ed(T + 2);
    vector<int> open(n + 1);

    for (int i = 1; i <= k; i++) {
        int p = read();
        int l = read(), r = read();
        // open[p] = {l, r};
        g[0].eb(p, 0);
        g[p].eb(0, 0);
        st[l].eb(p);
        ed[r + 1].eb(p);
    }
    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        int w = read();
        g[u].eb(v, w);
        g[v].eb(u, w);
    }

    auto dijkstra = [&](int s) {
        vector<int> dis(n + 1, inf);
        vector<int> vis(n + 1);
        dis[s] = 0;
        std::priority_queue<Node> q; q.ep(0, s);
        while (!q.empty()) {
            auto [d, u] = q.top(); q.pop();
            if (vis[u]) continue; vis[u] = 1;
            for (auto [v, w] : g[u]) {
                if (u == 0 and !open[v]) continue;
                if (v == 0 and !open[u]) continue;
                if (dis[v] > d + w) {
                    dis[v] = d + w;
                    q.ep(dis[v], v);
                }
            }
        }
        return dis;
    };

    int res = -1;
    for (int i = 1; i <= T; i++) {
        for (auto x : ed[i]) open[x] = 0;
        for (auto x : st[i]) open[x] = 1;

        if (ed[i].empty() and st[i].empty()) {

        } else {
            auto dis = dijkstra(0);
            res = 0;
            for (int i = 1; i <= n; i++) {
                res += dis[i] * a[i];
                if (dis[i] == inf) { res = -1; break; }
            }
        }
        
        cout << res << '\n';
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}