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$，菜出天际。