2021-11-8-Test

实际：100 + 70 + 0 + 0
能做：100 + 100 + 0 + 0

这场的 T1 比较简单但花了 2h 才写出来，导致浪费了很多时间

# Solutions:

# a

考虑两个点之间的连边只有出现奇数次的才会再最后被算到

于是使用 ll 模拟 bitset 即可。

# b

这种题为啥我会开始认为没有单调性呢？

于是二分一个答案 $x$ ，现在要求每个段平均值大于等于 $x$

要能分到 $k$ 块，于是我们使用一个 $dp$ 求最多能分几块。

于是我们就得到一个 $\mathrm O(n^2 \log a)$ 的做法

考虑优化，就是一个线性规划一样的东西，于是用 BIT 简单维护即可。

# c

神仙题，感觉有铲雪那味。

大概是，你在每条树边上放两条边，于是把原问题映射为在两条树边在每个点上做匹配的新问题。

考虑这个新问题，这两条边在匹配过程中有区别的，所以我们会算重，一个原问题中构造管道的方案对应着 $2^{n-c-1}$ 种方案，因为你可以先任意构造一种然后交换每对边的匹配，而相同管道的时候你交换就算重了，所以你要减去相同管道 $c$ 的方案，于是你发现就是题目那个奇怪的 $2^{-c}$ 权值，那对于新问题求解后除以 $2^n$ 就好了。

对于新问题，每个点是独立的，于是分别处理。对于每个点，可以看做 $n$ 个颜色的球，每个颜色有两个球，取两个不同颜色球匹配的方案数。设 $dp_{i,0/1/2}$ 表示已经取了 $i$ 对，还有 $0/1/2$ 个空余球，然后凭直觉 $dp$ 即可。

# d

鸽