模拟111 题解
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. 地理课
维护动态联通块大小,可以离线。
部分分提示使用并查集,所以可以想到一个类似线段树分治的过程。
即将每条边加入它存在的区间的线段树对应节点中。
之后不断递归线段树,开始递归时将数组记录并加入边,递归结束后将数组还原表示删边。
当递归到叶子节点,即贡献统计完毕,可以直接输出答案。
因为要进行还原操作,使用按秩合并并查集。
相关推荐
Set,List,Map的区别和功能到底是怎样的?其实它是与数组区分开来的。与数学中的集合最接近,两者都不包含重复元素。它的有些实现类能对集合中的键对象进行排序。切记在用到MAP时一定需要传入两个参数