CQOI2021 游记

人生第一场省选。 先拋结论：我是人间之屑。 正常的算法想不出来，暴力还敢写挂。服气了。 ## day0 星期四，隔壁高二机房有说有笑的，甚至还有人带头在老师面前打起了枪战。 也说不清楚有多少个人会就此离去，还是感觉挺悲凉的，转瞬间他们就从高一的精神小伙变成如今的老年选手了。 还好我才初三，还有救。 回家不准备复习了，摸鱼的时候看了命运石之门的前几集，~~我没觉得无聊啊？~~ 好家伙我直接好家伙。 ## day1 万恶的根源。CQ 考 A 卷。 我的习惯是先把所有题看一遍，部分分想完再开始打。~~这一想就想进了粪坑里~~。 看完一套题之后，发现都小清新的不得了，这个时候就开始慌了。然后我就做出了我最错误的决定 —— 爆肝 T2。 于是，一个小时过去了，两个小时过去了，~~甚至 CQ 的停电都没能阻止我爆肝的脚步~~，快要 11 点的时候，脑子快成浆糊的时候，我发现事情不对了。 老苟题。 我留下了这句判断去干 T1，还好脑子还没被 T2 彻底搅糊，早就发现只有可能从两边删，然后发现只需要二分答案，搞个双指针扫一遍就是 $O(n\log V)$ 的了。 这一场挽尊的决定出现了。我决定给自己的 T1 写一个对拍，因为为了保险，我在爆肝 T2 之前写好了 T1 的 60 分暴力，现在派上用场了。$1e5/1000$ 的数据拍上之后，我就去接着爆肝 T2 去了。 过了一小会，我打开那个对拍的 exe 窗口——**拍出来了**。当场直接吓出冷汗。 换成 $10/rand$ 的数据，过了一小会出来了一组，然后发现是双指针没判全。（这还过了大样例）。还好这 100pts 保住了。 爆肝 T2 到 12:30，叉掉自己的无数个假算法，还是一分都得不到。 去干 T3，得到了一个优秀的（反话）$O(n^3m)$ 暴力！然后试图优化也没优化出来。后来去试着跑了跑大样例。 因为剪枝，跑完只需要 1.2s 令我感动，但答案错掉让我冷汗狂飙。 调调调，调到最后仿佛调出来了？没来得及看就黑屏了。 估分 ： 100 + 0 + 0 = 100。直接心态爆炸。 同级的考的都比我好，这就是人间之屑的水平吗…… ## day2 开场全部开完，然后发现 T2T3 暴力分很足，T1仿佛是个奇怪的数据结构，准备先打完 T2T3 然后爆肝 T1。 这是我这场考试做的最好的决定了。 先来 T3，暴力每次删点就是 30pts，大力分讨一波树的情况 15pts，45pts 到手就跑路了。 再来 T2 ，我靠这不暴力 next_permutation 莽上去都有 60pts？爱了爱了，10 min 写完跑路。 来说说 T1 的心路历程吧。 首先就发现了每一种宝石只会在收集器里面对应一个位置，说明每一个位置如果钦定他这个位置收集了有用的宝石，那么后来应当收集什么是固定的。 然后就出现了大多数人写的 $O(n\log^2 n)$ 树剖 + 倍增。但我没有。 当时脑子里不知道出了什么问题，看到那个 m,c 的 5e4 之后根号就印在了我脑子里。即使想到的是 $\sqrt n$ 也毫不犹豫的去打了…… 就是重链上处理每个点作为开始，向上跳至多 $\sqrt n$ 步和向下跳到达的每一个点，然后每一条重链上都这么跳。 因为要找第一个可以接上的点，所以需要每次跳链都在颜色的 dfn 序 vector 上 lower_bound，这里有一个 log。复杂度分析出来是 $O((n+q)\sqrt n + q\log^2 n)$。 极其难写，写出来像个 * 一样，~~长度刚好4888~~，12:42 分过了大样例，跑 1.1s。 造了一下链跑的也不慢，心中默念少爷机加油。 估分 ： 100 + 60 + 45 = 205，还好没彻底身败名裂。 总估分 305，但是好像又炸了分…… ___ 还是大考经验太少了，之后对 day1T2 干出来的傻事绝对不能再犯。 同时思维题不够，套路练得也不熟练……感觉自己到处都是毛病，是时候加把劲了。 El Psy Congroo.