Score

65+0+100=16565 + 0 + 100 = 165

rank 15

Process

今天是考完学考的第一场考试,又有快一个月没有碰键盘了,但似乎状态没有想象中下滑得那么快?(因为本来水平就不高)

开场想了很久的T1,想到二分答案转化成二维平面上的问题,但是接下来的贪心没想清...最后写的网络流的暴力。实际上这个贪心特别sb,机房就我没A,很不应该

T3是之前费用流课件里的回路限制模型,写完卡卡常就过了

T2推了一些性质,但还是不够,导致没有想到正确的DP。并且考场上没有想出来暴力怎么写,想了很久费用流建图,但忘记了上下界费用流这个知识点

Summary

  • 分析问题不能浅尝辄止,要静下心来一点点想

  • 从最终答案的状态着手分析

Problems

清理通道 (clear) - 「IOI2013」Robot

二分答案,转化成二维平面上有一些点和一些线。每条竖线可以覆盖它左边平面的任意limlim个点,横线可以覆盖下面平面的任意limlim个点

把点按xx坐标排序,按xx坐标扫描线。只要碰到竖线,就要覆盖左边它还剩余的点(因为再往右走它就没用了)。而这些点的选取一定是按yy坐标从大到小选取(因为越小越有可能被横线范围覆盖)。这样考虑完所有竖线后,再按yy坐标从小到大依次考虑每条横线即可

砰砰博士 (peng) - 「IOI2017」Wiring

根据一些性质的挖掘可以发现,最终答案的状态是由若干个形如subtask2的块组成的

20-7-14-1

如上图就是由4个块组成的,每个块内部连边方案即为subtask2的方案

然后DP,设f(i)f(i)表示处理到第ii个数(第ii个数为当前最后一个块的右端点)的答案

subtask2计算答案的式子是(假设左边有nn个红点XiX_i, 右边有mm个蓝点YiY_i):

i=1nXnXi+i=1nYiY1+max{n,m}×(Y1Xn) \sum_{i=1}^{n} X_n - X_i + \sum_{i=1}^{n} Y_i - Y_1 + \max\{n, m\} \times (Y_1 - X_n)

处理到ii的时候mm是已知的,那么讨论一下nnmm的大小关系,分别用线段树维护DP值,区间取最小值即可

P.S.P.S. 正解是O(n)O(n)的我不会。这个做法看上去常数很大但跑得很快

P.S.S.P.S.S. 现在我会了,之前没有意识到 max{n,m}×(Y1Xn)\max\{n, m\} \times (Y_1 - X_n) 这一坨东西在确定了nmnm大小关系后是定值。。。

怪盗之翼 (wing) - 「BZOJ4261」建设游乐场

[TopCoder SRM570 900]CurvyonRails很像

先考虑怎么判断有无解。很明显,既然是棋盘,想不染色不二分图都难。染成黑白后,对于黑点,SS向其连容量为22的边,黑点向周围的白点连11,白点向TT连容量为22的边,判断是否满流就好了。

那么怎么计算代价呢?我们发现,如果要付出代价,那么一定是两个开口都给了同一列或者同一行,为了对此限制,我们拆点,分别管辖行和列。

如果这个点是黑点,我们向行对应的分身连一个容量11,费用00的边,再连一个容量11,费用vali,jval_{i, j}的边,表示如果只用一条边,不会产生费用,否则产生两条边的费用。列的话同理。

白点就不赘述了,其实也就是相较于反了一下,从分身连回本来的点。

跑费用流,不满流无解,满流输出费用即可。