日记

补豪，我的手感！

事情起因是这样的：唐诗视频看多了，不仅 OI 没手感，CS 也没手感了。

随机说话# Link to

我们经过打表发现，最终的答案和顺序一点关系都没有。

最小生成树# Link to

其实黑题都已经见怪不怪了。

首先有结论：在只考虑 $a$ 边的情况下把图分成几个联通块，那么最小生成树一定不会走出这个连通块再走进来，因为这样至少需要 $2b$，而在内部连只需要 $a$。所以我们把图分成几个连通块，设 $dp_{s,u}$ 表示经过的连通块集合为 $s$，$1 \to u$ 的最小距离。可以用 dijkstra 转移,复杂度 $O(2^n mn)$，显然不咋过得了。

我们发现对于大小 $\lt 4$ 的连通块，走外面一定没有走里面更优，于是我们只用考虑大小 $\ge 4$ 的连通块，数量就只有 $O(\lfloor \frac{n}{4} \rfloor)$ 个。复杂度降到 $O(2^\frac{n}{4}mn)$。

游戏# Link to

我们发现，有数集 $S$ 使得当且仅当 $S$ 里的数必须全部选完，所有员工都认真工作。这个 $S$ 可以 $O(n \log \log n)$ 预处理。然后设 $f_i$ 表示在前 $i$ 次里面取走 $S$ 里的所有数的方案数。有 $f_i = (i - 1)! \times |S| \times \binom{n - |S|}{n - i} \times (n - i)!$，分别表示前 $i - 1$ 个数随便排，第 $i$ 个数有 $|S|$ 种选法，剩下的 $n - i$ 个数塞到 $n - |S|$ 个位置里，$n - i$ 个数随便排。

后日谈 # Link to 后日谈

感觉 NOIp 不考高一点对不起这个只放一周的暑假。

翻看了 3 月的日记，发现 CF rating 涨了 $200$。