Day 0
下午准时到考场试机,结果刚到就被百日誓师给震撼了。
试机时发现电脑是 32 位机且不能运行程序,结果重启了就变成了 64 位机。
打了 tarjan、平衡树等板子后就跑路了,晚上在粥馆玩了谁是卧底,@ lazytag 被疯狂针对。
跟着 chery 去彩票店攒 rp,然后就回酒店玩了一局桌游,7 个人抽出 5 个自恋狂是什么操作,大概在 10:50 左右睡的。
Day 1
进了考场后先打了快读快输和对拍板子,打开题面后先把 4 个题都读了一遍,第一感觉 T1 和 T2 都是憨憨题,被 T3 的凸多边形给吓到了。
正序开题,T1 只用维护每行每列最后一次修改就行了,快速打完后发现大样例 fc 挂了,害怕不是格式原因去改了输出格式,结果还是挂的,耗了很久后确定是还是格式问题,就没管了,大概用了 30min。
开 T2,刚开始我很 naive 地认为只用枚举次数然后开 \(k\) 次根就行了,结果刚开打就发现会算重,之后就走了歪路,没想清楚算重的情况长啥样,以为容斥系数跟质因数个数有关,直到手玩了几个数后才意识到算重的一定是倍数,直接容斥就行了。
然后开 T3,可能被凸多边形震慑到了,没有任何思路,手玩了四边形的情况,发现一定走相邻的点,然后就不会扩展到多边形的情况了,但发现状压有 60,特殊性质感觉比较简单,先去看 T4 去了。
发现 T4 的 k=1 和 k=2 都是送分,\(k=3\) 二分很显然,但 check 想了很久都不会,突然发现可以沿用 \(k=2\) 的想法,考察全局最大最小值,它们一定不在同一行上,这样有一行的最大值确定,一行的最小值确定,另一行可以有哪些值也是确定的,于是可以枚举最小值类似扫描线修改每个位置的值,可以做到 \(\mathcal{O}(n\log V)\)。
决定先把会的分都打了,先打 T3 状态压缩的 60,然后打 T4,发现 \(k=3\) 并不好打,需要考虑最大值最小值在哪一行以及确定每一列有哪些数可以选,\(check\) 时为了方便用了 sort,复杂度多了个 log,打了很久才打出一份大常数代码,对着小数据调了很多小错误,终于在还剩 1h 时过了大样例。
此时摆在我面前的有两个选择:去做 T3 的特殊性质和 T4 \(k=4\) 的暴力,但害怕 T3 想假了,再加上 T4 的分多一些,还是去看 T4 了。
想了一会 \(k=4\),发现可以仿照 \(k=3\) 多枚举一行的最小值做到 \(\mathcal{O}(n^2\log V)\),很毒瘤,但还是冲了上去,打完了还有 20min,大样例一个没过,调了一会后过了前几个,但有一个 \(n=9\) 一直 RE,最后 10min 一直在挣扎找 RE 的地方,但是却出现了经典情况:删掉某个调试后就不 RE 了,显然某个位置越界导致 UB 了,直到考试结束都没找到。
出了考场后询问了其他人的情况,\(Sword\_K\) 30min 暴切前 3 题,但还是不会 T4 的 \(k=4\),\(cool\_milo\) 和 \(liuhangxin\) 切了 T3,发现自己还是太菜了。
下午晚上都在颓废,中途发现洛谷和 inf 上都有了民间数据,去测了测,好在没挂分,这对我来说很难得了。
联合省选 \(rp++\) !
upd:T4 偷懒用了 memcpy
在某些OJ上会 TLE 15分,希望 CCF 不要卡!!!
upd:官方数据:挂了 5 分。