日记 - 伊埃斯的博客站

为啥会背疼啊？

Final C↗

设 $dp_{i,j}$ 表示已经选了 $i$ 根弦，第 $i$ 根弦在二进制下又 $j$ 位是 $1$ 的方案数。初始化 $dp_{0,0} = 0$ ，转移就是 $dp_{i,j} = \sum\limits_{k = 0}^{32 - j}dp_{i - 1,k} \times \binom{32 - k}{j}$ 。最终答案就是 $\sum\limits_{i = 1}^{n}\sum\limits_{j = 0}^{32}dp_{i,j}$ 。

就是没想到最终答案。

Alex Combines↗

我们发现对于每个区间，左端点也不是定的，右端点也不是定的。这十分的麻烦。考虑固定一个左端点或者右端点来考虑。

设 $f_i$ 表示 $[i,f_i)$ 这段区间是合法的。显然这玩意可以 $O(n)$ 预处理。查询的时候暴力一点：如果 $f_l \le r$ ， $l$ 就跳到 $f_l$ ， $ans$ 加 $1$ 。注意 $ans$ 初始为 $1$ 。

看到这一就应该自然而然的想到倍增了。

最长 k 可重区间集↗

建边就这样建：先离散化， $i - 1 \to i$ 建一条容量 $k$ ，费用 $0$ 的边，对于每个区间， $l \to r$ 建一条容量 $1$ ，费用 $r - l + 1$ 的边， $s \to 1$ 建一条边，容量 $k$ ，费用 $0$ ， $n \to t$ 建一条容量 $k$ ，费用 $0$ 的边，跑最大流就是了。

如何理解？我们发现如果有 $x$ 条边重合了，那么一定需要至少 $x$ 的流量。

星际转移↗

枚举时间，在时间和下一站之间建边。

后日谈

今天还没消掉 $24^\circ$ 空调给的 debuff。。。

Thanks for reading!

日记

周五 5月 23 2025

371 字 · 2 分钟

life 日记