LA2678 Subsequence

题意

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

思路

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

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

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

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

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

代码

前缀和+尺取

前缀和+二分

 

LA3905 Meteor

题意

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

思路

扫描线。

这个题分为两部分,首先是要求出每一颗流星划过取景框的时间区间,这一步反而是这个题最复杂的地方,因为要讨论许多种情况,具体的讨论策略可以参考下面的代码。

求出来所有的区间之后,问题转化为选出一条线,使得这条线穿过的区间最多,这里就是扫描线算法派上用场的时候了。其实实现很简单,就是对于每个区间的两个端点,分别创建一个表示起始的事件和一个表示结束的事件,然后把所有事件按照出现的时间排序,接下来从小往大检查,遇到开始事件的时候计数器+1,遇到结束事件的时候计数器-1.

这里有一个问题,如果开始事件和结束事件恰好位于同一时点,怎么办?注意到我们的区间都是开的,这样我们只要优先处理结束事件,就不会导致解偏大了(这里面的逻辑需要自己试着理解一下)。

代码

 

UVA 11549 Calculator Conundrum

题意

给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。

这是一个循环的过程,你要找出在这个循环节中最大的数。

思路

首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。

取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。

找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。

代码

Floyd判圈法,数学方法求前n位。

 

UVa 11078 Open Credit System

题意

给出一个整数组成的序列,求两个整数A和B,其中A在数列的位置在B前面,令A-B最大,输出这个最大值。

思路

利用问题的单调性优化的典型例子。

暴力是O(n^2)的,显然无法通过。注意到A始终在B的前面,而且一定是A-B,也就是说对于每一个B,只要找到在它前面最大的A就可以了,不妨考虑随着B逐渐后移的同时,维护前面A的最大值,这样做的复杂度是O(n)的,很完美地解决了这个问题。

这种思想经常会被用在其他问题中作为一个需要优化的环节。

代码

 

 

UVA 11462 Age Sort

题意

排序,25MB大数据,都是整数,最大100最小0,内存极其紧张。

思路

面对这种数据范围很小,量很大的情况,考虑计数排序,原理非常简单就是开个数组统计一下不同值有多少个数字就搞定了,时间O(n)。

能做到O(n)的排序算法还有Sleep Sort,不过因为利用多线程睡眠差异太难控制所以也没啥实际意义。

被卡常数的时候,也可以考虑用计数排序进行没什么卵用的优化(结果可能就真卡过了)。

代码

LA3177 Beijing Guards

题意

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

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

思路

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

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

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

代码

 

LA3902 Network

题意

给出了一棵树,和一个初始的黑点(VOD服务器),所有边的边权均为1,你要求出最少还要染黑几个点,才能保证每一个白点到最近黑点之间的距离小于等于k。

思路

大概是贪心。

把给出的初始黑点当成树的根部,从根部dfs一次求出所有节点的深度,然后把深度最大的点(如果深度大于k)染黑,之后以这个点为中心dfs一次标记所有能覆盖的点。然后找第一个没有被覆盖的点,染黑,标记。。。直到所有点都被标记。

代码

 

UVa 11520 Fill the Square

题意

填充一个NxN网格,使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。

思路

注意到解的空间非常大,因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小,因为每一次的填充是从最小的字母开始尝试的。

代码

 

LA3635 Pie

题意

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

思路

二分答案。

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

代码

 

LA3971 Assemble

题意

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

思路

二分答案。

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

代码

 

Scroll to top