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 天内完成训练。

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<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)
#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 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 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. 代码的主体部分位于 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 函数分开写纯属个人习惯，主要是为了多组数据。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/486623.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

shell实现查询进程号并批量kill(脚本)

shell实现查询进程号并批量kill(脚本)

问题或需求描述 在shell中&#xff0c;如果你想通过命令行查询出一系列匹配某个关键词的进程&#xff0c;并使用xargs命令批量结束这些进程&#xff0c;可以按照以下步骤操作&#xff1a; # 查询并提取进程号 pgrep -f "关键词" | xargs kill# 或者&#xff0c;如果…
阅读更多...
Qt 用任意直线来分割多边形，返回分割后的多边形

Qt 用任意直线来分割多边形，返回分割后的多边形

任意直线分割多边形&#xff0c;返回分割后的多边形 效果 使用示例 QPolygonF LineSegmentationPolygon(const QPolygonF& poly, const QLineF& line, SideToRemove sideToRemove)源码 enum class SideToRemove {None,Left,Right};// 直线分割多边形 QPolygonF LineS…
阅读更多...
多叉树题目：N 叉树的前序遍历

多叉树题目：N 叉树的前序遍历

文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;N 叉树的前序遍历 出处&#xff1a;589. N 叉树的前序遍历 难度 3 级 题目…
阅读更多...
10-shell编程-辅助功能

10-shell编程-辅助功能

一、字体颜色设置 第一种: \E[1:色号m需要变色的字符串\E[0m 第二种: \033[1:色号m需要变色的字符串\033[0m ########################### \E或者\033 #开启颜色功能 [1: #效果 31m #颜色色号 \E[0m #结束符 1&#xff0c;颜色案例 2&#xff0c;效果案例 二、gui&am…
阅读更多...
波奇学Linux：网络接口

波奇学Linux：网络接口

127.0.0.1本地回环ip&#xff0c;用于本地测试&#xff0c;不会进行网络通信 TCP是面向连接的&#xff0c;服务器比较被动 需要服套接字监听 listen状态 正常通信默认会进行主机序列和网络序列的转换 TcpServer.cc #pragma once#include<iostream> #include<string…
阅读更多...
GAMES101 学习4

GAMES101 学习4

材质和外观 材质 BRDF 漫反射 任何方向的光进来都会被均匀的反射到周围各个不同的方向上去 假设能量守恒&#xff0c;那么 Li Lo&#xff0c;这之后BRDF就 &#xff0c;就可以定义一个反照率 &#xff08;Albeo&#xff09; - &#xff0c;在&#xff08;0 - 1&#xff0…
阅读更多...
【包远程安装运行】SpringBoot+Mysql实现的图书商城平台+演示视频+开发文档(论文模板)

【包远程安装运行】SpringBoot+Mysql实现的图书商城平台+演示视频+开发文档(论文模板)

今天发布的是一款由SpringBootMySQL实现的在线图书商城系统源码&#xff0c;系统主要实现的功能分前台用户和后台管理。 前台功能主要有&#xff1a; 图书物展示、图书分类展示、图书搜索、用户登录注册、图书收藏、图书添加购物车、用户个人信息修改、用户充值提交、购物车图…
阅读更多...
【Linux基础】ubuntu虚拟机配置及原理

【Linux基础】ubuntu虚拟机配置及原理

一、虚拟机 虚拟机&#xff08;Virtual Machine&#xff0c;VM&#xff09;是一种软件实现的计算机系统&#xff0c;它在物理计算机上模拟了一个完整的计算机硬件环境&#xff0c;包括处理器、内存、存储设备和网络接口等。通过虚拟机&#xff0c;用户可以在单个物理计算机上同…
阅读更多...
扭矩衰减的影响因素及改善措施——SunTorque智能扭矩系统

扭矩衰减的影响因素及改善措施——SunTorque智能扭矩系统

智能扭矩系统-智能拧紧系统-扭矩自动控制系统-SunTorque 扭矩衰减是许多机械系统中常见的问题&#xff0c;特别是在长期运行或高负荷工作环境下。扭矩衰减不仅影响设备的性能&#xff0c;还可能引发安全隐患。因此&#xff0c;了解扭矩衰减的影响因素及采取相应的改善措施至关…
阅读更多...
Python Flask框架 -- ORM模型的CRUD操作（增删改查）

Python Flask框架 -- ORM模型的CRUD操作（增删改查）

CRUD操作 使用ORM进行CRUD(Create、Read、Update、Delete)操作&#xff0c;需要先把操作添加到会话中&#xff0c;通过db.session可以获取到会话对象。会话对象只是在内存中&#xff0c;如果想要把会话中的操作提交到数据库中&#xff0c;需要调用db.session.commit()操作&…
阅读更多...
Navicat Premium 16中文---数据库管理与开发的强大引擎

Navicat Premium 16中文---数据库管理与开发的强大引擎

Navicat Premium 16是一款功能强大的数据库管理工具&#xff0c;旨在为用户提供高效、便捷的数据库连接、管理和保护体验。该软件支持多种数据库系统&#xff0c;如MySQL、Oracle、SQL Server等&#xff0c;满足用户多样化的需求。通过直观的图形界面&#xff0c;用户可以轻松进…
阅读更多...
电脑中msvcp140_codecvt_ids.dll丢失的解决方法,实测有效的方法

电脑中msvcp140_codecvt_ids.dll丢失的解决方法,实测有效的方法

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中最常见的就是缺少某个DLL文件。而msvcp140CODECVTIDS.dll就是其中之一。那么&#xff0c;msvcp140CODECVTIDS.dll是什么&#xff1f;msvcp140CODECVTIDS.dll文件属性又是什么呢&#xff1f;msvcp140C…
阅读更多...
探索LLaMA模型：架构创新与Transformer模型的进化之路

探索LLaMA模型：架构创新与Transformer模型的进化之路

引言 在人工智能和自然语言处理领域&#xff0c;预训练语言模型的发展一直在引领着前沿科技的进步。Meta AI&#xff08;前身为Facebook&#xff09;在2023年2月推出的LLaMA&#xff08;Large Language Model Meta AI&#xff09;模型引起了广泛关注。LLaMA模型以其独特的架构…
阅读更多...
C语言例4-3：复合语句，输出a,b的值

C语言例4-3：复合语句，输出a,b的值

代码如下&#xff1a; //复合语句&#xff0c;输出a,b的值 #include<stdio.h> int main(void) {int a 10;printf("a %d\n",a);{int b20; //复合语句printf("b %d\n",b); //复合语句中的数据定义语句放在其他语句的前面}return …
阅读更多...
【每日力扣】332. 重新安排行程与51. N 皇后

【每日力扣】332. 重新安排行程与51. N 皇后

&#x1f525; 个人主页: 黑洞晓威 &#x1f600;你不必等到非常厉害&#xff0c;才敢开始&#xff0c;你需要开始&#xff0c;才会变的非常厉害。 332. 重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你…
阅读更多...
急速解决代码扫描Mybatis的SQL注入问题

急速解决代码扫描Mybatis的SQL注入问题

1.sql注入是什么 sql注入见名知意&#xff0c;是指一些非法用户通过将一些特殊字符或者sql语句插入到要提交的表单之中&#xff0c;从而让服务器在不知情的情况下执行恶意的sql命令&#xff0c;从而引发一系列的安全隐患。 讲的通俗一点就是说&#xff0c;用户利用sql语法将一…
阅读更多...
java数据结构与算法刷题-----LeetCode75. 颜色分类

java数据结构与算法刷题-----LeetCode75. 颜色分类

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 双指针两次遍历2. 三指针 1. 双指针两次遍历 解题思路&#…
阅读更多...
数字化转型能给企业创造哪些价值？

数字化转型能给企业创造哪些价值？

企业数字化转型能创造哪些价值&#xff1f; 深耕TOB行业 9 年&#xff0c;下面来分享下自己的一些经验和看法。 &#xff08;看完要是觉得有用&#xff0c;记得点个赞哈~&#xff09; 1、从宏观上理解&#xff0c;我们可以分成4个大的方面&#xff1a; &#xff08;1&#x…
阅读更多...
Linux操作系统及进程（三）进程优先级及特性

Linux操作系统及进程（三）进程优先级及特性

目录 一、优先级概念 二、查看系统进程 三、进程切换 一、优先级概念 1.cpu资源分配的先后顺序&#xff0c;就是指进程的优先权&#xff08;priority&#xff09;。 2.优先权高的进程有优先执行权利。配置进程优先权对多任务环境的linux很有用&#xff0c;可以改善系统性能。…
阅读更多...
不敢想象吧！Anzo Capital发现不仅经济事件影响汇率天气也是

不敢想象吧！Anzo Capital发现不仅经济事件影响汇率天气也是

在投资交易中弄懂汇率的走势方向&#xff0c;对各位投资者的交易盈利那还不是小菜一碟&#xff0c;但各位投资者你们想象不到吧&#xff01;Anzo Capital发现不仅经济事件能影响汇率&#xff0c;就连天气也能轻易影响汇率。 就用2015年1月15日的经济事件来说&#xff0c;当瑞…
阅读更多...
最新文章

Copyright @ 2022~2023