2026.2~3 康复训练

最近在忙学校的事情，然后学习RL，数学公式看得好爽，比non-linear optimization好理解多了

怎么下个月就要去比赛了，除去准备midterm的时间，好像真不到一个月了

可能大概率要提早毕业啦，这貌似是本科最后一次机会进WF了，哭了

感觉自己的执行力还是不够，老是行动跟不上计划

2.6#

看了下ICPC NAC-O 的训练，感觉好像没啥太大用，还是得自己搞比较好

2.10#

效率有点太低了，被课内的没用的东西消耗精力，浪费的时间有点多，得做出取舍啦，时间就那么多，机会转瞬即逝，什么才是真正重要的，需要花时间的，我心里应该是清楚的。

看了看EC final的题，发现自己状态比较好的情况下好像也没法出线，感觉不是很妙

还有一个月的时间准备，得加训了

2.11#

小小的玉玉

重新看了一些之前的题，然后按着oi-wiki上的知识速通啦一下dp之前的，dp复习了一下ddp，dp of dp打算明天再看

然后鼓起勇气看了看当年退役的省赛题题解，确实感觉很可惜，空悲切！

总的来说还是看了不少东西的，明天开始写代码吧，不能光看

2.12#

重新开始写题，看高中生的blog看的有点上头。

老灯怀念过去了属于是，只用打竞赛的日子是真的爽，没好好珍惜啊。早知道家里能兜底也不至于高中压力太大导致发挥失常了。可惜青春只有一次，现在脑子已经完全转不动了。

P10614 BZOJ3864 Hero meet devil#

problem link ↗

dp of dp 板子题

首先对于经典的LCS问题，有个很显然的 $dp$ , 设$g[i][j]$ 表示 $T$ 的前 $i$ 位和 $S$ 的前 $j$ 位， LCS 的长度

这个是很显然的，然后dp 套 dp就是把 $j$ 这一维度的状态记下来，假设为 $S$ , $f[i][S]$ 表示考虑前$i$位$g[i][...]$的状态为 $S$ 的方案数。

发现状态数会非常大，有$15^{15}$, 考虑压缩状态

不难发现，固定$i$, $g[i][j]$ 肯定是递增的，并且相邻的增量最多为 $1$, 于是考虑直接记录差分数组，把差分数组当作状态，这样状态数就变成了 $2^{15}$ 一下子就可做了

具体转移就是对于每个$f[i][S]$, 考虑下一位填什么，然后看填了之后$S$ 会转移到什么状态，假设为 $T$, 直接 $f[i][T] += f[i][S]$ 即可

可以结合代码理解

code ↗

P4590 TJOI2018 游园会#

problem link ↗

内层的dp转移一样的，外层的多加一维就好了

代码差不多

P4072 SDOI2016 征途#

problem link ↗

xjb 推一下式子，把贡献拆开发现还是要分成 $m$ 段，然后每一段段平方求和最小

刚好复习斜率优化，推一下式子发现是

$f_{i,k} - s_i^2 = f_{j,k-1} + s_j^2 - 2 * s_i * s_j$

然后尝试写成斜率的形式 $b=y-kx$

变成了我么想要截距$b$ 最小

$y : f_{j,k-1}+s_j^2$

$k : 2*s_i$

$x : s_j$

维护一个下凸包即可，因为斜率 $k$ 是单调递增的，所以直接拿个队列转移就好了

code ↗

明天开始得每天至少写/口胡 10题了，不然真的来不及了。

2.13#

今天状态不是很好啊，昨晚睡的有点晚，早上又被舍友吵得睡不好

P3515 POI 2011 Lightning Conductor#

problem link ↗

有个非常显然的 $n^2$ dp, 然后不难发现转移的时候这个贡献函数$w(i, j)$ 写出来是满足四边形不等式的，满足单调性，直接分治优化转移即可

code ↗

CF750E New Year and Old Subsequence#

problem link ↗

又是ddp，这篇题解挺清晰的

https://www.luogu.com.cn/article/qf66h2g0 ↗

然后口胡还有盒了几题的题解，脑子有些昏昏的，懒得折腾了，明天和队友一起训练看看结果如何吧

2.14#

情人节和队友激情icpc训练五六个小时

vp了之前的nac，好像能进WF，题解之后再补，sleep

2.15#

除夕前，白天和朋友出去吃饭逛中超

干完饭回来晚上尝试学习，发现不太能学进去

复习 slope trick 和 aliens trick 感觉脑子有点不是很清醒，于是乎去看数据结构，更加不清醒了

不是很妙，可能是欠的ddl太多了，没法集中精力，还是先把欠的一堆HW补了吧

只剩一个月了，哭了

2.18#

过年给自己放几天假了说是

其实是被各种课的ddl折磨，有点烦，感觉自己的精力和时间管理有大问题

今天拿到了夜魔X（然鹅并没有时间打游戏，忙死了），终于联系上了 advisor，貌似一切向好了终于

提早毕业貌似出了点问题，可能之后得和家里沟通一下了，还是得多圈米，（其实多打一年icpc也没啥不好）

昨天学习了一个新的科技：简易版 LARSCH 算法 ↗

感觉非常妙妙，写了这个算法的经典题

P9266 PA 2022 Nawiasowe podziały#

problem link ↗

正常做法感觉会非常麻烦，需要 wqs二分 + cdq + 整体二分，非常炸裂

主要的问题就是这个 $w(i, j)$ 的计算，是不好直接算的，也不好离线算，所以相当于是强制在线了

然后就可以直接套用上面的算法做就好了，代码非常简单，这个算法有点妙妙

code ↗

刚好同时复习一下四边形不等式，决策单调优化和wqs二分

开学后好多乱七八糟的事啊，感觉还是得仔细管理一下自己的时间和精力，总感觉浪费了很多精力在没用的事情上面

马上要比赛了怎么还啥都不会，大学这几年浪费太多时间了 (感觉把打cs2的1000+h拿来训练做题估计早就能回到巅峰，甚至突破不少了)

2.19#

今天复习了一下字符串

把SAM之前的都重新看了一遍，发现自己以前写的代码有点抽象，为了省一两个数组把逻辑弄的有点不清醒

重新手写了一下SA，推了一下height，感觉不赖

明天开始干 SAM和PAM这些科技，然后后天继续模拟赛

感觉进度还是有些慢，每天就只能抽出两三个小时准备，乱七八糟的事情有点多

自己的精力也有点不足，感觉一天高效学习的时间非常非常少

重新开始做有氧运动了，希望可以提升精力

2.20#

上午sleep

下午在gym 嘴巴了几个题，写了下题解

复习了一下分块科技，树分块，明天写写题

有点摆

2.25#

摸了几天，各种project，quiz，paper有点烦

eva真好看，三刷发现自己以前还是很多地方没看懂

上一次看还是五年前

重新复习了一下各种莫队，线段树操作，李超树啥的，嘴巴了几题，写了下题解，还没写代码，明天写

2.26#

不能再打cs了，有点上头，又熬夜了

cs2卸载

重新嘴巴了一下李超树，然后看了一下猫树，还有2-sat，有点困

下周三场midterm，好折磨，好多事，大学有点太摆了，啥也没干，啥也没学

核心优势和竞争力也没培养出来

3.5#

忙了几天准备midterm还有赶各种ddl，终于能all in acm了，春假+周末连续的空闲时间，还是得好好珍惜

3.7#

昨天吧2022 省赛的D1 T2写了，今天吧D2T1写了，也算是直面过去了

明天vp noi2022？ 随便看两眼吧，还是准备acm比较重要

这几天勾起了不少的回忆啊

3.8#

本来今早想打cf，结果舍友昨晚凌晨打游戏大声吼叫，没睡好，咕了

补一下题解吧

P8290 [省选联考 2022] 填树#

link ↗

这题当时考场上其实是想出来正解了的，但是时间复杂度没算清楚，有些遗憾

首先暴力不难，钦定一个最小值，然后得到一个区间，随便dp + 容斥一下就能做到 $O(nL)$, 可以拿到40分。 然后不难发现，在枚举最小值计算的时候，对于一段，就是若干个东西乘起来，于是乎大胆猜想答案是个多项式，直接用拉格朗日插值加速计算即可。 具体来说，对于$[L, L+K]$ ， 当左右端点都没有碰到某个点的限制的时候，这个东西的答案是多项式， 我们要求前缀和，前缀和相当于多乘了一个多项式，次数高一点，对复杂度影响不大，直接插值就好了。 对于每一个连续的没有碰到限制的段，计算 $T$ 个点的点值出来，然后插值得到这段结尾的答案即可。 我取了 $T = n+5$, 最后的时间复杂度就是 $O(n^3)$

然而考场上犯傻了，把求点值的复杂度和插值的复杂度乘起来了， 以为是$O(n^5)$的，实际上求点值和插值是分开的，应该是$O(n^3)$

code ↗

P8292 [省选联考 2022] 卡牌#

link ↗

也是考场一眼秒的套路题，可惜当时心态已经炸了bruh

对于 $s_i <= 30$ 的，不难想到可以直接容斥， $2^T$, $T$ 是质数的个数

然后能想到类似寿司晚宴的套路，把质数按照根号分为大小两类

对于大的质数，不难发现他们在容斥的时候是相对独立的，不会出现需要拿两个大质数容斥的情况

于是乎对于小质数，可以直接$2^T$ 容斥，然后对于大的质数，直接钦定它必须至少有一个

小质数直接容斥即可，具体来说就是用总的减去钦定不出现 $S$ 这个集合里的小质数的方案， 减去$cnt(S) = 1$ 的， 加上$cnt(S) = 2$ 的这样容斥，然后还得保证大的质数都被钦定至少有一个

可以搞一个数组 $g[S][p]$ 表示不出现 $S$ 这个小质数集合里的，但是是 $p$ 的倍数的数有多少个，考虑大质数的时候就是乘上 $2^{g[S][p]-1}$， 然后减去设计到的个数，最后剩下的随便选这样容斥

具体可以看代码（感觉自己中文水平退步好多，不会讲话了）

code ↗

P7967 [COCI 2021/2022 #2] Magneti#

link ↗

我高中学的时候好像这种题叫拆贡献dp还是贡献延迟计算来着？

现在好像叫连续段 dp

首先还是先从小到大排序，大的满足一定会保证小的也满足

于是设 $f[i][j][k]$ 表示考虑了前 $i$ 个，一共变成 $j$ 段，占用了 $k$ 个格子

转移就比较简单，直接考虑新开一组，加到之前某组的两端，或者把两组合并三种情况

最后枚举 $f[n][1][k]$ 用插板法计算一下答案求和即可

code ↗

3.9#

昨天晚上和朋友出去玩，吃饭，今天起得比较晚

vp了一场arc，感觉水平还是不够，还是得多做题，但是貌似时间已经不多了

晚上面试还算顺利，面完立马让我明天加面，有点想摆烂了，不是很想面了

3.12#

前两天面试弄的有些没法专心准备比赛，技术面很快就过了

时间不多了，得all in了

感觉每题都写题解来不及了，可能得速通了，几分钟想不出就看题解

感觉大部分知识套路都是忘了，直接看题解可能效率会高点

3.22#

进 WF 了，爽的有点大