巅峰赛 #39 题解 | 非官方
本次题目猜测的总体难度如下，仅供参考：
题目编号 题目标题 难度 T1 Yuilice 的手工套装 入门 T2 Yuilice 的相册整理 普及- T3 Yuilice 的小区接送 普及/提高- T4 Yuilice 的分批冲印 普及/提高- T5 Yuilice 的打印店 普及+/提高 T6 Yuilice 的共用设备 普及+/提高
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1. YUILICE 的手工套装
题目大意
有 aaa 张大卡纸和 bbb 张小卡纸。一个手工需要一张大卡纸和一张小卡纸。一张大卡纸可以变成两张小卡纸。请问最多能作多少个手工。
解题思路
看到 aaa 的的范围 ≤106\le 10^6≤106，所以可以遍历 aaa。遍历的意思为将 iii 张大卡纸剪成小卡纸。新的小卡纸的数量为 b+2×ib + 2\times ib+2×i，而大卡纸的数量为 a−ia - ia−i。最后答案为 min(na,nb)\min(na, nb)min(na,nb)。
参考代码
时间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2. YUILICE 的相册整理
题目大意
定义“日期回退”为 ai>ai+1a_i > a_{i+1}ai >ai+1 。现在可以反转 kkk 个数，请问“日期回退”最少为多少。
解题思路
由于 kkk 为定值，所以我们可以使用滑动窗口来维护反转的区间。使用前缀和优化，如果 l∼rl\sim rl∼r 的“日期回退”数量为 xxx，那么反转后这段区间里面的“日期回退”数量则为 k−xk - xk−x，如果搞不清楚，也可以设置一个反向“日期回退”的前缀和。另外，我们需要判断反转后的两个端点，即 [l−1,r][l - 1, r][l−1,r] 和 [l,r+1][l, r + 1][l,r+1]，如果这两个也满足则需要将答案加 1。但是如果前面一段增加了那么后面一段既没有了，所以还要额外判断一下。最后取最小值。
参考代码
时间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3. YUILICE 的小区接送
题目大意
有一颗 nnn 个节点 n−1n-1n−1 条边的树，需要将这个树拆成若干条简单路径。每条路径需要：
* 支付一次固定派车费 CCC。
* 支付路径经过的每条道路的行驶费用。
* 若路径至少包含两个站点，支付两个端点各自的服务费，内部站点不收费。
* 若路径只有一个站点，只支付该站点一次服务费。
求所有路径费用之和的最小可能值。
解题思路
设 dp[u][fa]dp[u][fa]dp[u][fa] 为到这个节点能够获得最优解的森林构造。
设 basebasebase 为全部不相连的最代价，为所有孩子的 dp[v][0]dp[v][0]dp[v][0] 之和，加上自己的端点服务费 pup_upu 和 派车费 CCC。也就是：
(∑v∈subtree(u)dp[v][0]))+C+pu\Bigg( \sum_{v\in subtree(u)}dp[v][0])\Bigg) + C + p_u (v∈subtree(u)∑ dp[v][0]))+C+pu
如果 fa=0fa = 0fa=0，那么可以连接 0,1,20, 1, 20,1,2 个孩子。每连接一个孩子，代价为 delta=w−C−dp[v][0]+dp[v][1]delta = w - C - dp[v][0] + dp[v][1]delta=w−C−dp[v][0]+dp[v][1]，找到代价最小的两个，设为 delta1,delta2delta_1, delta_2delta1 ,delta2 。当连接 111 个孩子的时候，变化为 delta1delta_1delta1 ；当连接 222 个孩子的时候，变化为 delta1+delta2−pudelta_1 + delta_2
- p_udelta1 +delta2 −pu 。所以 dp[u][0]=min(base,base+delta1,base+delta1+delta2−pu)dp[u][0] = \min(base, base + delta_1, base + delta_1 + delta_2 - p_u)dp[u][0]=min(base,base+delta1 ,base+delta1 +delta2 −pu )。
如果 fa=1fa = 1fa=1，那么可以连 000 个孩子或者 111 的孩子。每连接一个孩子，代价为 delta=w−C−dp[v][0]+dp[v][1]delta = w - C - dp[v][0] + dp[v][1]delta=w−C−dp[v][0]+dp[v][1]，找到代价最小的一个。dp[u][1]=min(base,base+delta−pu)dp[u][1] = \min(base, base + delta - p_u)dp[u][1]=min(base,base+delta−pu )。减去 pup_upu 的原因是 uuu
多连了一个后，就变成内部点，内部站点不收费。
最后输出 dp[1][0]dp[1][0]dp[1][0]，因为根节点不可能有父亲。
参考代码
时间复杂度：O(nlogn)O(n\log n)O(nlogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T4. YUILICE 的分批冲印
题目大意
有 nnn 张照片，第 iii 张照片的打印时间为 tit_iti ，准备参数为 sis_isi 。可以把这些照片片分成至多 kkk 个非空批次，一个批次的耗时等于其中所有照片的打印时间之和，再加上这些照片的准备参数的最大值。求批次中最大耗时的最小可能值。
解题思路
当我们在题目里面看到“最大值最小”或者“最小值最大”，我们就要先想到二分。我们这一题可以二分的是耗时。我们将 aaa 不断从前往后遍历，如果 (sum+ti +(sum + t_i \space+(sum+ti + 区间最大 si)>mids_i) > midsi )>mid，那就说明再加一个数是不可行的，所以我们要分段。记录段数为 cntcntcnt，如果 cnt≤kcnt \le kcnt≤k，则方案可行；否则不可行。
参考代码
时间复杂度：O(nlog(∑ti+maxsi))O(n\log (\sum t_i + \max s_i))O(nlog(∑ti +maxsi ))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5. YUILICE 的打印店
题目大意
有 ppp 台打印机，第 j 台打印机打印一页需要 sjs_jsj 个时间单位。有四种操作：增加订单、取消订单、暂停接收、恢复接受。若在时刻 ttt 把一个 aaa 页的订单交给打印机 jjj，它在时刻 t+asjt+as _jt+asj 完成。求订单最终的结果。
解题思路
这是一题非常罕见的大模拟，让我们分析一下。
我们可以先创建一个 enum{enum}enum，表示订单状态。订单有四种状态，分别为：等待中、打印中、已取消、已完成。接着，我们分别要创建三个不同的结构体，分别是：打印机、订单、操作。
* 打印机结构体中，需要包含：
* 速度
* 当前订单
* 订单结束时间
* 是否可以用
* 打印机编号（可有可无）
* 订单结构体中，需要包含：
* 订单编号
* 订单页数
* 订单状态
* 订单答案结果
* 操作结构体中，需要包含：
* 操作类型
* 操作编号
* 操作参数
* 操作编号（可有可无）
接下来开始模拟，我们需要将打印机的操作开一个函数，表示操作。每一次操作需要遍历所有的打印机，如果这台打印机可用，那么我们就要从订单列表里面拿取下一个订单。但是如果这个订单取消了，我们就需要遍历下一个。接下来将打印机当前订单设置为这个订单，将订单状态设置为打印中，将订单结束时间设置为当前时间加上订单页数乘以打印机速度。然后将这个结束时间加入一个操作的大根堆，方便我们后续进行操作。
然后是主函数里面的操作。我们如果看到 op=0op = 0op=0，那说明这是自己设置的，其中的意思为订单已经完成。我们将这台打印机设置为空闲状态，订单设置为已完成，结果为完成时刻。如果 op=1op = 1op=1，则增加订单，将订单加入订单列表，订单数量 cnt++cnt++cnt++。如果 op=2op = 2op=2，那判断订单是否存在，且订单状态是否为等待中，如果是，则将订单状态设置为已取消，将答案设为 −1-1−1。如果 op=3op = 3op=3，直接将打印机能否使用改为 falsefalsefalse。如果 op=4op = 4op=4，则将打印机能否使用改为
truetruetrue。
接下来，如果操作为空，或者操作堆顶的结束时间不等于当前时间，则调用打印机操作函数。
最后，输出每一个订单的答案即可。
参考代码
单组测试样例时间复杂度：O(qlogq)O(q\log q)O(qlogq)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6. YUILICE 的共用设备
题目大意
有 nnn 个任务，每个人物有一个时间单位。每台设备可以有 1∼31\sim 31∼3 项任务。同一批中的任务同时开始，这一批的耗时等于其中最长任务的耗时。只有当前批次全部完成，下一批才能开始。有 mmm 对任务存在冲突，每对冲突任务不能放在同一批。计算完成全部任务的最短总时间。
解题思路
看到 nnn 的范围 ≤18\le 18≤18，范围非常小，所以可以使用状压 dpdpdp。
定义 SSS 为任务的完成状态，如果二进制下的位为 111，表示已完成；否则未完成。dp[S]dp[S]dp[S] 为记录完成状态 SSS 下的最小总耗时。
我们预先处理好所有的不冲突情况，n3n^3n3 暴力枚举，把任务状态最大值也记录下来，使用邻接表表示冲突关系。
状压 dpdpdp 过程中，我们要判断当前状态与之前暴力枚举的 maskmaskmask 是否有交集。如果有，则直接跳过，因为当前状态一定比之前状态更优。转移方程为：
dp[S ∣ mask]=min(dp[S ∣ mask],val+dp[S])dp[S\space| \space mask] = \min(dp[S\space| \space mask], val + dp[S]) dp[S ∣ mask]=min(dp[S ∣ mask],val+dp[S])
最后结果为 dp[(1≪n)−1]dp[(1 \ll n) - 1]dp[(1≪n)−1]。
参考代码
时间复杂度：O(2n⋅n3)O(2^n \cdot n^3)O(2n⋅n3)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
