CEOI 2018 Day 1 总结

快要 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)