省选联考 2021B卷 游记

## Day 0 ### 凌晨 NOIP 挺炸的，几个月以来都挺颓废。 学了一些有的没的，但是思维感觉没有得到任何提升。 两天时间打了一些板子： 线性基；扫描线；manacher；SA；SAM；高斯消元；杜教筛；Treap；无旋 Treap；CDQ；树套树；Pollard_Rho；NTT；多项式逆对指数。 Dinic 几天前也写过。 半个没有用上。 图论，字符串，DP 还是等于没学。 树分治还没学。 祈祷。 ## Day 1 ### 上午 起得晚了一点，8:20 的时候到了楼下，但是找不到机房在哪里。 游荡到只有 5min 才进考场。 已经发题目了。于是先看了下题目，T1 秒了，T2 感觉可能可做，T3 不可做。 然后改了 vim 缩进 tab 之类的配置。 T1 就是 $O(m\ln m)$ 的枚举倍数。花了 5min 写完，但是还是 naive 了，没有想到重复的数要去重。 沦为和暴力老哥同分。 然后求稳，用 $O(n^2)$ 暴力拍了一下。 过去 15min。 T2 想了一下，尝试了一些假做法，并且用 Dfs 过了前两个点。然后就总共过去了 1h。 决定先做 T3。 前面 4 个点都是非常裸的暴力，觉得很必须写一下。 然后就开始写并且调。 然后就又过了接近 1h，因为本身是暴力就肉眼查了一下。 想到 T2 $a$ 是单调的，就反应过来必须取连续的一段。 就开始写 $O(nm)$ 的做法，写完拍完就只剩不到 2h 了。 这个时候就开始考虑分治做，然后就想了个假的做法并且开始写，大概只有 20min 的时候发现是假的。 然后加文件，重新测试，静态差错，并且拍了前两组。 但是因为 T1 用的是 $O(n^2)$ 暴力，并且没有尝试极限数据测试，所以还是没看出复杂度假了。 然后就反复查，出来了。 吃完饭就发现 T1 挂了。 我人要无。 T2 的 $n\le 5\times 10^5, m\le 1000$ 部分分感觉很悬，但是给的大样例就是满的，能秒出，所以认为可能可以过去 $5,6$ 两个点。 不知道 T1 的部分数据范围，估分是 $[30,50] + 60 + 40 = [130,150]$ Day2 要注意的： - 改 vim； - 想到做法要确定是否假了再码； - 要用极限数据、手造数据测试； - 要算准复杂度，要注意有没有犯 sb 错误啊啊啊啊啊。 upd: 发现 T2 是 $O(m^2)$ 的...于是有 60 分了。 发现 T3 是 25 个点，于是只有 16 分了。 tmd T1 连题面都没有，只能猜是 $[30,50] + 60 + 16 = [106,126]$ 了。 - 要看对部分分... ## Day 2 进考场还有 15min。 发现电脑没有清空，还保留了昨天的全部文件。看了下 Day1 T1，发现只有 40，连暴力都不如。 写了个 treap。当然没有用上。 开题，发现 T1 非常 CF。根据经验，要不是一个 sb 结论题，要不是根本做不出来。 T2 树上问题，感觉可做。 T3 数数题，本来觉得可以做一下的，但是最终还是没时间。 出场发现人均可以暴力 60，我人傻了。 这个时候就已经有键盘声，对面一人拼命砸键盘。感觉挺搞的。 于是我认为 T1 全场切，事实上没有这么夸张（ 想了 30min，只会 $O(n^3)$ 30 分。 先去写 T2。先写了个 $O(nq)$ 暴力，25 分。 接着尝试想正解，不会。考虑（另外） 25 分的值域 $100$，发现向上的路径可以暴力匹配但是向下的做不到 /ll 考虑链部分分，发现没法预处理下一个匹配 /ll 但是看到值域 $5\times 10^4$，觉得这个非常像根号。 于是对于链上的情况考虑根号分治。 期间又在 T1 T2 间反复横跳。最终还有 1h30min 的时候搞出了一个奇怪的根号分治。 对于链上一个点，如果这个颜色在 $P$ 中出现为 $P_i$，考虑它之后第一个 $P_{i+1}$ 的位置为 $nxt_i$，之前记为 $pre_i$。 如果 $P_i$ 和 $P_{i+1}$ 出现次数不超过 $\sqrt n$，直接归并。 否则遍历一遍整个链计算。 前一种情况下每次 $O(\sqrt n)$，最多 $n$ 次，一共 $O(n\sqrt n)$，后一种类似，因为最多有 $\sqrt n$ 个大于 $\sqrt n$ 的颜色，也就最多有 $2\sqrt n$ 次遍历。 总复杂度 $O(n\sqrt n)$。实现起来要分 $nxt$ 和 $pre$ 考虑，当时没有决定写。 然后 T1 没有任何思路，T3 没看，痛失暴力分。 最后还有 30min 左右写完这个部分，调了一下过了一组手造，没时间了，就直接和暴力拼起来交了。 感觉暴力是稳的，不过这 20 分应该拿不到了。 $40 + [25,45] + 0 = [65,85]$ 更新 Day1: $40 + 60 + 16 = 116$ 两天 $[181,201]$。 第二天的教训是： - 不要对着一个题死磕，要估算自己多久没有思路的题就不能再想了。 - 部分分考虑周全，不要留着题不写。 - 开始考试就要规划好时间。 大意失分的有： Day1 T1 60分，Day2 T3 60分暴力。 假如加上：$[301,321]$。这成绩还有希望。 其实不就是菜吗！！！ --- 退役了。