模拟111 题解

kuoying 2019-11-12

A. 物理课

发现每次反弹之后移动的距离是上一次的$d^2$倍。

计算出第一次反弹之前移动的距离的答案$k$,

总的答案即$\sum \limits_{i=0}^{inf}d^{2*i}*k$。

发现这个东西就是一个等比数列求和。

设答案为$s$,那么有$s=\sum \limits_{i=0}^{inf}d^{2*i}*k$

$d^2s=\sum \limits_{i=1}^{inf}d^{2*i}*k$

作差可得$(1-d^2)s=k$,即$s=\frac{k}{1-d^2}$。

这个东西似乎是生成函数中一个基本的式子。

B. 数学课

对于一个数$x$,如果它在集合$A$中,

那么$2*x$一定在集合$B$,由此又可得$4*x$也在集合$A$中。

所以只需要考虑每个奇数$x$在哪个集合中,决定了$x*2^k$在哪个集合中。

很多的奇数是等价的,也就是说它们决定的元素个数相同。

所以可以处理出每个等价类中有多少个元素,

对于每个奇数元素,如果它出现在集合A中,那么会对集合A贡献a个元素。

如果它出现在集合B中,那么会对集合A贡献b个元素。

可以将每个奇数元素视作一个物品,然后可以$O(n^2)$暴力背包$dp$。

然后发现本题存在一个特殊性质,即$abs(a-b)<=1$

因为每个物品必须选其中之一,不妨直接选入较小的一个。

如果二者贡献的答案相同即等价,可以直接给答案$*2$。

因为差不超过$1$,可以直接用组合数算出选哪几个可以构成合法的方案。

组合数的级别很大,但是模数提示可以用$lucas$定理,所以就解决了。

C. 地理课

维护动态联通块大小,可以离线。

部分分提示使用并查集,所以可以想到一个类似线段树分治的过程。

即将每条边加入它存在的区间的线段树对应节点中。

之后不断递归线段树,开始递归时将数组记录并加入边,递归结束后将数组还原表示删边。

当递归到叶子节点,即贡献统计完毕,可以直接输出答案。

因为要进行还原操作,使用按秩合并并查集。

相关推荐