UOJ Logo wym6912的博客

博客

PPOJ Test Round 2题解

2017-04-18 22:51:38 By wym6912

A:输出 Hello World!\\n

B:简单的模拟题,注意坐标是以1为开始的

C:小的数计算,大的数可以打表= =还可以利用 RMQ ,枚举每个约数的倍数复杂度O(NlogN)

本题的要求是,求出一个给定区间内的含因子数最多的整数。

首先,有必要明确一下如何求一个数的因子数。若一个数N满足$N=P_1N_1·P_2N_2·P_3N_3·…·P_mN_m$,其中$P_1, P_2, …, P_m$是N的m个质因子。

则N的约数个数为$(N_1+1)·(N_2+1)·(N_3+1)·…·(N_m+1)$。这一公式可以通过乘法原理来证明。

有了求因子数的公式后,最容易想到的算法就是,枚举区间内的每个整数,统计它们的约数个数。 这个算法很容易实现,但是时间复杂度却相当高。

因为区间中整数的范围是1~1000000000,整个枚举一遍并计算因子数的代价约为$10^9×(10^9)^{0.5}=10^{13.5}$。这个规模是无法忍受的。所以,我们需要尽量优化时间。

分析一下枚举的过程就会发现,如果我们分别枚举两个数n和p·n(p为一相对较大的质数),那么我们将重复计算两次n的因子数。

其实,如果枚举顺序得当的话,完全可以在n的基础上去计算p·n,而如果能在n的基础上计算p·n,就相当于计算p·n的因子数只用了O(1)的时间。

这是一个比较形象的例子,类似的(可能相对更复杂一些)重复计算在枚举过程中应该是普遍存在的。

这就是枚举效率低的根本所在。为了解决这一重复,我们可以选取另一种搜索顺序——枚举质因子。这样的搜索顺序可以避免前面所说了类似n和p·n的重复计算。

定义number为当前搜索到的数。

初始时,令number=1,然后从最小的质数2开始枚举,枚举因子中包含0个2、1个2、2个2、…、k个2的情况……直至number·$2^k$大于区间的上限(max)。

对于每个“$2^k$的情况”,令number:=number*$2^k$,在这个基础上,再枚举因子3的情况。

然后在3的基础上枚举因子5的情况,然后是7的情况……整个过程是一个深度搜索的过程,搜索的过程中,利用前面提到的求因子数的公式可以算出当前的number的因子数供下一层枚举继承。

当number大于等于区间下限(min)时,我们就找到了一个区间内的数(枚举的过程已保证number不超过上界)。

所有枚举得到的区间内的数中,因子数的最大值就是我们要求的目标。

这样的枚举完全去除了重复计算,但是这还是不够的,因为光1~1000000000内的数每枚举一遍就有$10^9$个单位的操作。

所以,我们还需要找到一些剪枝的方法,进一步优化时间。

我们看到,如果当前搜索状态为(from, number, total),其中,from是指当前枚举到的质因子(按从小到大枚举),total是指number中包含的因子数。

那么剩下的因子数最多为q=log $from_{max}/number$,这些因子组成的因子个数最大为2q。因此,当前所能取到的(理想情况)最大约数个数就是total·2q。

如果这个数仍然无法超过当前最优解,则这一分支不可能产生最优解,可以剪去。

此外,如果[(min-1)/number]=[max/number],则表示以当前状态搜索下去,结果肯定不在区间内了,就无法产生合法解,也可剪去。不过,这一剪枝作用不是很大,因为即使不剪,再搜索一层也就退出了。

以上两个剪枝,前一个是最优化剪枝,后一个是合法性剪枝。相比较而言,前一个剪枝的作用要大得多。

下面我们用平摊分析的方法来讨论一下搜索的复杂度。

由于枚举的过程中没有重复计算,每枚举一个质因子,都可以得到一个不同的number(number≤max),所以可以将每一个单位的枚举质因子的代价与一个不超过max的number对应,并且还可在两者之间建立双射。

不同的number最多只有max个,所以枚举的总代价不超过O(max),max≤$10^9$。

加上了剪枝以后,计算总代价就远远小于O(max)了。从运行效果来看,即便是最大数据,也可以很快出解。

D:本题要求最大值最小,所以直接用二分。

先二分枚举一个答案ans,对图进行一次bfs,只要是小于等于ans的点都可以通过。

可以加一些小优化,如:只要到达最后一行就可以退出。

E:二分做法,对树排序,再进行二分比高度即可,因为高度参数越高,能砍到的木材越少,所以可以二分。

F: 题意:

给出很多类边

查询某类边删除某条构成的子图是否是二分图,以及有多少类边构成的子图是二分图

要求支持修改边的属性

考虑只有一类边和加边

使用并查集维护一个连通块类的边

对于点i记录dis[i]为其与其在并查集中的父亲是否属于同一类点

==

有删边操作

每条边对答案的贡献是独立的

使用陈丹琦分治转化为加边

== 多类边

取出和该类边有关的所有询问

求出每类边构成子图为二分图的时间区间以回答询问

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。