联合省选2022

· · 个人记录

Day1

T1 是个小模拟，应该能过。

T2 路径是吧，那就点分治 原来 n\le 200，K 大，待会再来想。

T3 像个 flow 但是数据范围有点大，暂时不会。

T1 直接拿 Trie 存宏递归就行了，懒得回溯直接传了个 bitset 进去。结果还写挂了几个字符。。好在没出大锅。前面一共花了 1.5h。

T2 先考虑给定一些区间怎么做。枚举最大值恰好是哪个，可行的最小值在一段区间内取。然后如果没有“恰好”限制，答案肯定是关于右端点的分段函数，每一段是一个多项式。再容斥一步，拿 K 的方案减去 K-1 的方案就得到了恰好的限制。

然后这个路径，发现可以类似树形 DP，对每个点求 F_u,G_u 为分段函数，F_{ui} 等于子树内选一条路径延伸下去并且右端点不超过 i 时左端点的方案数，G_{ui} 表示第二问答案。由于只需要求路径，不需要用 V-E 容斥之类的黑科技，只需要在 LCA 处统计答案。合并大概就是分段函数加和乘一下。复杂度它不重要 分析了一下像是 O(n^3) 带大常数。

口糊完了，冲了 1.5h 正解，喜提 6.5k。样例不出意外地挂了。发现拉格朗日差值预处理写挂了，漏抄了点东西。然后还是挂，只能花 10min 写个暴力。眼看就 11:50 了，这波怕不是要抱零了。暴力又调了 10min，最后终于弄完了暴力，把 f 输出了一下，正解大概是分段乘的时候没有把最后一段 0 给乘进去。经过长达两个多小时的奋斗，终于把这题大样例过了，不开 O2 跑了 0.8s。

这个 T3 有点烦人，想了想 A 性质发现普通网络流做法都不太行，然后想了一秒钟 B 性质（早知道就想两秒钟了）发现不会。C 应该是留给会做的人的，直接放弃。于是三个性质都不会，只能去拿那状压可怜的 8 分

并且成功写挂变成 0 分。

Day1 不知道该说打得好还是不好。个人感觉策略上问题有点大，这个 T2 没有先写暴力而是先写正解（虽然暴力只从正解那里改了 10min），导致最后一小时非常慌，当时的感觉就是这题要么 0 要么 100。最后有惊无险拿了 100。（导致过于紧张最后 8 分没有拿到）

不过听他们说 200 已经很高了，因为 T2 几乎没人切。而且有些人 T1 挂了。已知最高分是某位队友 220。

受到这个 T2 的影响几乎一整天都在手抖，打游戏都没法打，晚上实在没办法只能拿出所谓的催眠书《Neuromancer》看了会才静下来

分析了一下 Day1 的局势，莫得 DS，有一道数数，有一个好像是费用流。硬说有两道字符串似乎也很有道理 qwq。猜测 day2 会有乱搞，交互，DS，数学，预估简单一些。day1 成绩不错，大众分可能 150，基本上正常发挥能进了。

晚上享受长达 3h 的高质量睡眠

Day2

这都什么阴间场，一题不会。看来 U 裙昨天说的“你们想开点，说不定今天比明天好”是真的 qwq。于是抄起 T1 数数题就开想

2000 内一共有 333 个质数，这个问题等价于高位 FWT，唯一的区别在于 1 很少且有特殊性质。一行最多 4 个 1，但是就算只有 2 个也似乎困难。所以大概思路是想尽办法压缩 FWT 的位数。最后发现根号内只有 14 个质数，所以可以随便 FWT 了。最后实现使用了多次高维后缀和，复杂度挺高的，预计 [55,65]。

然后想了会 T2，第二个操作相当于告诉我们建括号树，并且同一层儿子顺序随意。操作一大概是把同一层两个儿子合成一个，把其中一个儿子的子树和自己扔到另一个儿子的子树里。然而这东西似乎啥都没用，根本无法决策。看来秒不掉，看 T3 去了。

这个 2GB 的空间已经让我认识到这几乎是一道不可做题了。仔细想了想确实不可做。链可以笛卡尔树上 DP，出题人却没有给。暴力 n! 滚粗。

回来康康 T2 的部分分。权值相等好像比较有趣，经过很久的讨论终于发现可以只跟深度的桶有关。因为被操作的子树深度不会改，只有当前点的深度+1 并变成叶子。也就是从上往下搜，每次留一个点在当前深度，其他深度等于当前深度的都变成下一深度的叶子。卧槽这不就是正解了么！！每次拿最小的点操作，留最大的点在当前层就没咯

所以这是签到题吗

回头给 T1 加了个记忆化防止出题人卡我（估计分也不会变）实际上是增加数据水的时候过的概率

以上均为口糊

Day3

D2T2 看错题了呜呜呜

只剩想的那个部分分了，一些特殊情况好像能过，看起来能过 x=y=1 的。小图灵拿了 20，如果 CCF 数据水可以多拿一点（？）

D2T1 写挂了一个地方 continue 的时候忘记把数组清空了。然后来了个大反转，我写挂的地方因为前面又写挂了一个地方，导致我那个写挂的地方根本不会执行，也就是没有挂。 世事难料啊

后来发现 D2T1 只要把一些东西预处理出来就过了

所以 Day2 是有点炸了，谁叫 Day1 把状态和 rp 用完了

由于 Day1 的超常发挥，加上 Day2 很多人 T2 抱零，T3 清一色的 n!，我在不挂的情况下大概省前三，挂了之后好像前五，因为几乎所有人都挂了而且比我挂得多很多

按照小图灵的估分是进了。只不过小图灵 D2T1 数据水给我过了，不知道 CCF 的数据怎么样。NOIP 的分差应该能拉回来

主要优势还是 D1T2 吧，鬼知道怎么在场上写了个调试之后 7k 的还过了