一个人的省选

· · 生活·游记

Day -?

开学，认识了 O(1) 个新同学，然后就拉去脱产了。

是这辈子第一次完全脱产学 OI 呢。

NOIP 考得很炸裂，基本上 E 类已经与我无缘了。

但我仍抱有一丝希望。

至少在 Day 1 结束前。

Day 1

键盘敲得我好难受，直接上巨大的 debuff（？）

开题，很快胡了 T1 的二分做法，10min敲完代码后发现过不了样例。考场上为了求稳，改成了离散后前缀和的做法，9：20 时通过了大样例，十分钟后对拍上了。

9:35 时开了 T2。

DAG 判联通是经典问题，先套个 bitset 再说。

首先当序列没有修改时，可以按值域分块，复杂度 O(n \sqrt n+\frac {n^2} \omega)。

对于有修改的，好像再套个询问分块就完了？每 B 个询问一块，那么这一块中就只有 O(B) 个数有修改，对于这部分直接暴力，总复杂度就是 O(n^{\frac 5 3}+\frac {n^2} \omega)？

我会了 Day1T2？？？

考场上的我以为自己赢了。从来没有在省选模拟赛中场切 T2，这次，竟然做到了吗……

光速开写，20min 写完 3.5k 代码，5min调完所有错误，当过了 n\le 2000 的样例时，我的手都在颤抖。

为了求稳，我先测了 n\le 6\times 10^4 的样例。

欸？？？怎么程序跑不出来？

30s 后，我的程序才缓缓跑出结果。这我***

然后开始红温。

从10：10到12：20 我一直在卡常和破防的边缘徘徊。

12：20 受不了了，打了个 T3 暴力，回去继续卡常。

比赛就这么结束了。100+20+8。T2 与暴力老哥同分。

出来看了下 LA 群，原来 T2 O(n^2) + 乱搞能有 80 分啊。

哦，那我连暴力老哥都比不上。

跟 Day1T2 出题人爆了。

下午一直颓，晚上打了场 abc，出乎意料 rk45。

Day 2

随便玩玩吧。

8：30 开了 T1，想到了拓扑排序，然后过了 30min 发现假了。（我怎么经常想道假做法然后过很久才发现……）发现直接贪就完了，又用 20min 写完 3kb 的线段树二分，没调试，直接过了。

没有拍，对自己的代码实现还是挺自信的。（？

开T2，生成树唯一直接 dp 就完了，剩下的，剩下的怎么都不会了……

期间想了 O(time) 个假做法，都被自己 hack 了。

最后无奈写了 24pts A性质+B性质，跑去看 T3，除了暴力一点思路都没有。

最后100+24+8。

In The End

288+100+88+8+100+16+8，Day2莫名奇妙fst了？