Day \((-\infty,-1]\)
在深中快乐玩耍。
可能是因为打了 3 天 JOISC 被打爆了的缘故,*回到 OI 开始做题&打模拟赛。
发现自己做不动题了,迟早要完。
Day 0
从深中旁边的酒店搬到马耀华中学旁边的酒店,过程中把手机充电线落在原来房间了,于是手机电量有点危险。幸好是充满了再弄丢的(
新酒店有充电线但是要钱,就很离谱……
下午复习了一下注意事项,然后就浪过去了。
晚上复习了多项式全家桶和洲阁筛,但是两个考的概率都很小。我觉得省选不会考计算几何(
复习了的都不会考,所以只要学弟把所有知识点都复习了,我就什么都不用复习了!
11 点睡觉。
Day 1
上午
七点起床,睡了 8 小时少一点,不是很精神。
早上在酒店吃早饭的时候面到了 cmd ,另外还在电梯里遇到了中山一中的哥哥们,然而叫不出名字((
到考场已经 8 点了,面到了 dqa 和 zjr 。例行上厕所之后进考场发呆。
8:28 允许动键盘,于是直接开冲板子。但是这键盘敲不出多少声音没法恐吓对手。反倒是坐在对面的 cdw 敲的巨大声。
T1 第一眼枚举前缀,但是不太会求最优后缀。第二眼二分答案+2sat ,但是常数巨大不可能过。
自闭了几分钟发现枚举前缀+树状数组好像就做完了,于是开冲。40min 的时候过了大样例,非常自信于是直接去看 T2 。
T2 怎么直接就构造题了啊……我要有信仰,我不开 T3 。
感受了一下,感觉好像见过差不多的模型,应该确定第一行第一列之后其他元素都会有不太难看的形式。
手玩出了 \(a_{i,j}=(-1)^{i+j+1}a_{1,1}+(-1)^{i+1}a_{1,j}+(-1)^{j+1}a_{i,1}+C_{i,j}\) ,其中 \(C\) 是关于 \(b\) 的常数。需要 \(a_{i,j}\ge 0\) (此时还没意识到需要 \(a_{i,j}\le 10^6\) )。
发现里面有三个变量于是暴毙了。但是要有信仰,这东西一定是差分约束(((
继续感受了很久,发现好像只需要确定第一列。
继续推,发现好像把奇数 \(i\) 的 \(a_{i,1}\) 取反之后真的就是差分约束了,我感觉我又行了。
这时候发现还要 \(a_{i,j}\le 10^6\) ,心态有点爆炸。冷静了一会发现好像竟然还是差分约束,只是又多了一倍的限制。
开冲。分类讨论把我人写傻了……
过了样例,但是随机有解数据都能挂,于是又调了很久。终于在 2.5h 的时候拍上了。
T3 给了个神必操作,但是仔细思考发现限制其实非常简单。
枚举起点就可以直接做到 \(O(nm)\) ,于是先冲暴力。写完发现要跑 2s ,感觉有点不爽。
冷静一下发现“路径上不能有编号小于起点的点”这个限制好像和 floyd 有点契合,甚至还可以减小一点常数,于是尝试把 floyd 和 \(O(nm)\) 拼在一起,发现好像确实能拼。我可以编号较小的枚举起点,编号较大的直接 floyd ,获得 \(O(kmn+((1-k)n)^3)\) 的阴间复杂度。
本来以为 floyd 最多跑个 600 左右,结果写完发现 800 只跑了 0.5s ,剩下 200 交给最短路处理。
迷惑的是,这 200 也跑了 0.5s ,而我竟然没有想到把剩下 200 也丢给 floyd 。
于是获得了 80~100 的随机分数。
最后 20min 感觉不拍 T1 有点虚,于是写了个拍。拍了 5min 竟然拍出来了!!!
发现把 pre 写成了 suf ,改掉之后就拍上了。
正解不对拍,爆零两行泪。
下午
又见到 dzd 了,没白来!!1