省选联考 2021B卷 游记

Vocalise · 2021-04-09 01:03:03 · 个人记录

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 分应该拿不到了。

更新 Day1: 40 + 60 + 16 = 116

两天 [181,201]。

第二天的教训是：

• 不要对着一个题死磕，要估算自己多久没有思路的题就不能再想了。
• 部分分考虑周全，不要留着题不写。
• 开始考试就要规划好时间。

大意失分的有：

Day1 T1 60分，Day2 T3 60分暴力。

假如加上：[301,321]。这成绩还有希望。

其实不就是菜吗！！！

退役了。