联合省选 2022 游记

· · 个人记录

Day -1

打了一些板子，感觉手感还可以

Day 0

又打了一些板子，健康作息了一把

Day 1

进了考场啥也不能干，等到 8:20 发了解压密码，开始看题

花了不到 10 分钟完全理解了 T1 在干啥，于是决定拿 map+dfs 一下，然后就写了二十分钟，反正是过了样例，就扔在那里了，复杂度没仔细算，但感觉大概没什么问题

接下来看 T2，上来只会 10 分 n,k\le 5；然后就套路性考虑枚举最小值，但 k 太大了，然后发现式子是 \sum\limits_{min,max}\sum \limits_{u,v}\prod\limits_{x\in path(u,v)}(\min(mx,r_x)-\max(mi,l_x)+1)，是个分段函数，那么最大最小值的枚举就变成 O(n^2) 的了

想了想发现不行，因为最小值对最大值有限制，那就转化成 x\le ans_i\le x+k，再容斥一手减掉 x+1\le ans_i\le x+k 的答案就可以得到 \min=x 的答案

最后答案的形式大概就是 \sum\limits_{x}f(x,k)-f(x+1,k-1)，其中 f(x,k) 表示 x\le ans_i\le x+k 的答案，再把这玩意弄进区间应该就行了

考虑到如何维护分段函数，就相当于求 \sum\limits_{u,v}\prod\limits_{p\in path(u,v)}g_p(x)，g_p(x) 是一个最多一次的多项式，于是直接背包，需要维护树上每个点的多项式，最后加起来做一个自然数幂次和，拉格朗日插值一下就能做完第一问

考虑到这个东西 u 的多项式最多有 u 往下的长链长度项，肯定 \le siz_u，所以卡一手 siz，整个做一次的复杂度就是 O(n^2)

故而总复杂度 O(n^3)，可以完美解决第一问

但有个非常严重的问题，ckf 不会写拉格朗日插值，但考虑到只需要求自然数幂次和，可以把 n=130\sim 200 的各项系数直接打表，然后再程序内计算 n=0\sim 129 的部分，这样程序的大小就只有 65K，贡献了 BJ 代码 \dfrac 18 的大小（

最后跑的还挺快的，大样例 0.8s，造了几组也都是差不多这么快，那问题完全不大了

第二问大概也差不多，因为时间不太够就没写

期望得分 100+70+0 = 170

事实上 T3 好像有送了 20 分，但根本来不及看（

upd：好像没 FST，还挺好

Day 2

还是进考场开题，T1 一眼寿司晚宴，T2 一眼 WC，T3 一眼树上的数

然后分阶段 DP，复杂度 O(qm\cdot2^{14}) 或者 O(\sum c \cdot 4^{14})，用 or 卷积合并的话就能做到 O(\sum c \cdot 14\cdot 2^{14}) 的复杂度，但感觉不太行

然后过了几分钟就考虑容斥，对 m 做容斥，答案就是 \sum\limits_{i=0}^m(-1)^i\sum\limits_{|S|=i}f(S)，其中 f(S) 表示没有 S 中的质因子的方案数

然后配合寿司晚宴，2^{14} 枚举小质因子集合 S'，之后大质因子两两不交，所以只需要预处理出每个大质因子出去 S' 还有多少个数，最后用容斥背包实现就可以了（似乎是 PKUWC 猎人杀？）

然后稍微一算复杂度 O(2^{14}(m+\sum c))，感觉有点危险，发现第 14 个质数 43 刚好可以扔掉，就少了一倍常数，中间实现了 45 分钟，过了大样例挂拍了又调了一会，大概一个半小时解决了 T1

之后开 T2，这 TM 啥玩意，暴力都不会写，感觉这个性质还挺复杂的，就先扔了看 T3。T3 稍微理解了一下题意，然后写了个阶乘暴力，此时还剩两个小时，我决定做一下 T3（主要是不想做 T2）

很套路性地考虑一条边换完之后子树会怎么样，发现子树内外有影响的只有最后换进去了哪个、换出来了哪个，然后就 dp_{u,i,j} 表示 u 子树 a_i 换出去，a_j 换进来，写了四五种转移，大概就是讨论换出去的在哪里之类的，复杂度是 O(n^4) 的

然后过了小样例开始对拍，一组挂，调了一会发现是有左/右儿子是空的情况有问题，又讨论了一下只有一个儿子的情况，然后就过拍了。现在想来我真 TM nb，基本没怎么调就过拍了，测了一下 n=100 跑 0.1s，非常稳

然后咸鱼了 20min，还剩大概 40min，期间上了无数趟厕所

本来觉得还可以了，但 128 咋说都有点低，所以考虑了一下决定优化 T3。大概就是观察转移，然后一类一类优化，最后反正弄成 O(n^3) 的了，但要开 500\times 500\times 500 个 LL，直接 1GB，但这个空限 2GB，所以没问题了

之后就是检查文件啥的，期望得分 100+0+44

出来发现人均会 T2，但好像没啥人写 T3，反正就差不多那样吧

Day 4

测出来了，按照 BJ 的分应该就进队了，就是 NOIp 有点拉，不然应该还能往上翻一点。这次还有很多暴力没写，D2T2 甚至基本没看，但最后好在没挂分，最后也跌跌撞撞进队了

感觉挺奇妙就是了