从 $2n$ 个点的无向完全图中, 删除给定的 $2n - 1$ 条边, 且这些边是一棵树. 问剩下的图的完美匹配数是多少.

$1 \le n \le 2000$

正难则反, 考虑求 “至少包含一条树边的完美匹配数”, 然后用完全图的完美匹配数相减.

无法直接数出 “至少包含一条树边的完美匹配数”, 所以这里考虑容斥. 如果能够求出包含树边 A 的完美匹配数, 包含树边 B 的完美匹配数, 包含树边 C 的完美匹配数… 包含树边 A 和 B 的完美匹配数, 包含树边 B 和 C 的完美匹配数, 包含树边 C 和 A 的完美匹配数… 包含树边 A, B, C 的完美匹配数… 这样就可以用容斥求出包含 A 或 B 或 C… 的完美匹配数, 即至少包含一条树边的完美匹配数了.

这样的话会有一个问题, 每条树边都得枚举, 复杂度会炸. 可以发现, 恰好包含一条树边, 无论是哪一条, 完美匹配数都是一样的. 进一步, 如果是恰好包含两条树边, 那么剩下来的点是可以随便连的, 而剩下来的点个数又是一样的, 所以, 无论选哪两条树边, 完美匹配数都是一样的. 那么我只要知道选择两条树边的方案有多少种, 然后乘以剩下来的点的匹配方案数, 就可以了. 推而广之, 现在的任务就是计算 “恰好选择k条树边的方案”.

期中考前打星, 勇!

24h 极限编程 x
24h 极限摸鱼 ✔

长度为 $n$ 的序列 $f_n$, 从中选出若干个数, 不改变其相对顺序, 使得 $\sum\limits_{j=1}^{k-1} f_{i_j}\&f_{i_{j+1}}$ 最大. $2 \ne n \le 10^6, 0 \le f_i \le 10^{12}$.

首先很容易想到一个 $O(n^2)$ 的 dp: 设 $dp(i)$ 为前 $i$ 个中, 选的最后一个为 $i$, 能得到的最大值. 方程为 $dp(i) = \max\limits_{1 \le j < i} \{dp(j) + (f_i \& f_j)\}$. 但很显然 $O(n^2)$ 是过不了的. 并且这范围好像用个数据结构维护起来都可能 T. 这里有个位运算. 所以一个方向是按位考虑.

我们看这个方程实际上是在干什么, 他就是一个很简单的枚举. 然后我们看一般的动态规划优化是在干什么, 他是将一些一定不是可能的最优解排除掉, 不去枚举他, 而是枚举一定可能是最优解的决策点. 那么我们需要做的就是从这个方向去考虑. 结合位运算, 那么一个方向就是, 考虑每一个位, 能不能排除一些一定不是最优的解.

由于 $f_i$ 对 $dp(i)$ 多出来的贡献是每一位是 $1$ 的个数, 那么我们可以枚举第几位, 考虑"这一位是1"的所有决策. 把这些决策单独拎出来, 一定会从离 $i$ 最近的点 $k$ ($k < i$) 转移过来, 否则假设从 $l$ ($l < k$) 转移过来, 那么如果把 $k$ 加进去, 答案会更优, 因为这一位的贡献是一样的, 但是由于 dp 值是递增的, 所以从 $k$ 转移会更好. 然后考虑"这一位是0"的所有决策, 也是同理. 那么我们把每一位都这样考虑掉, 实际上就是减少了很多不必要的枚举量, 从而使复杂度降下来.

$n$ 个点, 点权为 $a_i$. 两点之间有 $\frac{a_i}{a_i + a_j}$ 的概率从点 $i$ 向点 $j$ 连一条有向边(否则即有 $\frac{a_j}{a_i + a_j}$ 的概率 $j \to i$). 即根据概率建一个竞赛图. 求能到达其他所有点的点的期望个数.

$1 \le n \le 14, 1 \le a_i \le 10^6$

点数很少, 所以尝试点集为 $S$, 事件 $f(S)$ 表示有且仅有 $S$ 中的点能到达所有点, 直接根据期望的定义去计算答案, 应该为 $\sum |S|P(f(S))$.

现在考虑 $f(S)$ 如何计算. 首先我们可以发现 $S$ 一定是一个强连通分量, 且有 $\forall x \in S, \forall y \in \overline S, x \to y$ (之后用 $S \to \overline S$ 表示). 简单考虑一下后面这个条件的必要性: 若 $\exists (y \in \overline S, x \in S), y \to x$, 若 $S$ 中有其他点, 则要么 $\exists z \in S, z \ne x, z \to y$, 这种情况 $y$ 能和 $S$ 一起组成 SCC, 与 $f(S)$ 的定义矛盾; 若 $S = \{x\}$, 反过来考虑, 也会有 $x$ 可能与 $y$ 的 SCC 组成 SCC. 与 $f(S)/f(\{x\})$ 矛盾, 若不然, 则仅有 $f(\{y\})$, 与 $f(\{x\})/f(\{x\})$ 矛盾.

2021 年 10 月 18 日晚, 我正在学 CTF, 当我对知识点有一点模糊的时候, 我去翻我博客记录, 结果…

几个月前了解了这部片子, 有幸在国庆观赏. 总的来说是一部不错的青春励志片.