RainAir
My OI Blog
RainAir
ARC101 题解

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 https://blog.aor.sd.cn/wp-content/uploads/2019/02/20190103084314258.png
首先我们可以将“每一条边都覆盖”的限制转为有些边不被覆盖来进行容斥,容斥系数就是 $(-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$。

题解

还是我不会的题,我太菜了https://blog.aor.sd.cn/wp-content/uploads/2019/02/20181230194731601.png
我们先去掉只会掉入一个洞的机器人,然后考虑剩下的机器人它都可以向左右两个洞去掉。我们将这个机器人的初始位置距离左右两个洞的距离分别记做 $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$$
直接用树状数组维护就可以了。
代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/890
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ARC101 题解
C-Candles 普及组题,不说了 代码 D-Median of Medians 题意 定义序列 $a_1,a_2,\cdots ,a_n$ 的中位数为排序后从小到大第 $\lfloor \frac{n}{2}\rfloor+1$ 个数。 给定长度为 $N$ 的…
扫描二维码继续阅读
2019-10-18
标签
近期评论