2026.10.28 衡中集训

杂项（或许都可以归到DS

P12698 [KOI 2022 Round 2] 树与查询

好题。

有了边集后 DSU 维护并查集大小并统计答案是显然的。考虑如何从点集到边集。从点集中的点向父亲连边（如果父亲也在点集中）。很好理解这样复杂度是对的。

P14870 [ICPC 2020 Yokohama R] To be Connected, or not to be, that is the Question

一个点：可行的判断是 L + R - 1 <= min(cnt,n-cnt)。L 和 R 是左右连通块数量，cnt 是其中一边点的个数。

顺序维护并查集大小显然是容易的。

P6510 奶牛排队

容易推出式子。将限制分开来看：最右最高，用单调栈可以维护出可以转移的左边界。然而这个左边界并不准确。左端点要同时也是区间最小的。

再用一个单调栈维护小值。然后在这个单调栈上二分找到最左转移点。两个条件都得到满足。

P2216 [HAOI2007] 理想的正方形

这题应该拖了有很久了。今天解决掉了。

用两遍单调队列维护窗口的 max/min，问题在于写起来很不优雅。

DP 优化

写起来并不爽。

P10976 统计重复个数

基础的暴力 DP 都完全没有设计的思路……

dp_i,j 为从 s1 的第 i 位开始，找 j 次 s2 的最小代价。dp_i,j = dp_i,j-1 + dp_{(i+dp_i,j-1)%s1.length},j-1

之后的倍增优化反而是更好想的，把 j 给搞成二进制位就行了。

P2569 [SCOI2010] 股票交易

很容易想到 dp_i,j 表示第 i 天，有 j 股的最大收益。三个转移：不买，w 天前买，w 天前卖都好推。

如果用 st 表实现的话，我觉得这题还是挺容易的。但是它卡 st 表，只能用单调队列。

P10977 Cut the Sequence

一开始看这个题很有贪心的欲望，但是贪心是不对的。

DP 很容易写出平方的式子，这时有一个窗口的转移，启发使用滑动窗口。问题在于滑动窗口的边界并不一定是最优的。使用堆来去取答案，在维护滑动窗口的同时维护这个堆。

AtCoder DP/typical

Knapsack 1 AtCoder - dp_d

01 背包板子

Knapsack 2 AtCoder - dp_e

一般的背包是容量小权值大，这个是容量大权值小。那就把权值放到状态里。

其实这个也是一个比较典的思路，DP 状态里要放比较小的维或者是好转移的维。

LCS AtCoder - dp_f

LCS 板子。记录路径用 pre 表示上一个转移而来的状态即可。

Longest Path AtCoder - dp_g

DAGDP 板子题。

Cross Sum（★2） AtCoder - typical90_d

维护每行每列 sum。

Yokan Party（★4） AtCoder - typical90_a

最小值最大，考虑二分答案。这个时候要在满足条件的同时可分的块数尽可能多，以满足需求。小贪心即可。

谈

或许在去 CSP 的路上可以口胡一下 AtCoder typical/ 专题场的题。