9
导语
久违的巅峰赛,这次巅峰赛是以Dp和状压作为压轴的,毕竟许多朋友的状压熟练度还有待提升 (笑) 。
以下为题解
目录
题目编号 题目标题 难度 T1 Yuilice 的手工套装 入门 T2 Yuilice 的相册整理 普及- T3 Yuilice 的分批冲印 普及/提高- T4 Yuilice 的打印店 普及+/提高 T5 Yuilice 的小区接送 普及+/提高 T6 Yuilice 的共用设备 普及+/提高
YUILICE 的手工套装
题意简述
有 aaa 张大卡纸和 bbb 张小卡纸,每套手工套装需要一张大卡纸和一张小卡纸。可以把一张大卡纸剪成两张小卡纸,剪过的卡纸不能再当大卡纸使用。求最多能制作多少套。
样例 1 中输入为 5,05,05,0。剪开两张大卡纸后,还剩 333 张大卡纸和 444 张小卡纸,因此可以制作 333 套。样例 2 中小卡纸已经足够,直接使用 222 张大卡纸即可。
解题思路
解题方法
设剪开 xxx 张大卡纸,其中 0≤x≤a0\le x\le a0≤x≤a。操作结束后:
* 大卡纸有 a−xa-xa−x 张;
* 小卡纸有 b+2xb+2xb+2x 张。
每套需要两种卡纸各一张,所以固定 xxx 时最多制作
min(a−x,b+2x)\min(a-x,b+2x) min(a−x,b+2x)
套。枚举全部合法的 xxx,取最大值即可。
1. 读入 a,ba,ba,b,答案初始为 000。
2. 枚举 x=0,1,…,ax=0,1,\ldots,ax=0,1,…,a。
3. 计算当前值 min(a−x,b+2x)\min(a-x,b+2x)min(a−x,b+2x),更新答案。
任意一种制作方案都会剪开某个合法数量 xxx 的大卡纸,因此一定会被程序枚举。固定 xxx 后,套数不能超过剩余大卡纸数量,也不能超过小卡纸数量,所以最多是 min(a−x,b+2x)\min(a-x,b+2x)min(a−x,b+2x);取出这么多张两种卡纸后可以逐套配对,说明这个上限能够达到。
程序枚举了所有可能的 xxx,并取其中最大值,所以得到的正是最优答案。
时间复杂度为 O(a)O(a)O(a),额外空间复杂度为 O(1)O(1)O(1)。因为 a,b≤106a,b\le10^6a,b≤106,中间数量不超过 3×1063\times10^63×106,使用 int 足够。
* 剪纸后要同时减少大卡纸、增加小卡纸。
* 可以一次都不剪,x=0x=0x=0 必须被枚举。
* 不能直接输出 min(a,b)\min(a,b)min(a,b),因为剪纸可能增加可制作套数。
部分分
* 测试点 1~10(无额外限制):枚举裁剪数量即可获得满分。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
YUILICE 的相册整理
题意简述
有 nnn 张照片,日期为 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an 。如果 ai>ai+1a_i>a_{i+1}ai >ai+1 ,则位置 iii 有一处日期回退。可以不操作,也可以选择一段恰好包含 kkk 张照片的连续区间反转一次,求最少回退数。
反转只改变顺序,不改变日期;日期相等不算回退。
解题思路
解题方法
先记原序列的回退总数为 BBB,考虑反转区间 [l,r][l,r][l,r],其中 r=l+k−1r=l+k-1r=l+k−1。
区间内部的相邻关系会全部反向:原来严格上升的关系会变成回退,原来的回退会消失,相等关系仍然不计数。设区间内部严格上升数为 UUU、回退数为 DDD,内部部分反转后对答案的贡献就是 U−DU-DU−D。
区间外的关系都不变,只需要检查最多两条连接边:
* 如果 l>1l>1l>1,原来的 (al−1,al)(a_{l-1},a_l)(al−1 ,al ) 变成 (al−1,ar)(a_{l-1},a_r)(al−1 ,ar );
* 如果 r<nr<nr<n,原来的 (ar,ar+1)(a_r,a_{r+1})(ar ,ar+1 ) 变成 (al,ar+1)(a_l,a_{r+1})(al ,ar+1 )。
这样,每个区间都能在 O(1)O(1)O(1) 时间内算出答案。区间右移一格时,内部关系只删除最左边一对、加入最右边一对,因此 U,DU,DU,D 可以滑动维护。
1. 统计原序列的回退数 BBB,并令答案初始为 BBB,表示可以不操作。
2. 统计第一个长度为 kkk 的区间内部的上升数 UUU 和回退数 DDD。
3. 枚举区间左端点,用 B+U−DB+U-DB+U−D 加上两侧连接的变化量得到当前答案。
4. 窗口右移时删除离开窗口的相邻关系,加入新进入窗口的相邻关系。
5. 输出所有方案中的最小值。
把原序列的相邻关系分为三类:反转区间内部、区间左侧连接、区间右侧连接。内部关系反转后方向全部交换,因此贡献从 DDD 变成 UUU;两侧连接按反转后的端点重新计算;其他关系完全不变。三类关系覆盖了所有相邻位置且互不重复,所以公式准确计算了该区间的回退数。
滑动窗口每次只删除一条内部关系并加入一条新关系,故维护的 U,DU,DU,D 始终正确。算法枚举了所有长度为 kkk 的区间,同时保留了不操作方案,取最小值后就是全局最优解。
时间复杂度为 O(n)O(n)O(n),空间复杂度为 O(n)O(n)O(n)。比较关系必须使用严格不等号,日期相等时不计回退。
* 只处理两侧连接,忘记区间内部的方向会全部反转。
* 把相等关系算进上升或回退。
* 忘记不操作方案,或漏掉贴着首端、末端的区间。
* 这里统计的是相邻回退,不是任意两张照片组成的逆序对。
部分分
* 测试点 1~4(n≤2000n\le2000n≤2000,20 分):可以实际反转每个区间,再重新统计回退数。
* 测试点 5~20(无额外限制,80 分):使用滑动窗口维护区间内部贡献,并处理两侧连接。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
YUILICE 的分批冲印
题意简述
按顺序处理 nnn 张照片。第 iii 张照片的打印时间为 tit_iti ,准备参数为 sis_isi 。要把照片分成至多 kkk 个连续、非空批次。
一个批次的耗时是该批次所有 tit_iti 的总和,加上其中最大的 sis_isi 。目标是让所有批次中最大的耗时尽可能小。
解题思路
解题方法
二分答案。假设限制每个批次的耗时不能超过 XXX,从左到右尽可能多地把照片放入当前批次:
当前批次维护打印时间和 sum、准备参数最大值 mx。如果加入下一张照片后满足
sum+ti+max(mx,si)≤X,\text{sum}+t_i+\max(\text{mx},s_i)\le X, sum+ti +max(mx,si )≤X,
就继续加入;否则从这张照片开始新批次。
“尽可能长”必然合法,因为删去一个批次的前缀后,打印时间总和不会增加,准备参数最大值也不会增加。因此,贪心得到的批次数最少。
当 XXX 增大时,原来可行的分批方案仍然可行,所以可行性具有单调性,可以二分最小的 XXX。
1. 二分下界取 maxi(ti+si)\max_i(t_i+s_i)maxi (ti +si ),上界取 ∑ti+maxisi\sum t_i+\max_i s_i∑ti +maxi si 。
2. 在 check(X) 中从左到右维护当前批次的 sum 和 mx。
3. 如果单张照片都超过 XXX,直接判定失败。
4. 超过上限时新开批次,并清空当前批次的统计量。
5. 统计最少批次数是否不超过 kkk,据此继续二分。
对于固定的 XXX,设贪心算法第一批覆盖到位置 rrr。由于它取的是最长可行前缀,任何合法方案的第一批都不能超过 rrr。把贪心覆盖的前缀从任意合法方案中删去时,至多有一个批次被删去一部分前缀;剩余部分仍然合法,而且剩余批次数不会增加。
对剩余照片重复这个论证,得到贪心使用的批次数不超过任意合法方案,因此它得到的就是最少批次数。于是 check(X) 正确。又因为可行性随 XXX 增大而单调,二分找到的最小可行值就是答案。
一次 check 为 O(n)O(n)O(n),二分次数为 O(logU)O(\log U)O(logU),其中 U=∑ti+maxsiU=\sum t_i+\max s_iU=∑ti +maxsi ,总复杂度为 O(nlogU)O(n\log U)O(nlogU),空间复杂度为 O(n)O(n)O(n)。答案和中间和必须使用 long long。
* 准备参数取批次最大值,不是把所有 sis_isi 相加。
* 新开批次时要同时清空 sum 和 mx。
* 判断条件使用“加入后是否超过 XXX”,等于 XXX 时仍然合法。
* 需要先检查单张照片的 ti+sit_i+s_iti +si 是否超过 XXX。
部分分
* 测试点 1~2(k=1k=1k=1 或 k=nk=nk=n,10 分):直接计算整段或每张照片单独成批的答案。
* 测试点 3~6(n≤16n\le16n≤16,20 分):枚举相邻位置是否切分。
* 测试点 7~20(无额外限制,70 分):二分答案,使用最长可行前缀贪心。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
YUILICE 的打印店
题意简述
有 ppp 台打印机,共用一个先进先出等待队列。提交订单、取消等待订单、暂停打印机接单和恢复打印机接单都发生在给定时刻。
同一时刻必须按三步处理:先结算所有完成订单,再按输入顺序处理这一时刻的全部操作,最后按打印机编号从小到大统一接单。正在打印的订单不会因为暂停或取消而中断。
输出每个订单的完成时刻;被取消输出 −1-1−1;最终一直等待、没有开始打印输出 −2-2−2。
解题思路
解题方法
不能按时间单位逐秒模拟,因为时刻最多达到 10910^9109,订单完成时间还可能更大。系统状态只会在两类时刻发生变化:
1. 下一条外部操作发生的时刻;
2. 某台打印机完成当前订单的时刻。
每次跳到这两类时刻的最小值即可。维护每台打印机的状态、当前订单和完成时刻,维护每个订单的状态以及等待队列。
到达时刻 now 后严格执行:
1. 把所有完成时刻等于 now 的订单标记为完成,并释放打印机;
2. 按输入顺序执行 now 时刻的所有操作;
3. 按打印机编号扫描空闲且允许接单的机器,从队首跳过已取消订单后派单。
最后一条外部操作结束后仍要继续处理打印完成事件。若没有外部操作、也没有正在打印的订单,队列中的订单就不可能再开始,答案保持为 −2-2−2。
1. 读入全部操作,保存操作顺序。
2. 用 state 区分等待、打印中、完成和取消。
3. 每轮找到下一外部操作时刻与最早完成时刻的较小值。
4. 依次完成结算、批量处理操作、按机器编号派单。
5. 记录完成时刻、取消结果和最终等待结果。
相邻两个事件时刻之间没有新操作,也没有订单完成,所以跳过中间时间不会遗漏状态变化。每轮第一步结算所有完成订单,第二步按照原输入顺序处理全部操作,第三步按题目规定的打印机编号和队列顺序派单,因此这一轮得到的状态与真实过程完全一致。
由初始状态正确,按事件时刻归纳可知整个模拟正确。每个订单只会在完成时被记录一次;取消只会对仍在等待的订单生效。模拟结束时,仍等待的订单已经没有可接单的打印机,所以输出 −2-2−2 正确。
设提交订单数为 nnn。事件时刻数量不超过 q+nq+nq+n,每轮最多扫描 ppp 台打印机,因此时间复杂度为 O(p(q+n))O(p(q+n))O(p(q+n)),空间复杂度为 O(p+q+n)O(p+q+n)O(p+q+n)。完成时刻使用 long long。
* 同一时刻的多条操作之间不能派单。
* 暂停只影响接收新订单,不会打断正在打印的订单。
* 取消正在打印、已经完成或已经取消的订单都没有额外效果。
* 最后一条操作之后还要继续结算完成事件。
* 等待队列里的取消订单可以延迟到队首时跳过。
部分分
* 测试点 1~2(p=1p=1p=1,只有提交操作,10 分):维护单台打印机的结束时间。
* 测试点 3~6(只有提交操作,20 分):模拟多台打印机和共享队列。
* 测试点 7~10(只有提交、取消操作,20 分):增加等待订单取消和状态判断。
* 测试点 11~20(无额外限制,50 分):完整处理完成、操作、派单的时序。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
YUILICE 的小区接送
题意简述
给定一棵树,每个站点有端点服务费 pip_ipi ,每条道路有行驶费用 www,每条路线还要支付一次固定派车费 CCC。要把所有站点划分成互不相交的简单路径,单个站点也可以单独成路。
多站路径只收两个端点的服务费,内部站点不收费;单站路径只收该站点一次服务费。求总费用最小值。
解题思路
解题方法
在树上保留一部分道路。只要每个站点被保留的道路数不超过 222,保留下来的每个连通块就是一条合法路径;反过来,每种路径划分也对应这样一组保留道路。
设保留边集合为 FFF,则路径数量为 n−∣F∣n-|F|n−∣F∣,所有路径固定费用为 (n−∣F∣)C(n-|F|)C(n−∣F∣)C。每条保留边贡献道路费用 www,同时让两个连通块合并,减少一份派车费 CCC。端点和单站服务费统一写成“度数不超过 111 的点付一次”:
总费用=nC+∑e∈F(we−C)+∑deg(v)≤1pv.\text{总费用}=nC+\sum_{e\in F}(w_e-C)+\sum_{\deg(v)\le1}p_v. 总费用=nC+e∈F∑ (we −C)+deg(v)≤1∑ pv .
把树定根,定义 dp[u][0]dp[u][0]dp[u][0] 表示父边不保留时,uuu 子树的最小变形费用;dp[u][1]dp[u][1]dp[u][1] 表示父边保留时的最小变形费用。
假设所有子边都不保留,基准为 BBB。保留连接儿子 vvv 的边后,新增代价为
dv=dp[v][1]+wuv−C−dp[v][0].d_v=dp[v][1]+w_{uv}-C-dp[v][0]. dv =dp[v][1]+wuv −C−dp[v][0].
父边不保留时,uuu 最多选两条子边;父边保留时,最多再选一条子边。只需维护最小的两个 dvd_vdv 。注意不能只选负增量:两条正增量也可能一起省下当前点的端点服务费。
1. 迭代遍历树,记录每个点的父亲和遍历顺序。
2. 按逆序处理节点,保证儿子状态已知。
3. 计算所有子边不选的基准值,并维护最小的两个增量。
4. 根据父边是否保留,枚举允许选取的子边数量,得到两个 DP 状态。
5. 根节点没有父边,输出 nC+dp[1][0]nC+dp[1][0]nC+dp[1][0]。
费用公式逐项对应原题:nCnCnC 是假设每个站点单独成路的固定费用,保留一条边会减少一份派车费并增加 www,度数不超过 111 的点恰好是路径端点或单站点,因此最后一项正好表示服务费。
固定 uuu 的父边状态后,各个儿子子树之间没有其他连接,子树贡献可以独立相加。uuu 的总度数最多为 222,所以父边不保留时最多选两条子边,父边保留时最多选一条子边。程序枚举这些全部可能,并在固定选择数量时取最小增量,因此两个状态都取得最优值。
由叶子向根归纳,根状态覆盖所有合法路径划分,最终答案正确。
每条边只被处理常数次,时间复杂度为 O(n)O(n)O(n),空间复杂度为 O(n)O(n)O(n)。费用和增量使用 long long;迭代遍历可以处理最长链。
* 单站路径的服务费只收一次。
* 一个点最多连接两条保留边,不能让它成为三条路径的交汇点。
* 不能只保留负增量边。
* 所有站点都必须被覆盖,不能只求一条最便宜路径。
部分分
* 测试点 1~2(特殊性质 S,10 分):树是星形,最多保留两条边,枚举选择数量即可。
* 测试点 3~6(n≤18n\le18n≤18,20 分):枚举边子集,检查每点度数并直接计算费用。
* 测试点 7~20(无额外限制,70 分):使用父边状态的树形 DP。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
YUILICE 的共用设备
题意简述
有 nnn 个任务,第 iii 个任务耗时 tit_iti 。每一批可以同时执行 111 到 333 个任务,批次耗时为其中最大的任务耗时。给出 mmm 对冲突关系,同批任务中的任意两项都不能冲突。每个任务必须恰好执行一次,求总完成时间最小值。
解题思路
解题方法
批次之间只能顺序执行,所以总时间就是每个批次最大耗时的总和。任务的具体批次顺序不重要,只需要划分集合。
用二进制集合 mask 表示还没有安排的任务,令 dp[mask] 为安排这些任务的最小总时间。固定 mask 中编号最小的任务 iii,枚举它所在的批次:
* 只放 iii;
* 放 iii 和一个任务 jjj;
* 放 iii、jjj 和 kkk。
检查批内每一对任务都没有冲突,然后转移到移除这些任务后的集合。固定最低编号任务后,每个划分只会被枚举一次;枚举第三个任务时限制 k>jk>jk>j,避免重复。
无冲突的部分分可以排序后每三个任务分一批。完整数据使用集合划分 DP。
1. 用位掩码记录每个任务与哪些任务冲突。
2. 按 mask 从小到大计算 dp[mask],空集合的值为 000。
3. 取出 mask 中最低编号的任务 iii。
4. 枚举与 iii 合法的单人、双人和三人批次,并更新 DP。
5. 输出全集 dp[(1<<n)-1]。
任意合法划分中,最低编号任务 iii 都恰好属于一个大小为 111、222 或 333 的批次。程序枚举了这个批次的所有合法成员组合,因此不会漏掉最优方案。
移除这一批后,剩余任务形成规模更小的同类问题。若剩余划分不是最优,就可以替换成更优划分而不影响已经选择的批次,矛盾。因此转移中的子问题必须取 dp 最优值。
反过来,每个转移都只加入合法批次,并与一个合法的剩余划分拼接,所以不会产生非法方案。按集合大小归纳,全集状态就是全局最优答案。
状态数为 2n2^n2n,每个状态枚举至多 O(n2)O(n^2)O(n2) 个双人或三人批次,时间复杂度为 O(n22n)O(n^2 2^n)O(n22n),空间复杂度为 O(2n+n2)O(2^n+n^2)O(2n+n2)。n≤18n\le18n≤18,答案必须使用 long long。
* 三人批次必须检查三条冲突关系,不能只检查固定任务与另外两人的关系。
* 不能看到三个互不冲突的任务就立即成组,剩余任务仍需要全局最优。
* 固定最低编号任务是为了去重,不是限制最优方案的任务顺序。
部分分
* 测试点 1~2(m=0m=0m=0,10 分):按耗时降序排序,每三个任务分一批。
* 测试点 3~6(n≤9n\le9n≤9,20 分):递归枚举合法分组。
* 测试点 7~20(无额外限制,70 分):固定最低编号任务所在批次,使用状压 DP。
参考代码
有帮助,赞一个