2025 长训第三周 (1008 to 1013)

突然发现写长篇题解似乎是不必要的，以后只写关键观察，思考过程，以及一些自己原本不理解的部分。

有后效性的几种处理

整体转移

画转移图 --> 观察性质

TRICK

把 DP 状态看成高维空间中的点集。

考察其：轮廓凸性，…，

Slope Trick？数据结构维护分段函数？

根据计数答案的增长率，对其进行插值

凸相关

二分斜率 WQS 二分

四边形不等式 --> 二维差分非负

对于一个函数，它是凸函数，当且仅当： $\frac{f (x + s) + f (x - s)}{2} \geq f (x)$ 。

1009【模拟赛 #7】

没有分析自己代码的复杂度，看来对于一些不太显然的东西还是分析一下为好。

写出暴力 dp 后利用均值不等式证明其复杂度正确。

写完两题摆了，发现 T4 暴力挂分导致直降 6 个 rk。

写这里的主要作用是记录一下原题

赛时想起来一个思路：把三个字符串拼起来然后直接由两端往里面匹配。

感觉比较魔怔，细节比较多不太可做。

这实际上是【转移时的分类讨论】，而题解中的做法本质上相当于把分类讨论环节提前了。所以如果后期分讨太麻烦可以提到前期。

大概就是考虑选出来三个字符串中（长度为 $x, y, z$ ）， $x = z$ 以及 $x < z$ 的情况。每种都可以直接写一个类似 dp 的东西，扫指针进行匹配。

T1 糖糖构造磨掉我太久时间了。

对模 3 分讨然后大力做。赛时浪费了太多时间在推模 4 的推导了，本来中间试图拼一个模 3 然后当时以为模 3 之中也有一种情况不可做。

考虑把“不可能到达”者也标记一下，然后最后一个柱子不能被绕过当且仅当它贴墙。然后就可以做了，容易发现答案为不贴墙的联通块数量加一。

考虑用一张图刻画不可达关系，发现这张图强于竞赛图，于是有一些竞赛图上的结论：

所以我们对这个新图的结构 dp，显然是一条链，上面有一些大小为 1 或者 2 的 SCC。

设 $d p_{i, j}$ 为当前放了 $i$ 个点，最后一个 SCC 有 $j \in [1, 2]$ 个点的方案数。转移是容易的。

agc068_a