位置: IT常识 - 正文

CCF-CSP真题《202212-2 训练计划》思路+python,c++满分题解(2020ccf csp报名和考试时间)

编辑:rootadmin
CCF-CSP真题《202212-2 训练计划》思路+python,c++满分题解

推荐整理分享CCF-CSP真题《202212-2 训练计划》思路+python,c++满分题解(2020ccf csp报名和考试时间),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:2020ccf csp报名和考试时间,ccf csp-j/s 2021,ccf csp-j/s 2021,ccf csp成绩什么时候出,ccf csp考试内容,ccf-csp考试,ccf csp考试时间,ccf csp试题,内容如对您有帮助,希望把文章链接给更多的朋友!

想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全

试题编号:202212-2试题名称:训练计划时间限制:1.0s内存限制:512.0MB问题描述:问题背景

西西艾弗岛荒野求生大赛还有 n 天开幕!

问题描述

为了在大赛中取得好成绩,顿顿准备在 n 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 m 项科目的加强训练。其中第 i 项(1≤i≤m)科目编号为 i,也可简称为科目 i。已知科目 i 耗时 ti 天,即如果从第 a 天开始训练科目 i,那么第 a+ti−1 天就是该项训练的最后一天。

大部分科目的训练可以同时进行,即顿顿在同一天内可以同时进行多项科目的训练,但部分科目之间也存在着依赖关系。如果科目 i 依赖科目 j,那么只能在后者训练结束后,科目 i 才能开始训练。具体来说,如果科目 j 从第 a 天训练到第 a+tj−1 天,那么科目 i 最早只能从第 a+tj 天开始训练。还好,顿顿需要训练的 m 项科目依赖关系并不复杂,每项科目最多只依赖一项别的科目,且满足依赖科目的编号小于自己。那些没有任何依赖的科目,则可以从第 1 天就开始训练。

对于每一项科目,试计算:

1)最早开始时间:该科目最早可以于哪一天开始训练?

2)最晚开始时间:在不耽误参赛的前提下(n 天内完成所有训练),该科目最晚可以从哪一天开始训练?

n 天内完成所有训练,即每一项科目训练的最后一天都要满足 ≤n。需要注意,顿顿如果不能在 n 天内完成全部 m 项科目的训练,就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。

输入格式

从标准输入读入数据。

输入共三行。

输入的第一行包含空格分隔的两个正整数 n 和 m,分别表示距离大赛开幕的天数和训练科目的数量。

输入的第二行包含空格分隔的 m 个整数,其中第 i 个(1≤i≤m)整数 pi 表示科目 i 依赖的科目编号,满足 0≤pi<i;pi=0 表示科目 i 无依赖。

输入的第三行包含空格分隔的 m 个正整数,其中第 i 个(1≤i≤m)数 ti 表示训练科目 i 所需天数,满足 1≤ti≤n。

输出格式

输出到标准输出中。

输出共一行或两行。

输出的第一行包含空格分隔的 m 个正整数,依次表示每项科目的最早开始时间。

如果顿顿可以在 n 天内完成全部 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 天就开始训练。

10 天时间恰好可以完成所有科目的训练。其中科目 1 耗时仅 1 天,所以最晚可以拖延到第 10 天再开始训练;而科目 5 耗时 10 天,必须从第 1 天就开始训练。

样例 2 输入CCF-CSP真题《202212-2 训练计划》思路+python,c++满分题解(2020ccf csp报名和考试时间)

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 无法在 10 天内完成训练。

具体来说,科目 5 依赖科目 2、科目 2 又依赖于科目 1,因此科目 5 最早可以从第 4 天开始训练。

样例 3 输入

10 5 0 1 2 3 4 10 10 10 10 10

样例 3 输出

1 11 21 31 41

子任务

70 的测试数据满足:顿顿无法在 n 天内完成全部 m 项科目的训练,此时仅需输出一行“最早开始时间”;

全部的测试数据满足 0<n≤365 且 0<m≤100。

真题来源:训练计划

 感兴趣的同学可以如此编码进去进行练习提交

直接无脑解(70分):

n, m = map(int,input().split())p = [0]+[i for i in map(int,input().split())]t = [0]+[i for i in map(int,input().split())]earliest = [0 for _ in range(m+1)]latest = [0 for _ in range(m+1)]# 将每个科目的最早时间确定for i in range(1,m+1): if p[i]==0: earliest[i] = 1 else: earliest[i] = earliest[p[i]]+t[p[i]]# 输出每项科目的最早开始时间print(*earliest[1:])

 运行结果: 

错误解析:

        这种解法属于第二题看到题直白写就好,  由于70% 的测试数据满足:顿顿无法在 n 天内完成全部 m 项科目的训练,此时不需要考虑最晚开始时间是否输出的问题,这是不符题意的,但也有70分入手。 

pyhon满分题解: 

n, m = map(int,input().split())p = [0]+[i for i in map(int,input().split())]t = [0]+[i for i in map(int,input().split())]earliest = [0 for _ in range(m+1)]latest = [0 for _ in range(m+1)]mark = 1# 将每个科目的最早时间确定for i in range(1,m+1): if p[i]==0: earliest[i] = 1 else: earliest[i] = earliest[p[i]]+t[p[i]] # 判断所有科目最早开始的情况是否可以完成所有科目 if earliest[i]+t[i]-1>n: mark = 0# 输出每项科目的最早开始时间print(*earliest[1:])# 判断是否可以完成项目if mark==1: # 将确定每个科目的最晚,从最后的科目往前推,需要把依赖该科目的科目所消耗时间算上 for i in range(m, 0, -1): temp = 366 for j in range(i+1, m+1): #寻找是否有依赖该科目的科目 if p[j] == i: temp = min(temp, latest[j]) #如果没有被依赖,那么最晚开始时间 = 最后期限 - 持续时间的时刻 if temp == 366: latest[i] = n-t[i]+1 #如果有被依赖,那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻 else: latest[i] = temp-t[i] # 输出每项科目的最早开始时间 print(*latest[1:])

 运行结果: 

思路解析:

        在最早开始时间的计算中,每一个科目的最早开始时间依赖于它的前继科目;

        而在最晚开始时间的计算中,由于某科目是被别的科目依赖的,所以计算它的最晚开始时间时要考虑依赖它的科目能否如期完成,所以我们做个标记 mark ,如果最早可以完成,则继续分析最晚开始时间;

        而将确定每个科目的最晚,需要从最后的科目往前推,因为如果有依赖的科目,需要把依赖该科目的科目所消耗时间算上,如果没有被依赖,那么最晚开始时间 = 最后期限 - 持续时间的时刻,如果有被依赖,那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻。

c++满分题解:

#include<iostream>#include<cmath>using namespace std;const int N = 101;int n, m;int p[N], t[N];int earliest[N], latest[N];int main() { int mark = 1; cin >> n >> m; for (int i = 1; i <= m; i++) cin >> p[i]; for (int i = 1; i <= m; i++) cin >> t[i]; // 将每个科目的最早时间确定 for (int i = 1; i <= m; i++) { if (p[i] == 0) earliest[i] = 1; else earliest[i] = earliest[p[i]] + t[p[i]]; // 判断所有科目最早开始的情况是否可以完成所有科目 if (earliest[i] + t[i] - 1 > n) mark = 0; } // 输出每项科目的最早开始时间 for (int i = 1; i <= m; i++) cout << earliest[i] << " "; cout << endl; // 判断是否可以完成项目 if (mark == 1) { // 将确定每个科目的最晚,从最后的科目往前推,需要把依赖该科目的科目所消耗时间算上 for (int i = m; i >= 1; i--) { int temp = 366; for (int j = i + 1; j <= m; j++) { // 寻找是否有依赖该科目的科目 if (p[j] == i) temp = min(temp, latest[j]); } // 如果没有被依赖,那么最晚开始时间 = 最后期限 - 持续时间的时刻 if (temp == 366) latest[i] = n - t[i] + 1; // 如果有被依赖,那么最晚开始时间 = 依赖它的科目的最晚开始的时刻最小的科目 - 本身的持续时间的时刻 else latest[i] = temp - t[i]; } // 输出每项科目的最晚开始时间 for (int i = 1; i <= m; i++) cout << latest[i] << " "; } return 0;}

 运行结果: 

本文链接地址:https://www.jiuchutong.com/zhishi/299666.html 转载请保留说明!

上一篇:【计算机视觉】图像增强——图像的形态学操作(计算机视觉的未来发展方向有哪些)

下一篇:京东手机APP抢购茅台秒杀脚本(手机用)(安卓京东抢购)

  • 荣耀平板V7Pro怎么设置面部解锁(荣耀平板V7Pro怎么设置横屏全屏)

    荣耀平板V7Pro怎么设置面部解锁(荣耀平板V7Pro怎么设置横屏全屏)

  • 运费险是淘宝出还是商家出(淘宝运费险是包运费吗)

    运费险是淘宝出还是商家出(淘宝运费险是包运费吗)

  • 荣耀30pro跑分安兔兔是多少呢

    荣耀30pro跑分安兔兔是多少呢

  • 陌陌发动态被屏蔽了(陌陌动态被屏蔽了怎么办)

    陌陌发动态被屏蔽了(陌陌动态被屏蔽了怎么办)

  • iphone8电池容量(iphone8电池容量80%)

    iphone8电池容量(iphone8电池容量80%)

  • 淘宝店货源在哪里找(淘宝店货源从哪里来)

    淘宝店货源在哪里找(淘宝店货源从哪里来)

  • ps关闭按钮不见了(ps关闭按钮不见了怎么办)

    ps关闭按钮不见了(ps关闭按钮不见了怎么办)

  • asf格式视频正确的扩展名(视频asf格式怎么转换mp4格式)

    asf格式视频正确的扩展名(视频asf格式怎么转换mp4格式)

  • 政务服务实名认证失败(政务服务平台实名认证)

    政务服务实名认证失败(政务服务平台实名认证)

  • win10右下角盾牌不见了(win10右下角盾牌红叉什么意思)

    win10右下角盾牌不见了(win10右下角盾牌红叉什么意思)

  • qq一直被盗号改密码不管用(我的qq号总是被盗,改密码也不行)

    qq一直被盗号改密码不管用(我的qq号总是被盗,改密码也不行)

  • 朋友圈怎么手动打艾特(朋友圈怎么手动设置输入两年、三年等可见)

    朋友圈怎么手动打艾特(朋友圈怎么手动设置输入两年、三年等可见)

  • qq群课堂视频生成要多久(qq群课堂播放视频的格式)

    qq群课堂视频生成要多久(qq群课堂播放视频的格式)

  • 手机屏幕进水黑色阴影(手机屏幕进水黑屏)

    手机屏幕进水黑色阴影(手机屏幕进水黑屏)

  • 华为p30lite是什么意思(华为p30lite怎么样?)

    华为p30lite是什么意思(华为p30lite怎么样?)

  • 小米手机系统升级卡住了怎么办(小米手机系统升级怎么关闭)

    小米手机系统升级卡住了怎么办(小米手机系统升级怎么关闭)

  • 淘宝有几次换货机会(淘宝换货一次后还能换货吗)

    淘宝有几次换货机会(淘宝换货一次后还能换货吗)

  • abdlog储存限制是什么(adblog储存大小限制是什么意思)

    abdlog储存限制是什么(adblog储存大小限制是什么意思)

  • 华为mate30音量调节在哪(华为mate30 调音量)

    华为mate30音量调节在哪(华为mate30 调音量)

  • 手机充电器1a和2a的区别(手机充电器1A和2A的区别)

    手机充电器1a和2a的区别(手机充电器1A和2A的区别)

  • realmex2pro支持夜景模式吗(realmex2pro有红外吗)

    realmex2pro支持夜景模式吗(realmex2pro有红外吗)

  • 电脑可以下载手写输入法吗(电脑可以下载手机版剪映吗)

    电脑可以下载手写输入法吗(电脑可以下载手机版剪映吗)

  • 电脑重置后怎么安装系统(电脑重置后怎么恢复成以前那样)

    电脑重置后怎么安装系统(电脑重置后怎么恢复成以前那样)

  • 京东如何查看消费总额(京东如何查看消费)

    京东如何查看消费总额(京东如何查看消费)

  • 小规模纳税人收入超过500万怎么办
  • 建筑公司收到预付款怎么开票
  • 非营利组织免税资格认定申请表
  • 环境保护税的应税污染物有哪些
  • 房产公司结转收入条件
  • 发票收款人和复核没写可以用吗
  • 固定资产加速折旧法
  • 或有资产的确认条件ACCA
  • 所有者权益是
  • 税屋网官网房屋
  • 买金税盘发票能全额抵进项税吗
  • 受托代为投资账务处理
  • 定期定额户超过定额怎么报个税
  • 纳税人选择简易办法一经选择
  • 建设工程的停工损失包括哪些内容
  • 注册资本金印花税什么时候缴纳
  • 设备投入安装计入什么科目
  • 药品回扣2021
  • 抄税没成功
  • 如何冲销账面上的资金
  • 长期应付款账面价值和账面余额
  • 库存现金清查短款会计分录
  • 加工费月底需要全部结转吗
  • 销售蔬菜免税账务处理
  • 已完成认证
  • 啥叫规上工业企业
  • 固定资产报废的净损失计入哪里
  • ios路由设计
  • 二手车买卖如何纳税
  • 如何阻止win10升级到win11
  • 清除文件夹exe病毒工具
  • PHP:pg_copy_to()的用法_PostgreSQL函数
  • 溢价对外投资账务处理
  • 建筑业预缴增值税
  • php 微信公众号
  • netbeans ide 8.1
  • 建筑业异地预缴增值税
  • 用代码说话
  • mkisofs命令
  • 帝国cms怎么安装不了
  • 企业所得税不得核定征收行业
  • 付员工经济补偿金的分录
  • 关联广告是什么意思
  • 公司内控制度由谁制定
  • 小企业会计准则没有以前年度损益调整科目
  • 子公司和分公司的区别
  • 制作费开票属于什么编码类型
  • 高新企业申报条件有哪些
  • 保险公司作为奖金怎么算
  • 计提个税和缴纳个税金额不符的原因
  • 建筑工程人工费包括哪些内容
  • 没有抄税会导致什么情况
  • 小规模免征增值税到什么时间止
  • 出口收入没有及时申报怎么处罚
  • 个人取得全年一次性奖金征税规定
  • 公司送的车还能要回去吗
  • 利息保障倍数多少算正常
  • 关于投资收益纳税的说法
  • 年度的汇算清缴
  • 减免税款借方余额
  • mysql数据库用户名和密码怎么查看
  • window10怎么设置蓝牙
  • windows xp windows
  • linux修改系统日期命令
  • VMware虚拟机下载
  • win7升win8要钱吗
  • win10的uwp在哪
  • 在linux中使用什么命令可以执行shell脚本
  • win10 20h2怎么更新
  • 小郭聊一聊
  • 备份引导分区
  • [置顶]星陨计划
  • 利用JQuery实现datatables插件的增加和删除行功能
  • 在Unity中使用事件/委托机制(event/delegate)进行GameObject之
  • jQuery的ajax和遍历数组json实例代码
  • python冒泡排序流程图
  • 容积率大于0.5 房产原值怎样算
  • 企业改制相关文件
  • 朝阳银行作息时间
  • 申报地税的流程图
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设