2026.2 康复训练

最近在忙学校的事情，然后学习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拿来训练做题估计早就能回到巅峰，甚至突破不少了)