实际:100 + 70 + 0 + 0
能做:100 + 100 + 0 + 0
这场的 T1 比较简单但花了 2h 才写出来,导致浪费了很多时间
# Solutions:
# a
考虑两个点之间的连边只有出现奇数次的才会再最后被算到
于是使用 ll
模拟 bitset
即可。
# b
这种题为啥我会开始认为没有单调性呢?
于是二分一个答案 ,现在要求每个段平均值大于等于
要能分到 块,于是我们使用一个 求最多能分几块。
于是我们就得到一个 的做法
考虑优化,就是一个线性规划一样的东西,于是用 BIT 简单维护即可。
# c
神仙题,感觉有铲雪那味。
大概是,你在每条树边上放两条边,于是把原问题映射为在两条树边在每个点上做匹配的新问题。
考虑这个新问题,这两条边在匹配过程中有区别的,所以我们会算重,一个原问题中构造管道的方案对应着 种方案,因为你可以先任意构造一种然后交换每对边的匹配,而相同管道的时候你交换就算重了,所以你要减去相同管道 的方案,于是你发现就是题目那个奇怪的 权值,那对于新问题求解后除以 就好了。
对于新问题,每个点是独立的,于是分别处理。对于每个点,可以看做 个颜色的球,每个颜色有两个球,取两个不同颜色球匹配的方案数。设 表示已经取了 对,还有 个空余球,然后凭直觉 即可。
# d
鸽