【蒟蒻の日常】一个小技巧

今天在orac上做题,被吊打成狗,然后请教了隔壁闫老师,一眼秒好强啊,还有修老师直接翻出CF类比题QWQQQ图片20160623113040,我总结下这个技巧

先来看下题目吧OvO

Codeforces 526E Transmitting Level

题目大意 把一个环划分成最少的块数使得每块的和不超过一个询问值。n\leq 10^{6}

Method 1

遇到环形,显然就想着拆环成链。不难想出一个n^{2}的dp

f[i]表示在当前枚举的环状内,前i个东西划分,最少需要几块

显然有f[i]=f[j]+1,其中j满足A[i]-A[j]\leq K,A[i]-A[j-1]\geq K

不难发现j满足单调性,所以可以O(1)转移。

我们不满足于这个算法,发现根本没必要每次都重新计算dp值,直接算差值就行了。

也就是说,我们记录下f[i]的最早决策值,然后一次性扫一遍OK,时间复杂度O(n)

Method 2

有一个更优雅,更Universal的做法,就是我们先按照每个点为左端点,求出右端点最远是哪。

这样我们就得到了n个区间,现在我们关注下这些区间内的最短的区间[L,R],如果R相同取L最小的。

不难发现,组成最终的答案的若干区间中,一定存在一个区间的起点在[L,R]中。为什么?

非常显然 考虑反证法,假设其他区间的起点都不在这个区间里面,那么显然终点也不会在这个区间里面。其次,这样的话,这个区间等价于被包含了,那么显然,这个区间就不是最小的区间,与题设矛盾。故得证。

这样我们就可以枚举起点,然后在保证一定能构成最优答案的信心下,我们大力贪心即可

起点有O(R-L+1)个,因为这个是最小的,每一个区间的长度都会大于等于他,所以有O(\frac{N}{R-L+1})个区间,这样时间复杂度是O((R-L+1)\times\frac{N}{R-L+1})=O(N)。是不是很优雅?

再来回到我在Orac上遇到的题

FARIO2006 Guards(法奥联赛2006年第一题)

地球村是环形的,有n个建筑,建筑之间的距离已知,你要雇佣最少量的守卫去守护这个地球村,每个守卫能够保护与他距离不超过K的建筑,因为守卫也要休息,所以守卫只能摆放在建筑里。n\leq 10^{6}

考虑一个建筑放守卫,那么我们能得到一个区间,利用two-pointers可以在O(1)的时间内求出。

那么是不是和上一题很像呢?由于这个建筑可以覆盖编号小于他的建筑,我们需要记录覆盖某个点的最右边的建筑。这个在移动指针的时候就可以更新。

然后几乎就是一样的做法

时间复杂度O(n)

 

至此,这个小技巧的记录完结。QQ图片20160623113002

发表评论