CQOI2021游记

· · 个人记录

怎么说呢，还是太菜了。

Day 0

这时间怎么这么安排啊，月考考完就省选，考试当周没上竞赛课。

刚刚考完月考阴间英语吃完饭就出发去西附了，一个小时不到就到酒店了，在车上过了一遍模板，一进房间就开始上号直到睡觉。睡得挺早，十一点半就睡了，感觉还行。

Day 1

靠六点半就自然醒了，摸了半天（二十分钟）才起床，冲完早饭才七点半，和 hc、irc、tkz 巨佬一起散步过去了。

我竟然没看座位号就进去了，还好是在门口一下就找到了，这键盘跟学校的构造不大一样啊，Enter 要小一点。

开题。

T1 好像很水又有点眼熟的样子，但拿到题没有马上出思路，于是继续看题。CCF 怎么又出构造啊，但 T2 总体感觉有那么一点可做，各种部分分还多。T3 一看我一脸懵，感觉完全不可做，起飞。

干 T1，看完样例解释直接盲猜应该只翻左右两端的牌。稍加证明了一下感觉是对的，这样暴力枚举就可以做到 O(m^2)。又注意到了有那个部分分，猜想应该是对 O(m^2) 进行优化。枚举左端点肯定省不了，右端点又没有单调性，结果盯着看了半个小时想了各种办法都没做出来，我还是太菜了（所以是没有 O(mlogm) 或 O(mlogn) 的算法吧）。

于是直接去再读了读 T3，发现按题意模拟就可以拿到 16 分的好成绩，由于懒为了节省时间攻 T2 就没写 O(n^2m^2) 的 dfs，而是直接上了 O(mn^5) 的 Floyd 暴力开干，反正都是一样的。写完后考试已经才过去大概一个小时多一点点。

根据传统，构造题上来先把部分分打了找找规律或思路什么的，于是直接打了一波 n\le3 的部分分，打着打着电脑突然黑屏了，吓死我了，结果考场断电了。没错，它断电了。T2 又刚开有些细节还没搞，于是又想 T1，我真就对着它想就是想不出来，大概二十分钟过后来电了，监考老师宣布延时半小时。交换机启动真够慢的，我开个机又开了十分钟，刚打开时还很卡，我脑子里还一直在想 O(mlogm) 的 T1，大概搞到十一点才又放弃回去搞 T2。

感觉 T2 对数字大小的限制是真阴间，我打个 n=3 都分类讨论了半天。然后顺手就又去拿 m=2 的部分分，没错我算复杂度又把 T 给忘了，直接一边暴力 for 循环到 2\times10^6 干上去，一边感叹出题人暴力分给的足，其实是我太烂了。然后稍微想了下只有 01 的，写了一手。

然而我并没有找到什么规律，就只剩下一个小时了。我硬是啥思路都没有，真就一道 A 不了呗。场上估分 60+75+16=151。

考完后第一时间问 T1，巨佬们都用 O(nlogn) 爆切了，看来以后想不出来的时候应该换个脑子啊。green_orange 爆切 200+，clorf 甚至不出意外直接 AK 了（至少看赛后的题解思路应该是差不多的）。然后我发现 T2 只有 01 的部分分写挂了，那 T2 就只剩 35 分了。

还是太菜了，NOIP 又考得烂，算了一下，明天 AK 也不行，况且水平还差得远。

吃完饭直接回房上号，结果他们又开始打 splendor。上号上到五点半找他们去吃饭，结果他们说还早，我也去打了两把到七点才去吃 KFC，路上巨佬 PG 又毒奶一口明天要考字符串，我开玩笑说向 CF 靠近该考交互提答了。吃完回来一直打 splendor 到将近十一点，回房上了一小会号，十二点过就睡了，躺在床上又在脑子里过了一遍板子。

Day 2

我还是六点半自然醒了。照常。

开题。

过了一遍题，盲猜数据结构、状压 dp（这玩意太明显了）、Tarjan。由于自我感觉对 dp 比较擅长就先开了 T2。没错，我把求排名情况数都能搞成分配方案数，关键是我首先打的 O(2^nnm^2) 还能过前两个样例（第三个当然 TLE 了）？！于是当时我非常自信，觉得自己行了，直接着手优化，大概想了半个多小时搞出来了 O(2^nn^2m) 的，结果打上去发现一个样例都过不了。我还真硬整这题整了一个多小时，最终放弃了，把 O(2^nnm^2) 的又掉了出来。

感觉时间不够了，又感觉 T1 会比 T3 好写，于是直接对 T3 一手暴力加小推一下树的部分分回去干 T1。不知道是 Day 1 被二分整了还是什么，我直接想了二分，然后需要搞一些预处理然后 O(logn) 判断 p 二分出来的某个前缀是否是路径的子序列。预处理搞不出来，想可能会用到什么 SA/SAM 或者什么自动机之类的东西（我真觉得要考字符串了），不会，爬了，O(n^2) 暴力拿下人均分。

还剩一个半小时少一点，我执着于 T2 无法自拔，又回去调了半天始终过不了所有样例，直到还剩半个小时我才发现是求求排名情况数？！废了啊，直接一个感叹号贴上去还能拿 60 分，就只剩十分钟了。

我检查了一下又去想 T2，虽然我已经不准备打了。

出去没见到 clorf，不过他进队估计还是稳吧，PG 巨佬把 T2 卷掉了，irc 巨佬把 T3 卷掉了。我？省选真就陪考呗，一道题都没 A。PG 巨佬说 T2 复杂度是 O(2^nn^2m) 应该过得了，我这时候一下子就想到做法了，我真的是蒟蒻啊，果然 rp 守恒，模拟赛考得好，省选机房垫底。

我靠月考成绩这就出来了，手机上暂时还看不到。感受了 chery 的狂野飙车，一路上又在上号，回到机房直接开幕雷击，语文爆错 5 个选择题，喜提 113，英语更是直接起飞，竞赛和 whk 双丰收。

啥都还没测，估分 60+35+16+25+60+15=211，菜出天际。