给出长度为 $n$ 的, 仅由 a, b, c 组成的字符串. 问长度最小的满足条件的子串, 条件为: 长度至大于等于 $2$ a 在字串中的出现次数严格大于 b 的出现次数 a 在字串

从 $2n$ 个点的无向完全图中, 删除给定的 $2n - 1$ 条边, 且这些边是一棵树. 问剩下的图的完美匹配数是多少. $1 \le n \le 2000$ 正难则反, 考虑求 “至少包

长度为 $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$ 个中, 选的最后一个为

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