CQOI2021 游记

· · 个人记录

一次失败的考试,一次惨痛的经历,一个深刻的教训。

不要头铁。

upd: 记得算空间的时候不要忘了 \times 4(longlong \times 8)!!1

Day -2 ~ Day 0

这次省选在我们学校搞,不用跑到外面,爽(

打板子。黄队对着 NOI 大纲整理了 45 个板子,够三天打的了。

好多算法忘光了,重新捡起来了一遍。

Day 0 晚上跟外校大佬聊了半晚上,感慨还是挺多的。NOIP 落后队线 70 多分,这次 CQOI 应该也只是打着玩玩吧。不过万一能翻呢,万一...

Day 1

神 jiangly 来送考了,还亲自发了一波旺仔牛奶(((

进场没给密码,先码一个 NTT 板子。我不信今年没有多项式题。

8:25 的时候 NTT 板子刚好打完,也下发了密码。看一波题感觉 A 很傻逼,B 有点思维,C 不太会,于是先写了一波 C 的 16 分暴力,然后开 A。

感性理解一波觉得 A 可以直接枚举左端点,右端点的限制只有四种情况,可以 O(\log n) 算出来。然后就快乐开写。

写到大概 9:36 的样子机房突然停电,还是我们学校主办的,丢人()。趁这个时间想一波 B,想了个 m = 2 的错误贪心。

9:51 左右又来电了,但是因为交换机比较菜,开机什么的又开了五分钟。再写写调调 A,期间监考老师通知延时 30min。好鵺

11:00 左右 A 过了三个大样例,于是挂了个 n^3 暴力 dp 拍着(考试降智没想到 m^2 的傻逼做法,我是真的蠢比),然后去搞搞 B。

B 先把停电时的错误贪心给码出来了,没跑过样例,再细想一波发现根本不对。手推一下搞出了一个二分答案的做法(其实也是错的),准备开敲。然后 A 题出锅了!!1而且还不止一组而是三组数据出锅了!!1

看了看拍出来的错误,花了半个小时手摸了一波,惊讶地发现 A 做法锅了。然后我做了一个本次省选最错误的决定:硬刚 A。刚到 12:50 毫无收获,赶紧收手写 B 暴力。把傻逼错误二分答案给写了,然后在 13:29 的时候瞬间想出 n,m\le3 的做法,快乐遗憾离场。

估分:40+30+16=86,略低于大众分。唉。

心态爆炸。回家跟父母沟通了一下,调整了心态,教练又跟我聊了一波,心态逐渐平和。安详迎接 Day 2。

打了半晚上板子,一个没考。

Day 2

神 jiangly 又来送考了,又亲自发了一波旺仔牛奶(((

进场没给密码,先码一个 NTT 板子。我不信今年没有多项式题。

8:25 的时候 NTT 板子刚好打完,也下发了密码。今年确实没有多项式题。

看了一遍题,A 是道数据结构而且部分分巨多,B 数据范围看着不太对劲,可能是 O(2^nnm) 或者 O(3^nm) 之类,C 是我不会的一般图支配树,再细看一眼发现 n\le3000

吸取昨天教训,先把暴力打满。A 的 30 挺傻逼,写个倍增就跑了;B 枚举排列暴力 O(n) 判断居然给了 60,出题人专业防丢人;C 没啥太好的想法,只知道可以最暴力的 O(n^3/w) 算出每个点的支配点集,然后直接究极暴力 O(n^4/w) 计算答案。一开始觉得很傻逼考虑优化,后来仔细分析一波发现好像可以稳过 75,直接上手开码。希望数据给的随机一点,说不定能水过((((

搞完这些还剩 2h 左右,于是看看 A 能不能多拿点分。发现 50 可以拆成树剖区间做,爆码 3K 居然一遍过。仔细思考一下链的情况发现是傻逼并查集,大概思路就是正着扫一遍反着扫一遍这条链,每一次把当前颜色上的所有点合到下一个颜色上,再给当前颜色开一个点。快乐的开始写和对拍,快乐的写挂了,快乐的没调出来,快乐的跑路。

估分 :50+60+75=185,还挺行。

晚上跟红太阳以及高二的学长们出去聚餐,玩得很开心,被万恶的邓本主义压榨了一波劳动力()。只可惜这可能是我跟大多数高二的哥哥们的最后一次相聚了。

后记

随机数据下跑出来是 80+0+16+70+60+100=326,表现良好。但毕竟是随机数据,D1T1 和 D2T3 都没对我下手,官方数据十有八九不会这么良心。

另外,高二的哥哥们,后会有期。我最尊敬的选手 HenryHuang 黄老师,我在机房最好的朋友 konjacq 邓老师,还有谦虚的 wzhh 谢老师。

杨姐就不说了,这人进队稳如老狗。另外随机数据估了一波分,感觉黄老师挺可以进队的,希望如此。

后后记

D1T1 空间算错了,100 → 0,最后 0+0+16+70+60+75=221。D2T3 对我下手了,D1T1 已经不用他下手了,我自己来。(((

而且因为 NOIP 考爆了所以变成 321 其实也进不了队(((

杨姐就不说了,这人进队稳如老狗。黄老师直接爆砍 371 进队了!!1

可惜以后机房里还是少了 konjacq 和 wzhh 二人。whk 加油啊!