本文主要是介绍CCF-CSP认证考试 202212-2 训练计划 100分题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
更多 CSP 认证考试题目题解可以前往:CSP-CCF 认证考试真题题解
原题链接: 202212-2 训练计划
时间限制: 1.0s
内存限制: 512.0MB
问题背景
西西艾弗岛荒野求生大赛还有 n n n 天开幕!
问题描述
为了在大赛中取得好成绩,顿顿准备在 n n n 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 m m m 项科目的加强训练。其中第 i i i 项( 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m)科目编号为 i i i,也可简称为科目 i i i。已知科目 i i i 耗时 t i t_i ti 天,即如果从第 a a a 天开始训练科目 i i i,那么第 a + t i − 1 a + t_i - 1 a+ti−1 天就是该项训练的最后一天。
大部分科目的训练可以同时进行,即顿顿在同一天内可以同时进行多项科目的训练,但部分科目之间也存在着依赖关系。如果科目 i i i 依赖科目 j j j,那么只能在后者训练结束后,科目 i i i 才能开始训练。具体来说,如果科目 j j j 从第 a a a 天训练到第 a + t j − 1 a + t_j - 1 a+tj−1 天,那么科目 i i i 最早只能从第 a + t j a + t_j a+tj 天开始训练。还好,顿顿需要训练的 m m m 项科目依赖关系并不复杂,每项科目最多只依赖一项别的科目,且满足依赖科目的编号小于自己。那些没有任何依赖的科目,则可以从第 1 1 1 天就开始训练。
对于每一项科目,试计算:
1)最早开始时间:该科目最早可以于哪一天开始训练?
2)最晚开始时间:在不耽误参赛的前提下( n n n 天内完成所有训练),该科目最晚可以从哪一天开始训练?
n n n 天内完成所有训练,即每一项科目训练的最后一天都要满足 ≤ n \le n ≤n。需要注意,顿顿如果不能在 n n n 天内完成全部 m m m 项科目的训练,就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。
输入格式
从标准输入读入数据。
输入共三行。
输入的第一行包含空格分隔的两个正整数 n n n 和 m m m,分别表示距离大赛开幕的天数和训练科目的数量。
输入的第二行包含空格分隔的 m m m 个整数,其中第 i i i 个( 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m)整数 p i p_i pi 表示科目 i i i 依赖的科目编号,满足 0 ≤ p i < i 0 \le p_i < i 0≤pi<i; p i = 0 p_i = 0 pi=0 表示科目 i i i 无依赖。
输入的第三行包含空格分隔的 m m m 个正整数,其中第 i i i 个( 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m)数 t i t_i ti 表示训练科目 i i i 所需天数,满足 1 ≤ t i ≤ n 1 \le t_i \le n 1≤ti≤n。
输出格式
输出到标准输出中。
输出共一行或两行。
输出的第一行包含空格分隔的 m m m 个正整数,依次表示每项科目的最早开始时间。
如果顿顿可以在 n n n 天内完成全部 m m m 项科目的训练,则继续输出第二行,否则输出到此为止。
输出的第二行包含空格分隔的 m m m 个正整数,依次表示每项科目的最晚开始时间。
样例 1 输入
10 5
0 0 0 0 0
1 2 3 2 10
样例 1 输出
1 1 1 1 1
10 9 8 9 1
样例 1 说明
五项科目间没有依赖关系,都可以从第 1 1 1 天就开始训练。
10 10 10 天时间恰好可以完成所有科目的训练。其中科目 1 1 1 耗时仅 1 1 1 天,所以最晚可以拖延到第 10 10 10 天再开始训练;而科目 5 5 5 耗时 10 10 10 天,必须从第 1 1 1 天就开始训练。
样例 2 输入
10 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3
样例 2 输出
1 3 1 7 4 7 1
样例 2 说明
七项科目间的依赖关系如图所示,其中仅科目 5 5 5 无法在 10 10 10 天内完成训练。
具体来说,科目 5 5 5 依赖科目 2 2 2、科目 2 2 2 又依赖于科目 1 1 1,因此科目 5 5 5 最早可以从第 4 4 4 天开始训练。
样例 3 输入
10 5
0 1 2 3 4
10 10 10 10 10
样例 3 输出
1 11 21 31 41
子任务
70 % 70\% 70% 的测试数据满足:顿顿无法在 n n n 天内完成全部 m m m 项科目的训练,此时仅需输出一行“最早开始时间”;
全部的测试数据满足 0 < n ≤ 365 0 < n \le 365 0<n≤365 且 0 < m ≤ 100 0 < m \le 100 0<m≤100。
题解
感觉第二题不太会考拓扑,但是这题拓扑序太典了,然后也没有搜到官方的讲题视频,不知道本意是考什么,就直接写拓扑了。
对于最早开始时间:如果科目 i i i 依赖于科目 j j j,即要先训练 j j j 才能训练 i i i,那么就连一条 j → i j\to i j→i 的有向边。所有入度为 0 0 0 的科目都不存在依赖的科目,可以在第 1 1 1 天直接开始训练。其他的科目都要在其依赖的科目训练完后才能训练。执行拓扑的时候,当执行到边 j → i j\to i j→i 时,用 m n j + t j mn_j+t_j mnj+tj 更新(取最大值) m n i mn_i mni,最后即可求出最早开始时间。
求出所有科目的最早开始时间后,可以很容易求出最早结束时间为 m n + t mn+t mn+t,将其与 n n n 进行判断,如果大于 n n n 的话,就无法在 n n n 天内训练完 m m m 个科目,可以直接退出。
对于最晚开始时间:考虑反图,即如果科目 i i i 依赖于科目 j j j,即要先训练 j j j 才能训练 i i i,那么就连一条 i → j i\to j i→j 的有向边。所有入度为 0 0 0 的科目由于没有被依赖的科目,都可以在最后一刻完成,即 m x i = n − t i + 1 mx_i=n-t_i+1 mxi=n−ti+1。其他的科目都要在其被依赖科目的最晚开始时间前完成训练。执行拓扑的时候,当执行到边 i → j i\to j i→j 时,用 m x i − t j mx_i-t_j mxi−tj 更新(取最小值) m x j mx_j mxj,最后即可求出最晚开始时间。
时间复杂度: O ( m ) \mathcal{O}(m) O(m)。
参考代码(15ms,12.64MB)
/*Created by Pujx on 2024/3/25.
*/
#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)
#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 a[N];
int n, m, t, k, q;vector<int> g[N], ginv[N];
int in[N], out[N], mn[N], mx[N];void work() {cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> t;if (!t) continue;g[t].emplace_back(i), in[i]++;ginv[i].emplace_back(t), out[t]++;}cinarr(a, m);queue<int> q;for (int i = 1; i <= m; i++)if (!in[i]) mn[i] = 1, q.push(i);int x = 0;while (!q.empty()) {int u = q.front(); q.pop();for (auto v : g[u]) {mn[v] = max(mn[v], mn[u] + a[u]);if (!--in[v]) q.push(v);}x = max(x, mn[u] + a[u] - 1);}coutarr(mn, m);if (x > n) return;mem(mx, 0x3f);for (int i = 1; i <= m; i++)if (!out[i]) mx[i] = n - a[i] + 1, q.push(i);while (!q.empty()) {int u = q.front(); q.pop();for (auto v : ginv[u]) {mx[v] = min(mx[v], mx[u] - a[v]);if (!--out[v]) q.push(v);}}coutarr(mx, m);
}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;
}
/*_____ _ _ _ __ __| _ \ | | | | | | \ \ / /| |_| | | | | | | | \ \/ /| ___/ | | | | _ | | } {| | | |_| | | |_| | / /\ \|_| \_____/ \_____/ /_/ \_\
*/
关于代码的亿点点说明:
- 代码的主体部分位于
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
函数分开写纯属个人习惯,主要是为了多组数据。
这篇关于CCF-CSP认证考试 202212-2 训练计划 100分题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!