2026.1.1
新的一年。不对啊为什么我又失语了,一定是停课导致的罢。虽然 whk 学习并没有用掉整个 12 月,但是找了一堆理由拖到 1 月再写,机智如我。
现在看来过去的一年发生了好多事情,随便甩一个形容词都能荡漾一笔,甚至不需要是形容词——但毕竟飘风不终朝,也不便再谏过往。已经忘了过去这一年有没有许下什么愿望定下什么目标,正好也不用再纠结实现的问题。时间的破碎感愈发严重,现在我已很难完全静下心海。或许任由其波纹荡漾也是一种静,我不知道。
我思我在我的彼方
书写我关于我的真相
1.2
QOJ4218 Hidden Graph
就…就我不会 Brooks 定理和 Welsh–Powell 算法呗。
CF1630F Making It Bipartite
就…就 NOIP 前才看了偏序集宽度求法学了几周 whk 又忘了呗。
1.3
已被 ABC 严肃击杀。
复健之路道阻且长,其实还有一种可能是原本就只有这个绿题做不起的水平(?)。
ABC436E Minimum Swap
大脑响应时间小于 NOIP T1,已经赢了。
这是经典问题,但是大脑没开机。过了几分钟想起来最小交换次数为 \(n-\) 置换环个数,方案数等于各置换环内部完全图生成树个数之积。然后推广一下就做完了。
ABC436F Starry Landscape Photo
看错了两遍题,建议先回去把英语提升至 145。大脑响应时间约等于 NOIP T1,输麻了。
看懂题之后相当简单啊,一个方案对应到极小的 \([l,r]\) 和 \(b\) 就做完了。
ABC436G Linear Inequation
欸是原题不会做环节。记 \(V=\sum A\)。
-
\(M\) 贼大,\(V\) 贼小。从低到高二进制按位考虑每个物品选的个数,就可以做容量为 \(V\) 的 01 背包,做到 \(O(NV\log M)\)。
-
如果不会上面的做法怎么办呢,观察到这个东西的 OGF 是类似付公主的背包状物,但是 \(M\) 很大没法直接卷,只好严肃学习 Bostan-Mori。核心思想是对于 \(\dfrac{P(x)}{Q(x)}\) 上下同乘 \(Q(-x)\) 消去分子奇次项然后分讨 \(m\) 的奇偶性递归。相信自己要用的时候一定会推罢。
AGC038F Two Permutations
最小割模型上边 \((u,v,w)\) 的意义:若 \(u\in S, v\in T\),则有 \(w\) 的代价。