CCF-CSP认证考试 202212-5 星际网络 52/68分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

---

原题链接： 202212-5 星际网络

时间限制： 5.0s
内存限制： 512.0MB

问题描述

$23333$ 年，在经过长时间的建设后，一个庞大的星际网络终于初具规模。星际网络共接入了 $n$ 颗星球，由 $m$ 颗中继卫星来实现星球之间的互联互通。所有星球之间的通信都必须经由一颗或多颗中继卫星来实现，星球本身也可以起到中继的作用，如果两颗星球的距离很远，数据可以沿“星球——中继卫星——星球——中继卫星——…——星球”的模式进行传输。

对于每一颗中继卫星而言，可以与多颗距离上较为接近的星球通信，但由于卫星结构的设计原因，通信只能单向进行。具体而言，第 $i$ 颗中继卫星可以接收编号在 $[l_{1i},r_{1i}]$ 范围内的星球发送来的数据，并向编号在 $[l_{2i},r_{2i}]$ 范围内的星球发送数据。

数据在星际之间传输的延迟当然是惊人的。为简单起见，我们假设这一延迟只由数据经过的中继卫星决定，即数据从不同的星球发出，经同一个中继卫星，到达不同的星球，所需的延迟时间总是相同的。对于第$i$ 颗中继卫星，数据经由该中继卫星传输所需的延迟时间约为 $T_i$ 秒。由于这个数字实在太过巨大，而且对于星际间通信的延迟估计总是充满了各种不准确因素，我们只关心其若干位有效数字，具体而言将给出二元组 $(a_i,b_i)$ ，表示 $T_i=a_i\times 2^{b_i}$。我们假设数据在其他位置的延迟均可忽略。实际传输中，数据从源星球发出，经由很多颗中继卫星和星球最终到达目的星球，则总延迟为过程中经过的所有中继卫星的延迟之和。

数据从某个星球出发到达另一个星球，其在中继卫星和星球之间所经过的传输路径可能是多种多样的。与普通的计算机网络类似，我们需要设计相应的路由算法来选择合适的传输路径。一种直观的方案是最小延迟原则，即数据总是会选择总延迟时间最小的传输路径。

星际网络建成后，工程师们希望通过类似于计算机网络中ping的方法来测试该网络。从星球A向星球B发起一次ping的经过如下：首先从星球A发送请求数据，数据经星际网络传输至星球B，星球B随即发送回复数据，经星际网络传输至星球A，星球A计算从它发出请求到收到回复的所经时间，称为此次ping的响应时间。如果星际网络结构有缺陷，使得星球A发出的请求无法到达星球B，或星球B发出的回复无法到达星球A，则星球A在等待足够长时间后会得到“请求超时”的结果。

现在需要从 $1$ 号星球向其他所有星球依次发起一次ping，假设所有数据的传输均遵循最小延迟原则，请你计算出每次ping的响应时间。

输入格式

从标准输入读入数据。

第 $1$ 行：$2$ 个正整数 $n,m$。

接下来 $m$ 行：每行 $6$ 个非负整数 $l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i$，描述一颗中继卫星，具体含义如上所述。

输出格式

输出到标准输出中。

输出一行，$n-1$ 个整数，第 $i$ 个整数表示星球 $1$ 向星球 $i+1$ 发起ping的响应时间，对 $10^9+7$ 取模后输出。

特别地，如果某次ping的结果为请求超时，输出 -1。

样例 1 输入

5 5
1 2 2 3 1 2
2 2 1 1 3 0
2 3 4 5 1 1
3 3 4 4 1 0
4 4 1 2 1 0
1
2
3
4
5
6

样例 1 输出

7 6 6 -1
1

样例说明

从 $1$ 号星球到 $2$ 号星球的请求数据最小延迟为 $4$，$2$ 号星球的回复数据最小延迟为 $3$。

从 $1$ 号星球到 $3$ 号星球的请求数据最小延迟为 $4$，$3$ 号星球的回复数据最小延迟为 $2$。

从 $1$ 号星球到 $4$ 号星球的请求数据最小延迟为 $5$，$4$ 号星球的回复数据最小延迟为 $1$。

从 $1$ 号星球到 $5$ 号星球的请求数据最小延迟为 $6$，$5$ 号星球的回复数据无法到达 $1$ 号星球。

样例 2 输入

3 2
1 2 1 2 999999999 34
2 3 2 3 987654321 12
1
2
3

样例 2 输出

122094981 986235983
1

数据范围

对于所有数据，$n\le 10^5,m\le 10^5,1\le l_{1i}\le r_{1i}\le n,1\le l_{2i}\le r_{2i}\le n,1\le a_i\le 10^9,0\le b_i\le 10^5$。

---

52 分题解（测试点 1~13）

前置知识：线段树优化建图 - OI Wiki。

前 $13$ 个测试点的 $b=0$，即边权的范围是 $[1,10^9]$，直接用 long long 做就行了。

先建立好出树和入树，对于给定的一条边 $l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i$，新建一个节点 $x$，建立从出树中在 $[l_{1i},r_{1i}]$ 中且其父节点不在该区间中的节点编号到 $x$ 的一条边，和从 $x$ 到入树中在 $[l_{2i},r_{2i}]$ 中且其父节点不在该区间中的节点编号的一条边。对建好的图跑以 $1$ 号点为源点的 Dijkstra 算法即可求出从 $1$ 号点到其他点的最短距离。

重新建立一张图，所有边的方向调换。即在建立好出入和入树后，对于给定的一条边 $l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i$，新建一个节点 $x$，建立从出树中在 $[l_{2i},r_{2i}]$ 中且其父节点不在该区间中的节点编号到 $x$ 的一条边，和从 $x$ 到入树中在 $[l_{1i},r_{1i}]$ 中且其父节点不在该区间中的节点编号的一条边。对建好的图跑以 $1$ 号点为源点的 Dijkstra 算法即可求出从其他点到 $1$ 号点的最短距离。

将两个距离相加即为答案，注意取模和不可到达的情况。

时间复杂度：$\mathcal{O}(n\log n+m\log n\log (m\log n))$。

52 分参考代码（718ms，87.85MB）

/*
    Created by Pujx on 2024/3/29.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
//const int mod = 998244353;
const int mod = 1e9 + 7;
template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int l1[N], r1[N], l2[N], r2[N], a[N], b[N];
int n, m, t, k, q, cnt;
vector<pair<int, i64>> g[N << 2];

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r, lson, rson; } tr[N << 2];
    void build(int& s, int l, int r, bool io) {
        s = ++cnt;
        tr[s].l = l, tr[s].r = r;
        if (l == r) {
            if (!io) g[l].emplace_back(cnt, 0);
            else g[cnt].emplace_back(l, 0);
            return;
        }
        int mid = l + r >> 1;
        if (l <= mid) build(tr[s].lson, l, mid, io);
        if (mid < r) build(tr[s].rson, mid + 1, r, io);
        if (!io) g[tr[s].lson].emplace_back(s, 0), g[tr[s].rson].emplace_back(s, 0);
        else g[s].emplace_back(tr[s].lson, 0), g[s].emplace_back(tr[s].rson, 0);
    }
    vector<int> v[2];
    void query(int s, int l, int r, bool io) {
        if (l <= tr[s].l && tr[s].r <= r) return v[io].emplace_back(s), void();
        int mid = tr[s].l + tr[s].r >> 1;
        if (l <= mid) query(tr[s].lson, l, r, io);
        if (mid < r) query(tr[s].rson, l, r, io);
    }
};
SegmentTree<int> T;

i64 dis[N << 2], ans[N];
bool vis[N << 2];
void dijkstra() {
    mem(dis, 0x3f); mem(vis, 0);
    dis[1] = 0;
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto tem : g[u]) {
            int v = tem.first; i64 w = tem.second;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
}

void work() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> l1[i] >> r1[i] >> l2[i] >> r2[i] >> a[i] >> b[i];

    int rto, rti;
    auto calc = [&] (int* l1, int* r1, int* l2, int* r2) {
        for (int i = 1; i <= cnt; i++) g[i].clear();
        cnt = n;
        T.build(rto, 1, n, false);
        T.build(rti, 1, n, true);

        for (int i = 1; i <= m; i++) {
            T.v[0].clear(), T.v[1].clear();
            T.query(rto, l1[i], r1[i], 0);
            T.query(rti, l2[i], r2[i], 1);
            ++cnt;
            for (auto v : T.v[0]) g[v].emplace_back(cnt, a[i] * ksm(2ll, b[i]));
            for (auto v : T.v[1]) g[cnt].emplace_back(v, 0);
        }
        dijkstra();
        for (int i = 1; i <= n; i++) ans[i] += dis[i];
    };
    calc(l1, r1, l2, r2); calc(l2, r2, l1, r1);

    for (int i = 2; i <= n; i++) cout << (ans[i] < INF ? ans[i] % mod : -1) << " \n"[i == n];
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

---

68 分题解（测试点 1~17）

在 $52$ 分题解中，存储距离用的是 long long，但是在 $14\sim 17$ 中边权较大，显然不行。

将 long long 换成压位高精，每 $64$ 个二进制位压成一位（这样压位首先可以用 unsigned long long 存储，其次也可以较为方便的处理 $\times 2^b$ 的操作），使用 std::array<unsigned long long, M> 存储，[0] 为最低位，[M - 1] 为最高位。由于最大的距离大约为 $1000\times 10^9\times 2^{1000}\approx (2^{64}{)}^{16.248}$，高精的位数选取 $M=17$ 位。

重载一下用到的运算符 +，<，>。

最后输出答案 $x$ 前，只要计算得出 $\sum _{i=0}^{M-1}{x}_i\times (2^{64}{)}^i\mathrm{mod}10^9+7$ 即可。

时间复杂度：$\mathcal{O}(17(n\log n+m\log n\log (m\log n)))$。

68 分参考代码（1.937s，455.2MB）

/*
    Created by Pujx on 2024/3/29.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
const int M = 17;
//const int mod = 998244353;
const int mod = 1e9 + 7;
template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

using BigInt = array<ui64, M>;
const i128 MOD = (i128)1 << 64;
int pw[M];
BigInt operator + (const BigInt& a, const BigInt& b) {
    BigInt ans;
    i128 g = 0;
    for (int i = 0; i < M; i++) {
        g = g + a[i] + b[i];
        ans[i] = g >= MOD ? g - MOD : g;
        g = g >= MOD;
    }
    return ans;
}
BigInt init(const i64& a, const int& b) {
    int j = b % 64, i = b / 64;
    i128 val = (i128)a << j;
    BigInt ans = BigInt();
    while (val) {
        ans[i++] = val % MOD;
        val >>= 64;
    }
    return ans;
}
int chg(const BigInt& a) {
    if (a[M - 1] == INF) return -1;
    i64 ans = 0;
    for (int i = 0; i < M; i++)
        ans = (ans + a[i] % mod * pw[i]) % mod;
    return ans;
}
bool operator < (const BigInt& a, const BigInt& b) {
    for (int i = M - 1; ~i; i--) {
        if (a[i] < b[i]) return true;
        else if (a[i] > b[i]) return false;
    }
    return false;
}
bool operator > (const BigInt& a, const BigInt& b) {
    return b < a;
}

int l1[N], r1[N], l2[N], r2[N], a[N], b[N];
int n, m, t, k, q, cnt;
vector<pair<int, BigInt>> g[N << 2];

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r, lson, rson; } tr[N << 2];
    void build(int& s, int l, int r, bool io) {
        s = ++cnt;
        tr[s].l = l, tr[s].r = r;
        if (l == r) {
            if (!io) g[l].emplace_back(cnt, BigInt());
            else g[cnt].emplace_back(l, BigInt());
            return;
        }
        int mid = l + r >> 1;
        if (l <= mid) build(tr[s].lson, l, mid, io);
        if (mid < r) build(tr[s].rson, mid + 1, r, io);
        if (!io) g[tr[s].lson].emplace_back(s, BigInt()), g[tr[s].rson].emplace_back(s, BigInt());
        else g[s].emplace_back(tr[s].lson, BigInt()), g[s].emplace_back(tr[s].rson, BigInt());
    }
    vector<int> v[2];
    void query(int s, int l, int r, bool io) {
        if (l <= tr[s].l && tr[s].r <= r) return v[io].emplace_back(s), void();
        int mid = tr[s].l + tr[s].r >> 1;
        if (l <= mid) query(tr[s].lson, l, r, io);
        if (mid < r) query(tr[s].rson, l, r, io);
    }
};
SegmentTree<int> T;

struct node {
    BigInt dis; int u;
    bool operator < (const node& t) const {
        return dis > t.dis;
    }
};

BigInt dis[N << 2];
int ans[N];
bool vis[N << 2];
void dijkstra() {
    for (int i = 1; i <= cnt; i++) dis[i] = BigInt(), dis[i][M - 1] = INF, vis[i] = false;
    dis[1][M - 1] = 0;
    priority_queue<node> pq;
    pq.push({dis[1], 1});
    while (!pq.empty()) {
        int u = pq.top().u; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto tem : g[u]) {
            int v = tem.first; BigInt& w = tem.second;
            if (!vis[v] && dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
}

void work() {
    pw[0] = 1, pw[1] = MOD % mod;
    for (int i = 2; i < M; i++) pw[i] = 1ll * pw[i - 1] * pw[1] % mod;

    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> l1[i] >> r1[i] >> l2[i] >> r2[i] >> a[i] >> b[i];

    int rto, rti;
    auto calc = [&] (int* l1, int* r1, int* l2, int* r2) {
        for (int i = 1; i <= cnt; i++) g[i].clear();
        cnt = n;
        T.build(rto, 1, n, false);
        T.build(rti, 1, n, true);

        for (int i = 1; i <= m; i++) {
            T.v[0].clear(), T.v[1].clear();
            T.query(rto, l1[i], r1[i], 0);
            T.query(rti, l2[i], r2[i], 1);
            ++cnt;
            for (auto v : T.v[0]) g[v].emplace_back(cnt, init(a[i], b[i]));
            for (auto v : T.v[1]) g[cnt].emplace_back(v, BigInt());
        }
        dijkstra();
        for (int i = 1; i <= n; i++) {
            if (ans[i] != -1) {
                int val = chg(dis[i]);
                if (val == -1) ans[i] = -1;
                else ans[i] = (ans[i] + val) % mod;
            }
        }
    };
    calc(l1, r1, l2, r2); calc(l2, r2, l1, r1);

    for (int i = 2; i <= n; i++) cout << ans[i] << " \n"[i == n];
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

---

100 分题解（无）

想不出来，也没找到官方题解，太菜了。

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。