GDKOI 2021 参赛总结

dqa2022 · 2021-01-31 21:41:27 · 个人记录

I. 前言

这个比赛已经变得相当 informal 了。

简单写写吧。

II. 时间轴

Day 1 1.29

• T1：给一张无向图，求划分成两个集合，使得集合之间的边数不少于一半。n\le 10^5。

• T2：给一个柱状图，求输出面积数组从小到大排序后的一个区间。n\le 3\times 10^5,R-L+1\le 3\times 10^5。

• T3：给一个字符串，每次询问一个区间的最长回文子串。n,q\le 5\times 10^5。

• T4：一个 n 个叶子结点的完满二叉树（非叶子都有两个儿子），叶子结点的权值是 1，非叶子的权值大多是 a，只有 k 个特殊情况，左儿子大小为 s_i 则权值为 v_i。一棵树的权值是结点权值乘积。求所有可能的形态的权值之和，对 10^9+7 取模。n\le 10^6,k\le 10。

T1 算是经典模型了。随机下每条边有一半的概率在割集中。可以加以改进，贪心增量构造（“去随机化”）。

T2 笛卡尔树的结构比较合适。可以二分出对应 rk 的权值，相当于是要把每个结点管理的权值（排序后）的一段区间挖出来，想清楚一点就能比较方便实现了。O(n\log V+m\log m)。

题解的做法是二分出下界，然后每个结点维护一个堆表示后继权值，每次取出最小值，再压入其后继权值，操作到足够为止。O(n\log V+m\log m)。

T3 manacher 后唯一问题就是边界上的可能越界。那么二分完答案就能解决了，因为只需要 check 一个答案，可以把询问的位置区间收缩到越不了界。可以用 ST 表平衡复杂度。O((n+q)\log n)。

感觉这些题质量一般般啊……

T4 卡 NTT，不然直接分治 NTT 一下都很可能过得去。那么要么就是生成函数搞，要么就是拿卡特兰数的组合意义等特殊性质搞。

后来发现有个地方没想清楚，这个东西似乎不是标准的卡特兰数。然后就想如果不带暴力修改怎么做。想了一堆乱七八糟的东西没有成果，去推了推生成函数，发现和卡特兰数就差了个 z^{-1}，啊这……然后马上脑补出一个简单合理的映射：DP 状态改记非叶子结点个数。至少能拿到 30 分了，不过因为这么一个 trival 的转化卡了这么久，果然是没脑子……

思路整体比较乱，后面没有什么新的进展了。

最后一点时间冲了一个分治套分治乘，复杂度应该是 O(n^{1.57}) 的，但是写出了一个小错误，最后一分钟不能去搞了。实际 5\times 10^4 跑了 10 s，反正都过不去，没有遗憾。

期望 & 实际得分 100+100+100+30=330。

后来和 zjr 大师讨论 T4，两人各提供了半个思路，拼成了一个有点奇怪的 O(nk^2) 做法。居然是标算方法。

大致是说把暴力替补的系数写成一个稀疏多项式 G，则

然后分段递推 F 的各项系数。段的关键点即权值修改点。段中间的递推可以直接用 ODE 的技巧做到 O(k^2)（根号里面的非零系数总数），段末的类似，只不过要考虑 [z^k]G(z) 的影响并更新 G，把未知量主元 [z^k]F(z) 移一下项，应该就能直接推出来了。

感觉还是挺妙的。自己推生成函数时没有想到，一则可能是前面思路比较乱，二则是因为觉得 G 也会变，所以没去仔细想。其实即使它是不确定的，也能推，只要移一下项。每个生成函数作为独立个体，其实本身有比较好的递推结构。

讲课讲拟阵，这个之前研究过，但是不是很深入，以感性为主。宜结合论文食用。

Day 2 1.30

• T1：一个计数器 c，每次有 p_c 的概率 c\leftarrow c+1，1-p_c 的概率 c\leftarrow \max(0,c-1)，求到达 n 的期望次数。n\le 10^6。

• T2：一张有向图，每个点 i 存在出边 i\rightarrow i+1 和 i\rightarrow a_i。多次操作，每次单点修改 a_i 或询问一个点的传递闭包中编号最小的点。n,q\le 10^5。

• T3：一个字符串，初始为空，每次可以在末尾添加一个字符，或者把某个后缀对称过去（奇偶回文皆可），都有对应代价。求形成给定字符串的最小代价。n\le 5\times 10^5。

• T4：一个排列，每次抽出一个区间，线性构造二叉小根堆（编号从大到小进行下滤操作），询问某个结点的权值，或者一个权值的位置。n\le 10^5。

T1 又是经典题。可以直接递推过去，从实际意义的角度理解，不可能出现主元问题。仔细推一推就发现分母是给定常数，可以线性求逆元。O(n\log P) 或 O(n)。

T2 一开始没啥思路，总想着维护树结构，甚至是维护树边的倍增，然后就难以自拔了。

T3 一开始想到那个记不太清细节的 PAM 上 DP 技巧（其实是出题人想要考查的），正觉得头疼，发现可以直接 manacher + 线段树优化 DP 搞过去，线段树可以非递归，常数很小。然后迅速搞完了。O(n\log n)。

T4 一开始想了一个相当简单的解法，check 了一下居然还没找出问题，然后把它实现出来了，这才知道是妥妥的假做法……这在这种手速场很不利，很容易打乱节奏。后面对 T4 的思路就开始混乱起来了，感觉可以从不同角度搞，不同角度有不同性质，但是想不清楚，可能只会一个四个 \log 的做法。

T2 没搞出来还是很头疼，这时改去想一些不太常规的方法。想到了定时重构，发现非常能做，而且常数小。就是把块内修改的边挖掉，然后递推出能到达的最小点，然后暴力跳带修改的边即可。O(n^{1.5})。

之后又在 T4 的思路上继续混乱下去了。

期望 & 实际得分：100+100+100+30=330。

T2 其实有非常简单的做法：每个 a_i<i 的返祖边都相当于一条线段，而询问相当于沿着已有的线段最左能走到哪里。然后就拿个数据结构维护一下就行了。O(n\log n)。第一感觉没找准，后面还是受很大影响……不过被根号的 alterative solution 救了……

T4 确实有一个转化：把倒序下滤改成按权值从小到大上滤，构造出来的堆等价。这样的好处是每次上滤到尽量高，就拆分成了两个独立的子树。那么就要跟踪询问的结点，从上到下来模拟 O(\log n) 次上滤。即每次求最小值，然后把它一路交换上去。至于最小值怎么单次 O(\log n) 求，则相当于 交换进来的 和 没有交换出去的 取 \min。前者只有 O(\log n) 个，后者需要分 O(\log n) 层做，并且要绕过 O(\log n) 个交换出去的结点，因此有 O(\log n) 个静态区间，可以 ST 表。这样就 O(n \log^2 n) 了。感觉是很妙很优美的题，并且思维发散性较强，有难度。

讲课讲随机化和概率论。还是学到不少的，不过对于一些较复杂的分析还是不够熟练，要加大一下力度。

Day 3 1.31

• T1：一棵树，点带点权，求所有路径对的交的点权 \text{lcm} 之积。n\le 5\times 10^5,V\le 5\times 10^6。

• T2：两个序列 a,b，一个区间，如果其 b_i 之和是正的，则对 ans_{\sum a_i} 有贡献 1，如果是负的，则是对 ans_{-\sum a_i} 贡献 1。求 ans 数组。n\le 10^5,|a_i|\le 1。

• T3：初始有 n 个格子是黑色的，下一时刻格子的颜色取决于本时刻四连通的黑色个数奇偶性，奇数则为黑。求 [L,R] 时刻的黑色格子个数和。n\le 15。

• T4：一张无向图，记 dis_{i,j} 为两点之间最短路长度。求划分成若干个集合，满足集合大小下限 lim，且集合半径最大值尽量小，要求构造方案。集合 S 半径定义为 \min\limits_{u\in S}\{\max\limits_{v\in S}\{dis_{u,v}\}\}。n\le 200。

觉得这一场难度不太对劲，但是又拿捏不太准。同时，也感觉到连续打几场，反应能力和判断能力都在不断下降……

T1 显然要质因子独立做。大概是把质因子的虚树建出来，然后一个方案的系数指数为交上碰到的最大指数的关键点。再线性性拆分一下，变成了只要是经过关键点就有贡献。然后不知道为什么，想了很久没想清楚具体怎么算贡献，直到很久之后才编出一个算贡献的做法，并且要分一万种情况讨论（精细实现复杂度 O(n(\log n+\log V))）。这种情况下很可能是做法搞复杂了，如果硬冲成本很高，所以又在想怎么调整一下。没有什么可观的调整，并且时间浪费得有点多，还是比较急的。

插 T1 的空想 T2，首先想了半天，才反应过来，是一个 FFT 题。然后又意识到自己的想法本质上把正负贡献分别求出来了，限制更死了，因此通常走不通。后来又是思路比较混乱，编出一些看似有点道理的假做法，还在想可能是一堆分治套在一起，或许拿根号平衡一下 \log。

前面用了相当多时间构思前两题（大概有 90 ～ 120 min），后两题看起来就不可做，没有仔细想正解。

后来想，要不要冲一发 T1。刚写一点真的不太敢写了，感觉是在破釜沉舟。高爸跟我讲过，如果时间比较紧了就不要花太多心思去冲一些风险较大的分了，考虑自救。于是把三题的暴力写了（T1 高一点分的暴力和正解比同样难写，推到最后还没搞完）。还没把暴力写完，就结束了，何况去冲码农题，其实策略应该还是对的。

就这么结束了。期望得分 0+20+25+40=105，实际得分 0+60+5+20=85。T4 条件没看仔细，少了一个 task，T3 估计规律没找准，T2 暴力常数小多过了很多点。

NOI 2020 Day 2 是不能，也没有重演了。不过对于工作量大、难度高而集中的场次，还是有一种应对的无力感。还是需要变得更加成熟，才能更好面对挑战性更大的任务。

T1 差不多就是我那个做法，而且好像比我还要麻烦一点，不提。

T2 其实正、负都考虑，就是放宽了区间 l\le r 的限制，因此大可以把位置限制解除。剩下就是按 b 排序，a 后面减前面的，贡献答案。可以分治 + FFT。不过 FFT 长度固定，因此要小范围暴力，平衡复杂度。O(n\sqrt{n\log n})。

T3 图的形态是不好维护的，但是为什么要维护图的形态呢？一个点的状态就是所有初始点通过某个时间段的移动拓展到该点的路径数的奇偶性。然后可以借助 Lucas 定理相关的知识简单而形式化地描述出来。多个不同的初始点，可以考虑容斥。要求 [L,R] 的贡献和就套一个数位 DP 即可。

T4 前三个包都比较 trival，第四个其实是“可以得知确切答案（或更大），但是只能构造出确切答案两倍以内的答案”。二分答案 k 之后，考虑分两个层次做：一是保证半径，二是保证每组内数量。第一个可以直接贪心，每次选一个点为中心，然后剥掉尽可能多的点，使得距离不超过 2k；要解决每组下界的问题，则比较自然考虑走若干“增广路”，把组内太多的换到组内不够的。可以证明在二分阈值不小于答案（半径长度限制）的时候能构造出半径限制为 2k 的解，反之显然不能。

我按自己的思路梳理了一下，只要每次从多的组中尝试把一个点直接换到少的组即可，如果不能则无解。原理也是类似的。复杂度也正确。

这里写的都是大体思路（并且还没仔细想并实现过，因此比较粗略），希望有助于感性理解，细节可以看官方题解。

感觉（自己想）还是挺难的，但是（理解起来）好像又不是很难。

讲课讲生成函数和多项式。查漏补缺？

III. 反思与展望

三天分数 330+330+85=745，算是排得上号，但还是不怎么满意吧。

其实水平没有什么大问题，但是总是在一些细枝末节，或者是高精尖的部分打点折扣，导致这里少一点，那里少一点。

还是要加强训练，不断提高综合实力。然后考场上的紧迫性稍微松一点，不然适得其反。此外遇到题目不要有“难”的预设，不然影响做题心态。

其他可能和《WC 2021 参赛总结》比较重合，我也写累了，没必要搬运一次了。

敢问路在何方？路在脚下。

2021.2.6