做内衣的网站好,山西省城乡住房和建设厅网站首页,短视频素材免费下载网站,信阳做房产哪个网站好用更多 CSP 认证考试题目题解可以前往#xff1a;CSP-CCF 认证考试真题题解 原题链接#xff1a; 202212-5 星际网络
时间限制#xff1a; 5.0s 内存限制#xff1a; 512.0MB
问题描述 23333 23333 23333 年#xff0c;在经过长时间的建设后#xff0c;一个庞大的星际网络… 更多 CSP 认证考试题目题解可以前往CSP-CCF 认证考试真题题解 原题链接 202212-5 星际网络
时间限制 5.0s 内存限制 512.0MB
问题描述 23333 23333 23333 年在经过长时间的建设后一个庞大的星际网络终于初具规模。星际网络共接入了 n n n 颗星球由 m m m 颗中继卫星来实现星球之间的互联互通。所有星球之间的通信都必须经由一颗或多颗中继卫星来实现星球本身也可以起到中继的作用如果两颗星球的距离很远数据可以沿“星球——中继卫星——星球——中继卫星——…——星球”的模式进行传输。
对于每一颗中继卫星而言可以与多颗距离上较为接近的星球通信但由于卫星结构的设计原因通信只能单向进行。具体而言第 i i i 颗中继卫星可以接收编号在 [ l 1 i , r 1 i ] [l_{1i},r_{1i}] [l1i,r1i] 范围内的星球发送来的数据并向编号在 [ l 2 i , r 2 i ] [l_{2i},r_{2i}] [l2i,r2i] 范围内的星球发送数据。
数据在星际之间传输的延迟当然是惊人的。为简单起见我们假设这一延迟只由数据经过的中继卫星决定即数据从不同的星球发出经同一个中继卫星到达不同的星球所需的延迟时间总是相同的。对于第 i i i 颗中继卫星数据经由该中继卫星传输所需的延迟时间约为 T i T_i Ti 秒。由于这个数字实在太过巨大而且对于星际间通信的延迟估计总是充满了各种不准确因素我们只关心其若干位有效数字具体而言将给出二元组 ( a i , b i ) (a_i,b_i) (ai,bi) 表示 T i a i × 2 b i T_ia_i\times2^{b_i} Tiai×2bi。我们假设数据在其他位置的延迟均可忽略。实际传输中数据从源星球发出经由很多颗中继卫星和星球最终到达目的星球则总延迟为过程中经过的所有中继卫星的延迟之和。
数据从某个星球出发到达另一个星球其在中继卫星和星球之间所经过的传输路径可能是多种多样的。与普通的计算机网络类似我们需要设计相应的路由算法来选择合适的传输路径。一种直观的方案是最小延迟原则即数据总是会选择总延迟时间最小的传输路径。
星际网络建成后工程师们希望通过类似于计算机网络中ping的方法来测试该网络。从星球A向星球B发起一次ping的经过如下首先从星球A发送请求数据数据经星际网络传输至星球B星球B随即发送回复数据经星际网络传输至星球A星球A计算从它发出请求到收到回复的所经时间称为此次ping的响应时间。如果星际网络结构有缺陷使得星球A发出的请求无法到达星球B或星球B发出的回复无法到达星球A则星球A在等待足够长时间后会得到“请求超时”的结果。
现在需要从 1 1 1 号星球向其他所有星球依次发起一次ping假设所有数据的传输均遵循最小延迟原则请你计算出每次ping的响应时间。
输入格式
从标准输入读入数据。
第 1 1 1 行 2 2 2 个正整数 n , m n,m n,m。
接下来 m m m 行每行 6 6 6 个非负整数 l 1 i , r 1 i , l 2 i , r 2 i , a i , b i l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i l1i,r1i,l2i,r2i,ai,bi描述一颗中继卫星具体含义如上所述。
输出格式
输出到标准输出中。
输出一行 n − 1 n-1 n−1 个整数第 i i i 个整数表示星球 1 1 1 向星球 i 1 i1 i1 发起ping的响应时间对 1 0 9 7 10^97 1097 取模后输出。
特别地如果某次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 输出
7 6 6 -1样例说明
从 1 1 1 号星球到 2 2 2 号星球的请求数据最小延迟为 4 4 4 2 2 2 号星球的回复数据最小延迟为 3 3 3。
从 1 1 1 号星球到 3 3 3 号星球的请求数据最小延迟为 4 4 4 3 3 3 号星球的回复数据最小延迟为 2 2 2。
从 1 1 1 号星球到 4 4 4 号星球的请求数据最小延迟为 5 5 5 4 4 4 号星球的回复数据最小延迟为 1 1 1。
从 1 1 1 号星球到 5 5 5 号星球的请求数据最小延迟为 6 6 6 5 5 5 号星球的回复数据无法到达 1 1 1 号星球。
样例 2 输入
3 2
1 2 1 2 999999999 34
2 3 2 3 987654321 12样例 2 输出
122094981 986235983数据范围
对于所有数据 n ≤ 1 0 5 , m ≤ 1 0 5 , 1 ≤ l 1 i ≤ r 1 i ≤ n , 1 ≤ l 2 i ≤ r 2 i ≤ n , 1 ≤ a i ≤ 1 0 9 , 0 ≤ b i ≤ 1 0 5 n\leq 10^5, m \leq 10^5, 1\leq l_{1i} \leq r_{1i} \leq n, 1\leq l_{2i} \leq r_{2i} \leq n, 1 \leq a_i \leq 10^9, 0 \leq b_i \leq 10^5 n≤105,m≤105,1≤l1i≤r1i≤n,1≤l2i≤r2i≤n,1≤ai≤109,0≤bi≤105。
测试点编号$n \leq $$m \leq $ b i ≤ b_i \leq bi≤特殊性质 1 1 1 10 10 10 10 10 10 0 0 0无 2 ∼ 3 2 \sim 3 2∼3 100 100 100 100 100 100 0 0 0无 4 ∼ 5 4 \sim 5 4∼5 1000 1000 1000 1000 1000 1000 0 0 0无 6 ∼ 8 6 \sim 8 6∼8 1 0 5 10^5 105 1 0 5 10^5 105 0 0 0 l 1 i r 1 i , l 2 i r 2 i l_{1i}r_{1i}, l_{2i}r_{2i} l1ir1i,l2ir2i 9 ∼ 10 9 \sim 10 9∼10 1 0 5 10^5 105 1 0 5 10^5 105 0 0 0 l 1 i r 1 i l_{1i}r_{1i} l1ir1i 11 ∼ 13 11 \sim 13 11∼13 1 0 5 10^5 105 1 0 5 10^5 105 0 0 0无 14 ∼ 15 14 \sim 15 14∼15 100 100 100 100 100 100 100 100 100无 16 ∼ 17 16 \sim 17 16∼17 1000 1000 1000 1000 1000 1000 1000 1000 1000无 18 ∼ 20 18 \sim 20 18∼20 1 0 5 10^5 105 1 0 5 10^5 105 1 0 5 10^5 105 l 1 i r 1 i , l 2 i r 2 i l_{1i}r_{1i}, l_{2i}r_{2i} l1ir1i,l2ir2i 21 ∼ 22 21 \sim 22 21∼22 1 0 5 10^5 105 1 0 5 10^5 105 1 0 5 10^5 105 l 1 i r 1 i l_{1i}r_{1i} l1ir1i 23 ∼ 25 23 \sim 25 23∼25 1 0 5 10^5 105 1 0 5 10^5 105 1 0 5 10^5 105无 52 分题解测试点 1~13
前置知识线段树优化建图 - OI Wiki。
前 13 13 13 个测试点的 b 0 b0 b0即边权的范围是 [ 1 , 1 0 9 ] [1,10^9] [1,109]直接用 long long 做就行了。
先建立好出树和入树对于给定的一条边 l 1 i , r 1 i , l 2 i , r 2 i , a i , b i l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i l1i,r1i,l2i,r2i,ai,bi新建一个节点 x x x建立从出树中在 [ l 1 i , r 1 i ] [l_{1i},r_{1i}] [l1i,r1i] 中且其父节点不在该区间中的节点编号到 x x x 的一条边和从 x x x 到入树中在 [ l 2 i , r 2 i ] [l_{2i},r_{2i}] [l2i,r2i] 中且其父节点不在该区间中的节点编号的一条边。对建好的图跑以 1 1 1 号点为源点的 Dijkstra 算法即可求出从 1 1 1 号点到其他点的最短距离。
重新建立一张图所有边的方向调换。即在建立好出入和入树后对于给定的一条边 l 1 i , r 1 i , l 2 i , r 2 i , a i , b i l_{1i},r_{1i},l_{2i},r_{2i},a_i,b_i l1i,r1i,l2i,r2i,ai,bi新建一个节点 x x x建立从出树中在 [ l 2 i , r 2 i ] [l_{2i},r_{2i}] [l2i,r2i] 中且其父节点不在该区间中的节点编号到 x x x 的一条边和从 x x x 到入树中在 [ l 1 i , r 1 i ] [l_{1i},r_{1i}] [l1i,r1i] 中且其父节点不在该区间中的节点编号的一条边。对建好的图跑以 1 1 1 号点为源点的 Dijkstra 算法即可求出从其他点到 1 1 1 号点的最短距离。
将两个距离相加即为答案注意取模和不可到达的情况。
时间复杂度 O ( n log n m log n log ( m log n ) ) \mathcal{O}(n\log nm\log n\log(m\log n)) O(nlognmlognlog(mlogn))。
52 分参考代码718ms87.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 pairint, int
#ifdef DEBUG#include debug.h
#else#define dbg(...) void(0)
#endifconst 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;
vectorpairint, 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);}vectorint 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);}
};
SegmentTreeint T;i64 dis[N 2], ans[N];
bool vis[N 2];
void dijkstra() {mem(dis, 0x3f); mem(vis, 0);dis[1] 0;priority_queuepairi64, int, vectorpairi64, int, greaterpairi64, 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 LOCALfreopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.in, r, stdin);freopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.out, w, stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int Case 1;//cin Case;while (Case--) work();return 0;
}
/*_____ _ _ _ __ __| _ \ | | | | | | \ \ / /| |_| | | | | | | | \ \/ /| ___/ | | | | _ | | } {| | | |_| | | |_| | / /\ \|_| \_____/ \_____/ /_/ \_\
*/ 68 分题解测试点 1~17
在 52 52 52 分题解中存储距离用的是 long long但是在 14 ∼ 17 14\sim 17 14∼17 中边权较大显然不行。
将 long long 换成压位高精每 64 64 64 个二进制位压成一位这样压位首先可以用 unsigned long long 存储其次也可以较为方便的处理 × 2 b \times 2^b ×2b 的操作使用 std::arrayunsigned long long, M 存储[0] 为最低位[M - 1] 为最高位。由于最大的距离大约为 1000 × 1 0 9 × 2 1000 ≈ ( 2 64 ) 16.248 1000\times 10^9\times 2^{1000}\approx(2^{64})^{16.248} 1000×109×21000≈(264)16.248高精的位数选取 M 17 M17 M17 位。
重载一下用到的运算符 。
最后输出答案 x x x 前只要计算得出 ∑ i 0 M − 1 x i × ( 2 64 ) i m o d 1 0 9 7 \sum\limits_{i0}^{M-1}x_i\times(2^{64})^i\mod 10^97 i0∑M−1xi×(264)imod1097 即可。
时间复杂度 O ( 17 ( n log n m log n log ( m log n ) ) ) \mathcal{O}(17(n\log nm\log n\log(m\log n))) O(17(nlognmlognlog(mlogn)))。
68 分参考代码1.937s455.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 pairint, int
#ifdef DEBUG#include debug.h
#else#define dbg(...) void(0)
#endifconst 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 arrayui64, 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;
vectorpairint, 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());}vectorint 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);}
};
SegmentTreeint 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_queuenode 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 LOCALfreopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.in, r, stdin);freopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.out, w, stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int Case 1;//cin Case;while (Case--) work();return 0;
}
/*_____ _ _ _ __ __| _ \ | | | | | | \ \ / /| |_| | | | | | | | \ \/ /| ___/ | | | | _ | | } {| | | |_| | | |_| | / /\ \|_| \_____/ \_____/ /_/ \_\
*/100 分题解无
想不出来也没找到官方题解太菜了。 关于代码的亿点点说明 代码的主体部分位于 void work() 函数中另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ... 是用来开启 O2、O3 等优化加快代码速度。中间一大堆 #define ... 是我习惯上的一些宏定义用来加快代码编写的速度。debug.h 头文件是我用于调试输出的代码没有这个头文件也可以正常运行前提是没定义 DEBUG 宏在程序中如果看到 dbg(...) 是我中途调试的输出的语句可能没删干净但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步加快输入 cin 输出 cout 速度这个输入输出流的速度很慢。在小数据量无所谓但是在比较大的读入时建议加这句话避免读入输出超时。如果记不下来可以换用 scanf 和 printf但使用了这句话后cin 和 scanf、cout 和 printf 不能混用。将 main 函数和 work 函数分开写纯属个人习惯主要是为了多组数据。
