Codeforces

Pro: 4/5/11

Rank: 13/19

给出$n$个物品,每一个物品有一个重量,现在要把这些物品分成三堆,使得最大堆物品的重量和与最小堆物品的重量和的差最小,求分配方案.

显然,最后的答案不超过30(也就是物品的重量上限),所以可以猜一个范围然后DP.

记$f[i][j][k]$表示已经分配了前$i$堆物品,次大堆比最小堆重$j$,最大堆比次大堆重$k$.然后按顺序枚举物品进行转移,同时记录下转移路线即可.

为了方式特殊数据卡掉可以在最开头加一个random_shuffle

有一些容器,问能不能用这些容器倒出体积恰好为$A$的水.每一次可以选择倒满,倒空一个容器,或者用一个容器向另一个倒水直到倒满或者倒空.

分析后不难发现是一个拓展欧几里得的模型,有解的条件就是这些容器的gcd能够整除$A$.然后可以钦定让最大的容器往外倒,剩下就是一个类似爆搜的东西了.

签到题

给出一系列的$c_{i}$和$d_{i}$.然后有一些询问,每一个询问会给出一个$a$,$b$,对于每个询问,找到一个$i$,使得$ac_{i}+bd_{i}$的值最小.

化简一下后发现是一个凸包,在上面进行查询就可以了.

有一个插座和一些插线板,以及一些要用点的电器.每一个电器有一个安全系数,当且仅当这个电器与插座间的插线板数量不超过安全系数时,才可以正常工作.问最多能让几个电器正常工作.

二分答案,优先满足安全系数较高的电器.

前期的开题策略有一点问题,发现G是一个凸包并且可做之后,应该稍放一放,优先跟榜写J.发现J题思路越想越复杂之后更应该直接换人而不是一直顶着WA提交,中间浪费了不少时间导致A题没有调完.之后做题人员轮换要果断一些,及时止损.