流星延停
$Day -\infty$
今年的 CTS 和 APIO 因为一些个人因素没有去.
这期间一边学 OI ,一边上文化课,月考凭借爆算苟了一个级 rk1 .
说起来这还是从初中开始的第一个 rk1 呢,算是完成了一个小心愿?虽然 rk2 拿了好几次…
$Day\ 1$
做题顺序 $1\to 2\to 3$ .
$T1$ 感觉 $70$ 分很可做,大力 $O(\max q\cdot n)$ 来 $dp$ .
不是 $DAG$ 也没有关系,时间那一维是没有后效性的,先枚举时间就好了.
然后又感觉后面的 $15$ 分也可以做,每个点按照所有的上/下车时间,将 $n$ 个点拆成 $O(m)$ 个点,这部分 $A=0$ ,贡献是线性的,所以对于原来一个点拆出来的所有点,连边时不需要两两连,按时间排序,相邻的才连边,然后跑 $Dijkstra$ .
感觉这个玩意细节处理起来比较麻烦,只有 $15$ 分,就先放着,去看后面两个题.
$T2$ 无想法,写了 $20$ 分暴力就放着了.
$T3$ 无想法,写了个 $28$ 分的 $O(n^4)$ 大力 $dp$ 就放着了.
回过去看 $T1$ ,发现 $\max q$ 只有 $1000$ .
算了一下,发现答案不会爆 $int$ ,这样开一个 $\max q\cdot n$ 的二维数组需要 $400\ MB$ 左右?空间限制是 $512\ MB$ ?
那直接 $O(\max q\cdot n)$ 行不行啊,感觉还有很多无效状态的样子.写了一发,开上 $O2$ ,发现大样例要跑 $2s$ .感觉可以寻址优化,于是把二维数组的两个维度交换一下,就只用跑 $0.5s$ 了.这东西能过?虽然不太清楚但也只能先这样了…
$T2$ 还是没有什么想法,但发现 $T3$ 费用流应该可以做 $n\le 150$ 的点,说不定 $n\le 2000$ 也可以过.
迅速建了个模,码码码…发现不对.肉眼调试了一会,发现没加反边.(蠢得离谱)
改过来,发现还是不对.调了一会,发现我求的是最小值.把费用改成负的,还是不对?
小数据调了一下,发现建模有问题,流量可以偷偷流走.调整了几波模型,发现流量还是偷偷流走.
可能就没什么时间了.费用流就破产了,把三道题的三个暴力检查了一下,卡了下常数,今天就结束了.
然后出去吃饭,黄学长还吃过敏了…
下午 $4$ 点左右有数据了.测了一下, $100+20+28=148$ ,没挂,
成功获得暴力分.
$Day\ 2$
做题顺序 $1\to 2\to 3$ .
$T1$ 感觉用 $kdt$ 建图就好了?然后发现空间 128 MB .跑了一波边数,发现开不下.
意识到出题人安排这个空间就是卡 $kdt$ 的?但是貌似想不出其他比较优秀的做法了…
只好头铁写了一波 $kdt$ .
看 $T2$ ,怎么又是 $landlords$ …先写了个 $10$ 分暴力,写 $dp$ 的部分分时候思路很乱,胡乱写了一发,过不了样例.调了一会,未果,只好放着了…
$T3$ 是个交互?自己似乎是第一次做这种带端口的交互(之前只在 $CF/ATC$ 上遇到输出命令来交互的题).
有点被吓到,冷静下来分析一波,发现前面 $5$ 个点就是暴力分,每个点改一次,再询问所有点,变了的就是与它有边的.
度数 $=1$ 的部分也比较可做,图是 $N/2$ 个点对,询问次数是 $N\log N$ ,提示得比较明显,每个二进制位都做一次,将当前二进制位为 $1$ 的点 $modify$ 一次,再询问所有点,若它的状态改变,说明它连的点这一位上与它相同,否则不同.
于是就有 $36$ 分的暴力了.
回过去再卡了一下 $T1$ 的空间,就结束了…
下午测了一波, $76+10+36=122$ .
后记
果然自己还是菜的真实,打 $\color{brown} {Cu}$ 了.希望明年能作为正式选手取得令自己满意的成绩吧.
结果官方测出来有 $286$ ?虽然还是打 $\color{brown} {Cu}$ 了.