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

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


# Solutions:

# a

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

于是使用 ll 模拟 bitset 即可。

# b

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

于是二分一个答案 xx ,现在要求每个段平均值大于等于 xx

要能分到 kk 块,于是我们使用一个 dpdp 求最多能分几块。

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

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

# c

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

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

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

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

# d

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝