赛纲介绍
本次题目的总体题目难度如下,各位选手可以借此评估一下自身的技术水平。
题目编号 题目名称 题目难度 T1 项目计划 入门 T2 千载难逢的良缘 普及- T3 保险金 普及- T4 晋级赛 普及- T5 科技展示 普及- T6 活动筹备计划 普及-
T1 项目计划
题目大意
给出项目数量和产线数量,并给出完成项目所需的时间,所有项目的时间都是给出的这个时间。求完成所有项目所需的总时间。
题解思路
先用取余运算确定完成所有项目所需的轮数,如果无法整除则需要单独再增加一轮时间。确定轮次之后计算总时间,可以先单独计算时分秒,再按秒分时的顺序进行进位判断。
需要注意输入的格式中存在 : 分隔符,需要用提示中的 scanf 获取,或在读取时注意 : 的位置。
参考代码
T2 千载难逢的良缘
题目大意
给出每个人的平分,评分差值的绝对值越小越有缘,求最有缘的两个分数以及他们的差值绝对值。
题解思路
差值绝对值最小的两个分数一定是大小最接近的,所以整体排序后遍历整个数组,记录其中差值绝对值最小的情况。
参考代码
T3 保险金
题目大意
给出每个客户的 mmm 条事故保险金,要求按照客户顺序处理,每个客户内按金额从小到大处理,直到当天能发放的保险金总额不够继续发放。
题解思路
按题目要求的顺序排序,可以使用结构体排序,按客户编号和金额大小排序,再模拟发放过程即可。
需要注意题目要求的输出格式,当遇到新客户时要输出名字和发放事故数,再输出每个事故的保险金数量。所以这里要记录上一个发放事故的客户编号,区分不同的客户。在输出时也要先遍历统计数量,再遍历输出对应的面额。
参考代码
T4 晋级赛
题目大意
给出选手分数,查询多个分数对应的无法晋级人数。
题解思路
由于是多次查询,因此可以先排序,再使用二分查找的方法查询晋级分数所在的数组下标,从而得到无法晋级的下标范围。
参考代码
T5 科技展示
题目大意
给出 n 件展品,选择 m 件展品,要求方案输出时编号按升序排列。
题解思路
经典深度优先搜索抽小球,需要注意用 vis 数组记录哪些展品已经选择。但本题中要求编号按升序排列,因此在递归时可以加入编号范围的参数,用于控制选取时的循环范围,确保选取编号是升序。
参考代码
T6 活动筹备计划
题目大意
三种任务在每天有不同的效果值,不能连续两天选择相同的任务,切换任务会获得对应的切换效果值。求 nnn 填的最大总效果值。
题解思路
由于每天每个任务的效果值都可能变化,所以选择动态规划,状态转移方程形如 dp[i][0]=max(dp[i-1][1]+w[1][0],dp[i-1][2]+w[2][0])+val[i][0];,其中 w[i][j] 表示切换任务 i 到任务 j 的效果值,val[i][j] 表示第 i 天完成任务 j 的效果值。
类似于涂色问题,由于选择任务时不能和前一天的任务相同,因此需要记录前一天选择的任务编号,重复的情况是无法转移的,同时前一天的任务编号也参与了切换效果值的计算。在 dp 数组的设计中选择二维形式,dp[i][j] 表示第 i 天选择任务 j 的最大总效果值。
参考代码