「Log」2023.10.17 小记

CSP 第二轮倒数 \(3\) 天。

序幕

\(\text{6:40}\)：到校，整理博客。

\(\text{7:30}\)：模拟赛发题。

题意都很简单，感觉都是很怪异的配置，T1 性质是显著的，一会就切了。

T3 感觉不知道想考啥，反手扔个乱搞。

T2 T4 是一点思路没有，T4 连暴力都不会，应该涉及到切比雪夫距离性质啥的。

被创死了。

T2 有点像点分治，但肯定不是点分治。

\(100 + 0 + 0 + 0 = 100\)，被创死了。

中午吃和府捞面感觉良好，下完棋准备写题。

\(\color{blueviolet}{P4768}\)

预处理到 \(1\) 的距离，然后 Kruskal 重构树简单倍增维护一下即可。

\(\color{blueviolet}{P4322}\)

式子是显著的，考虑分数规划，二分后树 DP 也是显著的。

\(\color{blueviolet}{P6087}\)

显著的分数规划，需要注意的是可能出现区间长度小于 \(L\) 的解，所以要扩展至 \(L\) 进行特殊处理。

单调队列边界寄了，调了好一会。

\(\color{blueviolet}{P2473}\)

状态是显著的，但正着转移并不可以，因为状态分布不均匀，没法直接算方案数，所以倒着转移。

感觉是典型的题，有点神仙（大概吧）。概率正着推，期望逆着推。（题解里的话。）

\(\color{blueviolet}{P4197}\)

思路是显著的，Kruskal 重构树后上主席树查询（按照 DFS 序建即可）。

不知道为啥倍增维护祖先挂掉了，明天再看看，刚开始还以为会有图不连通的情况。

尾声

咕噜咕噜睡大觉。