Sweetlemon 的博客

Sweetlemon 的博客

CEOI 2018 Day 1 总结

posted on 2019-07-01 17:23:17 | under 总结 |

快要 NOI 了,于是开始弄其他地方的题来写~

T1 clo (Cloud Computing)

题意:有 $n(n\le 2000)$ 种计算机,每台计算机有 $c_i(c_i\le 50)$ 个处理器核心,主频为 $f_i$ ,价格为 $v_i$ 。有 $m(m\le 2000)$ 个订单,每个订单需要 $C_i(C_i\le 50)$ 个主频不小于 $F_i$ 的处理器核心,收益为 $V_i$ 。现在要购买若干台计算机并接受若干个订单,求最大利润。

这题一看就非常像动规题的样子,一定很可做。首先想到的状态时 $f[i][j]$ 表示前 $i$ 台计算机、前 $j$ 个订单的最大利润,但是状态并不完整,剩余的核心数和主频都没有表示出来。

然后就想到网络流。从源点向每一台计算机连边,从计算机向可以满足的订单连边,再从订单向汇点连边——可是这样计算机就变成可拆分的了!又不行了。

最后经过较长时间的思考,发现其实题目并没有固定计算机和订单的顺序,也就是“前 $i$ 个”这种信息其实是不太有用的。于是想到排序——把计算机和订单混合起来按主频逆序排序, $f[i][j]$ 表示在前 $i$ 个元素中,剩余 $j$ 个核心的状态下所得利润的最大值。由于前面剩的核心后面一定还能用,因此就成了一个普通的背包了。

当然有一点要注意,就是主频相同时,计算机要排在订单的前面。

这道题我在考场上犯了比较大的错误:

  1. 数组大小计算不准确,导致数组开小,出现蜜汁RE,调了好一段时间才发现问题;改了数组大小后还是不够大,最终测评时又RE……
  2. 调试代码未备份原文件,乱改的代码进入最终提交代码中导致WA。

有四个建议:

  1. 一定要认真计算数组大小!
  2. 考场上想到的特殊数据要记录下来,提交前拿特殊数据检查一遍
  3. 出现问题,printf查错一段时间没有发现问题的,一定要坚持静态查错
  4. 调试要改代码时要备份原文件

T2 glo (Global Warming)

T3 lot (Lottery)