2026.1 康复训练 • lomit

考完final，摸了十天鱼终于想起来要康复训练了，之前一直不知道从哪里开始，于是乎一直在摆烂。前两天突然发现明年WF可能在上海，有机会公费回国，突然来兴致了，冷静思考一下感觉还是得认真准备一下。我必须得考虑这是否是我此生仅有的机会了。

寒假选择不回国留在学校的初衷也是防止自己回国过于摆烂，还是有很多事情要做的。

做这个系列是因为感觉还是得记录一下，不管是科研还是icpc，在寒假这剩下21天的宝贵时间里不记录每天干了啥容易摆烂

顺便写写题解

12.29#

其实准确的来说是 12.29开始的，但是归进 26 年1月好了

今天一早起来vp了一场 ABC 418，边和高中同学聊天一边打，前面的题都还算容易，基本一眼秒。到了倒数第二题开始发现不会做，以为有什么神必性质没看出来，看题解发现原来是 DDP，然后最后一题是确定性有穷自动机，现在都卷到这种程度了吗？？

看了一下去年NAC的题，发现只要能稳定做出7个蓝题+切1/2题紫题就能进 WF了，去年还是太摆了。

ABC418E - Trapezium ↗#

现在暂时还没法补，先占个坑吧

ICPC NAC 2025 H. Ornaments on a Tree ↗#

不难发现，自底向上的贪心显然很对

对于当前的点 $u$ , 如果是 $-1$ ，只需让其等于 $\min(K - sum[fa], K - sum[u])$ 即可

然后更新一下 $sum[fa], sum[u]$ 接着做

code ↗

别的题看了一下，有想法，明天补吧

广义串并联图方法 ↗ 看了一下还没理解，明天研究一下

12.30#

上午看完了广义串并联图，就学了一下怎么做题。找了两题写了一下

然后去学校健身房练完，回来到处乱看了一些知识和blog

看高中生blog看得有点玉玉，忆往昔岁月了说是，浪费了巨量的时间

然后发现今年国家集训队好像都没法直接保送，还得笔试和面试，感觉非常逆天

SNOI2020 生成树 ↗#

广义串并联图就是不存在 $K_4$ 子图的图，对于这种图，可以用删一度点，缩二点，然后叠合重边的方式把大图缩成小图，然后维护答案

对于这题，显然给出的图是广义串并联图

于是在缩图的时候，可以考虑用 $dp$ 维护边 , $f[e], g[e]$ 表示对于这条边删或者不删的方案数

对于删一度点，直接让 $ans = ans \times f[e]$

对于二度点点两条边 $e_1, e_2$ 假设缩成的边为 $e^*$

$f[e^{*}] = f[e_1] * f[e_2]$

$g[e^{*}] = f[e_1] * g[e_2] + g[e_1] * f[e_2]$

对于叠合重边

$f[e^{*}] = f[e_1] * g[e_2] + g[e_1] * f[e_2]$

$g[e^{*}] = g[e_1] * g[e_2]$

可以直接拿个队列维护这玩意，代码还算好写 (不知道为啥题解区的好多代码码风很奇特)

code ↗

ICPC NAC 2025 G. Most Scenic Cycle ↗#

这题比上一题还简单，只用维护最长的路径

缩二度点的时候相加，然后叠合重边的时候计算答案并且维护最大值

code ↗

luogu P4839 P 哥的桶 ↗#

线性基康复训练题

不难发现这是一个单点修改，区间询问问题

首先搞个线段树，然后每个节点上用线性基维护即可

把两个线性基合并就是for其中一个，然后把里面的插进另一个线性基即可

code ↗

12.31#

跨年，国内高中同学熬夜和我打游戏，然后晚上我又熬夜和他们打游戏，有点上头

整理了一下房间

跨年还是休息一下吧

1.1#

摸

1.2#

重新开始写题，感觉没啥动力，摆摆的，只想躺着，游戏都不想打

不过写题感觉还是比research有意思一点，有点想逃避了

ABC133F Colorful Tree ↗#

一开始看想着树剖，但是发现不用，可以直接倍增LCA + 可持久化线段时

具体来说就是每个节点一个线段树，记录每个颜色出现的次数和距离和，简单算算即可

code ↗

ABC134F Permutation Oddness ↗#

不会做，贺！

发现原来是拆贡献dp，死去的记忆突然苏醒，对于绝对值，就把贡献拆成两个部分，大的是正的，小的是负的

然后主要是状态设计比较有意思，每次同时考虑值 $i$ 的位置和第 $i$ 个位置放什么

从小到大考虑

设 $f[i][j][k]$ 表示考虑到第 $i$ 个位置和值 $i$ , 有 $j$ 对小的值和位置没有被匹配，当前贡献为 $k$ 有几种情况

$p[i] = i$ , 即 $i$ 放在第 $i$ 个位置，那么 $f[i][j][k] += f[i - 1][j][k]$
$p[i]$ 和 $i$ 都和后面大的匹配，即作为负贡献的那一方，那么 $f[i][j][k] += f[i-1][j-1][k + 2*i]$
$p[i]$ 和 $i$ 匹配前面小的，即作为正贡献的那一方，那么 $f[i][j][k] += f[i-1][j+1][k - 2*i] * (j+1)^2$
$p[i]$ 和 $i$ 一个匹配前面小的，一个匹配后面大的，那么 $f[i][j][k] += f[i - 1][j][k] * j * 2$ 转移即可

code ↗

ABC135F Strings of Eternity ↗#

首先肯定是要把 $s$ 的长度补齐到至少 $t$

然后把对 $t$ 建 kmp，在 $s$ 上面跑出来一个匹配，然后把匹配上的连边跑最长链就好了

(然而kmp写挂，最长链dp方向写反调了一万年)

code ↗

效率还是有点低，总是去摸鱼干别的事情，但是也没有摸爽

1.3#

上午写了一题，不知道为啥又没啥动力了，下午在校园里随机游走，思考一些东西

1.4#

摆

1.5#

上午起来写了一题，然后去健身，不应该练腿的，练猛了，整个下午困得要死，sleep

晚上沉迷方舟剧情，有点上头bruh

ABC136F Enclosed Points ↗#

一开始没想到该咋办

但发现，其实可以拆贡献，考虑每个点的贡献

于是乎以每个点为坐标原点考虑，可以分为四个象限，然后容斥一下就可以的算出贡献了

以每个点为坐标原点分四个象限，就是简单点二维数点问题

code ↗

ABC137F Polynomial Construction ↗#

一眼拉格朗日插值，但是但是脑子有点不清醒

于是考虑类似的思想，拉插和中国剩余定理的想法都是构造 $n$ 个式子，每个柿子刚好满足其中一个点值，在别的点为 $0$ , 然后再把所有式子加起来.这题也可以考虑类似的构造

假设我们构造的式子要满足第 $i$ 个要求，即 $f(i) = a_i \ (\mod p)$ 然后仔别的地方为 $0$ ，不难想到可以用费马小定理来构造，即为 $1 - (x-i)^{p-1}$ 刚好可以满足

然后最后的多项式就是 $\sum\limits_{i=0}^{p-1} 1 - (x-i)^{p-1}$ 用二项式定理展开求系数即可

code ↗

ABC138F Coincidence ↗#

首先我记得有个性质是 $y \mod x <= y/2$

这个可以直接将 $x$ 分类讨论一下证明

然后对于这题

因为上面那个性质，所以 $x,y$ 的最高位一定相同，不然 xor 会比 mod 大

那么就可以知道 $y/2 <= x$

那么 $y \mod x = y - x$ 这题转换为 $y-x = x\ \text{XOR}\ y$

考虑每一位，直接上就是在二进制下 $y$ 应该包含 $x$ 即 $(x,y)$ 每一位只有 $(0,0), (0,1), (1,1)$ 三种可能

直接数位dp即可（别忘了前面最高位必须相同的条件）

设 $dp[pos][o][l][r]$ 表示当前从高到低考虑到第 $pos$ 位，是否已经确定最高位，是否卡着上下界

code ↗

ABC147F Sum Difference ↗#

遇到这种题还是要先把答案的式子表示出来

$\sum\limits_{i\in S} a_i - \sum\limits_{i\notin S} a_i$

然后发现可以写成 $2 * \sum\limits_{i\in S} a_i - \sum\limits_{i=1}^{n} a_i$ 然后发现要考虑的实际上只有 $\sum\limits_{i\in S} a_i$ 别的都是常数，不用管，只用看这个的个数

然后再带它的表达式，假设 $S$ 集合里选了 $t$ 个数，那么答案就是

$tX + kD$ 其中 $k$ 就是从 $0,1,2,...n-1$ 中选 $t$ 个求和的值，容易得到 $k$ 的范围就是

$k\in[\frac{t(t-1)}{2}, \frac{(n-1+n-t)t}{2}]$ 然后，按照 $tX \mod D$ 分类(记得后面的取值范围要加偏移量)，每一类里面就是一个线段求并问题（区间覆盖），随便做做

code ↗

1.6#

从12点睡到11点，早睡晚起这块

不应该练腿的，连着几天没精神，从训练清单上去掉，改成有氧吧

起床后得知WF在迪拜，好像没有机会回国了sad

ABC157F Yakiniku Optimization Problem ↗#

正确的做法是二分 $T$ 然后得到 $n$ 个圆，每个圆的半径是 $T/C_i$ , 然后两两圆的交点就是答案备选，大力枚举交点算即可

注意到需要把坐标随机旋转一个角度，确保不会出现没有斜率的情况

a[i].x = x * cos(theta) - y * sin(theta);
a[i].y = x * sin(theta) + y * cos(theta);

cpp

然后发现这题数据范围不大，可以尝试模拟退火，顺便复习一下

（结果发现自己之前写的退火一直都是错的，写反了）

具体来说就是，对于更优的答案，显然接受

对于不是更优的答案，算它与当前最优答案的差值，假设为 $\Delta > 0$

那么，我们可以以一个 $e^{-\Delta / T}$ 的概率去接受这个不那么优的答案

直观也很好理解，当 $\Delta$ 越小或者 $T$ 越大的时候，这个值会越接近 $1$ , 否则会越接近 $0$

然后我们就可以随机一个 $0<p<1$ , 当 $p<e^{-\Delta / T}$ 的时候就接受这个答案

随机一个 $p$ 满足 $p<e^{-\Delta / T}$ 的概率就是 $e^{-\Delta / T}$

就是

if(ret < ANS) ANS = ret, nowx = x, nowy = y;
else
	if((rand() * 1.0 / RAND_MAX) < exp(- (ret - ANS) * 1.0 / T))
		nowx = x, nowy = y;

cpp

代码懒得调参了

code ↗

ABC163F path pass i ↗#

第一眼淀粉质，但是发现好像没那么复杂

考虑求不经过某个颜色的点的方案数，不难发现拿掉这些点之后会变成若干联通块，然后每个联通块里随便选两个，加起来即可

然后对于每种颜色，应该可以在dfs的时候随便做做，具体还没想好，明天写

btw怎么效率这么低，好摆啊

1.7#

有点upset，放纵了一天，推完了白2 IC篇

这是真神作，丸户神了！

1.8#

唉，好乱啊最近，今天去学校健身房一堆警车

口胡了几题，没啥动力写题bruh，明早起来vp一场div 1吧

干research去了