LA2678 Subsequence

题意

给出一个由n个整数组成的数列,要你求长度最短的连续序列,使得序列中所有元素的和大于等于S。

思路

单调性优化,或者说是尺取法。

暴力O(n^3)显然无法接受,套用前缀和优化再枚举O(n^2),还是无法接受。

在套用前缀和的基础上,可以枚举终点,二分查找起点,这样是O(nlogn),可以过了。

然而还有更好的办法,设两个指针,表示连续区间的左端点和右端点,一开始不断右移右端点,直到序列大于等于S,记录长度。然后右移左端点,再开始不断尝试右移右端点,直到条件再次满足,停下纪录,右移一下左端点。。。如此往复,直到右端点无法右移,且左端点无论怎么移动也无法满足条件。

这就是尺取法(名字来源于挑战程序设计竞赛),CF上面也叫Double Pointers,是一种基于单调性的优化手段。

代码

前缀和+尺取

前缀和+二分

 

LA3177 Beijing Guards

题意

可以参见LRJ白书第一章例题16.

有n个人,围个圈,每个人想要一定数量的礼物,注意每个人所持礼物不可以重样,两个相邻的人所持的礼物也不能重样,问你至少要准备多少种不同的礼物,才能符合要求?

思路

大概是个构造题综合二分答案。

首先要想到对n的分类讨论:

  • 如果n是偶数,那么你只需要准备两套不同配置的礼物,按照ABABABABAB这样循环下去就可以满足要求了,因此答案是max{r_i+r_((i+1)%n)}
  • 如果n是奇数,情况就比较复杂。我们可以先反向思考,如果给定有r种礼物,如何才能构造合适的礼物配置满足题设要求?白书里面给了这样一种方法:令编号为奇数的尽量选取靠前的种类,编号为偶数的尽量选取靠后的种类,即把r种礼物分成两半(即前、后两组),对于每一个人维护他按照上面策略进行选取的前组后组中元素数量,最后检查第一个人和最后一个人是否相容即可。这样我们就有了二分答案的检查方法了。

代码

 

LA3635 Pie

题意

给出若干个Pie,你要求出最大的大小k,使得每个人(包括自己)得到的Pie的大小都正好为k,注意在分Pie的时候,可以切碎,但是不可以给一个人不同种的Pie。

思路

二分答案。

类似于“最小值最大问题”,检查的时间可以接受,因此问题可以通过二分答案解决。

代码

 

LA3971 Assemble

题意

请参考LRJ白书第一章例题11

思路

二分答案。

典型的“最小值最大问题”,考虑二分答案,检查一次二分的时间是可以接受的,因此本题得到解决。

代码

 

SPOJ SORTBIT Sorted bit squence

[等待填坑]

 

CodeForces 484B Maximum Value

题意

给你一串数,让你找出一组(i,j),使得在保证第i项大于等于第j项的同时,第i项mod第j项最大,求这个最大值。

思路

要有一种转换的思维,余数最大的话,可以另一个方向进行考虑,a%b=c的话,a可以看成是kb+c,这个里面b,c是已知的,这个k可以枚举,这样就把求余数这个事情转换成了枚举/搜索,换一个思路问题可能就突破了。

对给出的数列sort一下,unique一下,erase一下,这样就有效的避免了重复数据的干扰(如果你不unique可能会被这个题的某组坑数据给弄T),而且sort完才能做。sort好之后,我们挨个数枚举,对于每个数k,我们考虑这个数列上0~k,k~2k,2k~3k,…这些个小区段,每个小区段中最大的那个数 mod k可能是最大的,我们挨个数挨个区段去枚举就可以了。
但是暴力枚举是过不了的,我们就把在数列中找k,2k,…这个过程改成二分搜索,这样复杂度降为nlogn就行了。

代码

 

 

POJ 3685 Matrix

题意

好像是《挑战程序设计竞赛》上面的原题。题意是给你一个矩阵上每一项的位置与值对应的公式,让你求第k小的项。

思路

我们仔细看公式会发现对于每一个固定的j,公式结果随i单调递增,这样我们可以二分答案,对于mid值,我们在每一列再二分一次,求出比这个数小的数的个数,然后每一列的个数相加,就是这个数的排名。然后这个排名可以作为二分中判定的基准。这里还有一种替代思路,就是对于每一列不二分,而是解一个二次方程直接求出每一列的分排名。

代码

 

CodeForces 484B Maximum Value

在lower_bound之后如果加入了多余的判断(判断pos的位置等等),就会T,如果没有用unique来压缩输入,就会T。

总觉得很寸,应该是数据做的有漏洞。

解法的思路就是先从小到大排序,然后从第一项开始,借用素数筛法的思路,对于每个数检查以这个数的倍数为终点的各个区间,然后找出每个区间之内离终点最近的数,更新答案。找终点的过程使用了二分搜索,STL自带的lower_bound和upper_bound就能很好地工作,使用upper_bound的话还有一个小窍门就是把搜索目标设成目标-1,这样的话搜索完落在的点就和lower_bound是一样的了。

CodeForces 279B Books

lower_bound真的不是那么好掌握的。。。有时候很坑。

这个题就是前缀和还不够,在前缀和的基础上还要使用二分搜索进一步减小时间复杂度才能过掉大数据。

CF 460C Present

二分答案求解,这种求最小值的最大值,或者可以转化成求最小值的最大值的问题都可以通过二分答案,回代验证的方法求解。

这个题要注意在ok那个函数中res会被加爆int,如果把判定推出的if写进for里就可以避免加爆还能剪枝加速,要么就用long long也是可以的。

注意在回代检验的过程中,使用了前缀和来快速提取当前节点已经在先前被浇了多少次水。

Scroll to top