日记

为啥会背疼啊？

Final C# Link to

设 $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# Link to

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

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

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

最长 k 可重区间集# Link to

建边就这样建：先离散化，$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$ 的流量。

星际转移# Link to

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

后日谈 # Link to 后日谈

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