组合数
求n和m都各在一个范围里的组合数里能被k整除的数的个数.
用熟悉的组合数的公式.
\( C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \)
把组合数先处理出来.
对于多组询问, 求出上面那个数组的二维前缀和即可.
蚯蚓
你有n只蚯蚓. 每秒把最长的蚯蚓砍成同比例的两段, 且其它蚯蚓变长. 求m秒中每一秒被砍的蚯蚓和最后所有的蚯蚓.
\( n \leq 10^5, m \leq 7*10^6 \)
目测那个t只是为了输入输出不超时.
正常的暴力是用堆来维护蚯蚓长度.
发现一个性质, 下一次被砍的蚯蚓被砍之后两段肯定会分别短于本次被砍的蚯蚓的两段.
仔细想想没有低于\( O(m) \) 的做法.
所以我们把堆换成若干个队列, 每次只取队首的蚯蚓来比较, 砍, 然后塞回队尾. 保证队列中的元素单调.
这样时间复杂度就变成线性了.
小鸟
平面上有若干只猪. 你可以从原点发射一个抛物线并消灭抛物线上的所有猪. 求最小发射多少次.
\( n \leq 18 \)
我们知道两点确定一条过原点的抛物线. 所以枚举两只猪就能得到所有能消灭至少两只猪的消灭方式. 剩余的猪只能直接消灭.
可以使用状态压缩型动态规划来解决这个问题. 只需要记录下当前已经消灭了哪些猪, 就可以进行转移了.
ps
题目难度还是比去年高. 祝各位好运.
laekov版权所有, 未经允许不得转载. 侵权必究.