C-Candles

普及组题，不说了
代码

D-Median of Medians

题意

定义序列 $a_1,a_2,\cdots ,a_n$ 的中位数为排序后从小到大第 $\lfloor \frac{n}{2}\rfloor+1$ 个数。 给定长度为 $N$ 的序列 ${a}$，对于每一对 $1 \leq l \leq r \leq N$ 的 $[l, r]$，把 $a_l,a_{l+1},\cdots ,a_r$ 的中位数丢进 ${b}$ 中。
求 ${b}$ 的中位数。
$ 1\le N\leq 10^5，1\leq a_i \leq 10^9$。

题解

首先我们显然去二分中位数，然后就是判断 ${b}$ 中有多少个数大于等于中位数就可以去调整下一次二分的位置了。
考虑我们这次二分的中位数为 $k$ 令 $\geq k$ 的数变成 $1$，$\leq k$ 的数变成 $0$。如果一个子区间的和是 $\geq 0$ 的，那么说明这个子区间的中位数一定是 $\geq k$ 的。我们相当于只需要数区间和 $>0$ 的个数。直接用树状数组维护就可以了。
代码

E - Ribbons on Tree

题意

给定 $N$ 个点的树。称一个“把所有点两个分为一组，一个点只在至多一组且分成恰好 $\frac{n}{2}$ 组的方案”是好的，当且仅当:如果我们把每组两个点的最短路上的边都打上标记，最后每条边都被标记了。 求好的分组方案数。答案对 $10^9 + 7$ 取模。
$2 \leq N \leq 5000$，$N$ 是偶数。

题解

发现自己只会容斥但不会转 dp
首先我们可以将“每一条边都覆盖”的限制转为有些边不被覆盖来进行容斥，容斥系数就是 $(-1)^{|E|}$。然后我们考虑如何求某些边不被覆盖的方案：我们考虑将这些边删掉，就是 $n$ 个点随意匹配的方案数了，设这个方案数为 $g$，显然有 $g[i] = g[i-2]* (i-1)$（注意奇数的时候没方案）。
然后题解说是要 dp（？我们可以用 dp 快速的求出所有的方案并累加起来，因为在容斥的过程中对于某些子树其实它是有很多重复的状态的。于是我们设 $f_{v,i}$ 表示已经将 $v$ 的子树的配对结果处理完了，有 $i$ 个子节点是要在根的上面匹配的。我们考虑每个边分给深度较深的端点，那么 $f_{v,0}$ 显然就是 $|E|=1$ 的情况，也就可以得
$$f_{v,0} = -\sum_{i} f_{v,i} g_i$$
然后对于其他的状态，我们考虑用背包的方法转移，这样第二维的 $i$ 和 $j$ 会贡献给 $i+j$，容斥系数也是直接相乘了。（好妙啊一点都想不到）
代码随便写写就好了。
代码

F - Robots and Exits

题目描述

在数轴上有 $N$ 个机器人和 $M$ 个洞，他们的位置两两不同。 你每秒可以让所有机器人集体向左或者向右一格，如果机器人走到洞上面就会掉下去。
问有多少种机器人掉洞方案，答案对 $10^9 + 7$ 取模。 两个方案不同，当且仅当存在机器人在两个方案中掉的洞不一样。
$1 \leq N,M \leq 10^5$。

题解

还是我不会的题，我太菜了
我们先去掉只会掉入一个洞的机器人，然后考虑剩下的机器人它都可以向左右两个洞去掉。我们将这个机器人的初始位置距离左右两个洞的距离分别记做 $a_i$ 和 $b_i$。
然后就开始一些我想不出来的神奇变换了。。。
首先我们将 $(a_i,b_i)$ 放在平面上，考虑一次向左操作就 $(x,y)\to(x+1,y)$ ，向右就 $(x,y)\to(x,y+1)$。然后我们发现对于一条路径，在它下面的点一定是右边的洞，上面的一定是左边的洞，我们实际上是对这种可能的划分方案计数。
然后我们考虑平移这条直线，使其卡在下面的洞上，（也就是类似于每次转向都在洞上转向），然后我们就可以考虑设 $f_i$ 表示最终在 $i$ 这个洞上的方案数，转移就是
$$f_i = 1+\sum_{x_j < x_i,y_j < y_i} f_j$$
直接用树状数组维护就可以了。
代码