2023-11-01 的模拟赛,应该是 jzyz 出的题,被爆杀

预估得分 100+20+20+10=150100 + 20 + 20 + 10 = 150

实际得分 40+10+16+0=6640 + 10 + 16 + 0 = 66

A 的复杂度假了,没卡过去,C 题题面没说捆 Subtask 结果数据捆了,D 题文件名写错了

赛后还发现 D 题的数据巨水,n2n ^ 2 加上优化可以过掉 10510 ^ 5 的数据,得到整整 70pts

哪个天才造的数据

阅读全文 »

题意

洛谷:link

nn 个任务排成一个序列在一台机器上等待完成(顺序不得改变),这 nn 个任务被分成若干批,每批包含相邻的若干任务。

从零时刻开始,这些任务被分批加工,第 ii 个任务单独完成所需的时间为 tit_i。在每批任务开始前,机器需要启动时间 ss,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。

每个任务的费用是它的完成时刻乘以一个费用系数 fif_i。请确定一个分组方案,使得总费用最小。

阅读全文 »

题意

现在有 nn 个工人要粉刷一段篱笆,每个工人可以粉刷包含 startistart_i 的一段最长不超过 lenilen_i 的篱笆(当然也可以不粉刷),每个工人粉刷长度为 11 的篱笆的收益为 costicost_i,求最大收益

阅读全文 »

题意

给定一个有 nn 个点的环(1n1×1061 \le n \le 1 \times 10 ^ 6),环上每个点有一个权值 viv_i,环上每条边的长度均为 11,求 max1i,jn{vi+vj+dis(i,j)}\max \limits_{1 \le i, j \le n} \lbrace v_i + v_j + dis(i, j) \rbrace

阅读全文 »

题意

洛谷:link

贝茜是一只非常缺觉的奶牛.她的一天被平均分割成 NN 段(3N38303 \leq N \leq 3830),但是她要用其中的 BB 段时间(2B<N2 \leq B \lt N)睡觉。每段时间都有一个效用值 UiU_i0Ui2×1050 \leq U_i \leq 2 \times 10^5),只有当她睡觉的时候,才会发挥效用。

有了闹钟的帮助,贝茜可以选择任意的时间入睡,当然,她只能在时间划分的边界处入睡、醒来。

贝茜想使所有睡觉效用的总和最大。不幸的是,每一段睡眠的第一个时间阶段都是“入睡”阶段,而旦不记入效用值。

时间阶段是不断循环的圆(一天一天是循环的嘛),假如贝茜在时间 NN 和时间 11 睡觉,那么她将得到时间 11 的效用值。

阅读全文 »

题意

给定一棵 nn 个节点的无根树(n2×105n \le 2 \times 10 ^ 5),每一条树上的边有一个流量,你需要选取一个点为根(源点),所有叶子节点为汇点,使得树中的最大流量最大(到达所有汇点的流量之和最大)

阅读全文 »