CCF-CSP认证考试 202212-2 训练计划 100分题解

2024-03-25 22:12

本文主要是介绍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 1im)科目编号为 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+ti1 天就是该项训练的最后一天。

大部分科目的训练可以同时进行,即顿顿在同一天内可以同时进行多项科目的训练,但部分科目之间也存在着依赖关系。如果科目 i i i 依赖科目 j j j,那么只能在后者训练结束后,科目 i i i 才能开始训练。具体来说,如果科目 j j j 从第 a a a 天训练到第 a + t j − 1 a + t_j - 1 a+tj1 天,那么科目 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 1im)整数 p i p_i pi 表示科目 i i i 依赖的科目编号,满足 0 ≤ p i < i 0 \le p_i < i 0pi<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 1im)数 t i t_i ti 表示训练科目 i i i 所需天数,满足 1 ≤ t i ≤ n 1 \le t_i \le n 1tin

输出格式

输出到标准输出中。

输出共一行或两行。

输出的第一行包含空格分隔的 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 天内完成训练。

demo.jpg

具体来说,科目 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<n365 0 < m ≤ 100 0 < m \le 100 0<m100


题解

感觉第二题不太会考拓扑,但是这题拓扑序太典了,然后也没有搜到官方的讲题视频,不知道本意是考什么,就直接写拓扑了。

对于最早开始时间:如果科目 i i i 依赖于科目 j j j,即要先训练 j j j 才能训练 i i i,那么就连一条 j → i j\to i ji 的有向边。所有入度为 0 0 0 的科目都不存在依赖的科目,可以在第 1 1 1 天直接开始训练。其他的科目都要在其依赖的科目训练完后才能训练。执行拓扑的时候,当执行到边 j → i j\to i ji 时,用 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 ij 的有向边。所有入度为 0 0 0 的科目由于没有被依赖的科目,都可以在最后一刻完成,即 m x i = n − t i + 1 mx_i=n-t_i+1 mxi=nti+1。其他的科目都要在其被依赖科目的最晚开始时间前完成训练。执行拓扑的时候,当执行到边 i → j i\to j ij 时,用 m x i − t j mx_i-t_j mxitj 更新(取最小值) 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;
}
/*_____   _   _       _  __    __|  _  \ | | | |     | | \ \  / /| |_| | | | | |     | |  \ \/ /|  ___/ | | | |  _  | |   }  {| |     | |_| | | |_| |  / /\ \|_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明:

  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 速度(这个输入输出流的速度很慢)。在小数据量无所谓,但是在比较大的读入时建议加这句话,避免读入输出超时。如果记不下来可以换用 scanfprintf,但使用了这句话后,cinscanfcoutprintf 不能混用。
  6. main 函数和 work 函数分开写纯属个人习惯,主要是为了多组数据。

这篇关于CCF-CSP认证考试 202212-2 训练计划 100分题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/846396

相关文章

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

【Kubernetes】K8s 的安全框架和用户认证

K8s 的安全框架和用户认证 1.Kubernetes 的安全框架1.1 认证:Authentication1.2 鉴权:Authorization1.3 准入控制:Admission Control 2.Kubernetes 的用户认证2.1 Kubernetes 的用户认证方式2.2 配置 Kubernetes 集群使用密码认证 Kubernetes 作为一个分布式的虚拟