icontofig | 发布于 2019-08-08 23:29:10 | 阅读量 272 | DP 回溯
发布于 2019-08-08 23:29:10 | DP 回溯
2019 Multi-University Training Contest 6 1002 Nonsense Time  LIS(O(nlogn)版本)
题目大意给n个数,每个时刻就会有一个新的数可用,求每个时刻所有可用的数字按照序列位置组成的最长上升子序列长度。数据生成完全随机。 题解由于数据完全随机生成,所以当所有数都可用的时候,LIS的期望长度是n1/2 。我们删掉一个数,这个数在LIS中的概率期望是1/n1/2。 我们可以把原问题逆向来考虑,从一开始所有数可用,然后不断删除数字。 如果删除的数字在上一次的LIS中,则我们需要重新求一次LIS,否则就延续上一次的答案。 如果我们使用O(nlogn)方法的LIS,那么一组数据的总体时间复杂度就是O(n3/2logn) 这题因为手写二分写丑了没用lower_bound被卡T一次,然后因为行末空
继续阅读
icontofig | 发布于 2019-07-20 09:58:14 | 阅读量 277 | DP 贪心 回溯
发布于 2019-07-20 09:58:14 | DP 贪心 回溯
Codeforces Round #2 The least round way DP+贪心
题目大意现在给一个n*n的矩阵,你要从(1,1)走到(n,n),求一条路径,使得路径上所有数的乘积的尾部零的个数最少。 题解我们先考虑尾部零怎么能够产生。 首先要产生尾部零,就一定要乘10或者0。 先来考虑0的情况,如果你走一条带有0的路径的话,那么最后乘积一定会是0,尾部零的数量为1个。 如果我们不走带有0的路径的话,那么要产生尾部0就一定要有因数10,而且有多少个因数10就有多少个尾部零。 而10这个数,很明显的,我们能够将其分解为2*5,由质因数分解的唯一性,我们只需要统计路径上2和5的个数,然后取其中的最少就是最终因数10的个数,也即尾部零的个数。 讨论完尾部0的产生,我们来看一下怎样
继续阅读