尺取法小结

/ 0评 / 0

尺取法顾名思义是用尺子一段一段测量。测量物件长度通常是一端对其,看另一端的刻度得出答案;
借挑战上的话 尺取法通常是数组保存一对下标,即所选取的区间的左右端点,然后根据实际问题不断推进区间,在这其中可以根据已有经验保持右端点从上一状态继续推进。

虽然比较暴力,但往往很高效,可以优化普通枚举区间到 O(n)时间。遂在此总结下。

POJ 3061 Sequence

题意

给出一个长度为$N(1e5)$的整数$(1e5)$序列,找出一段长度最小的区间满足区间元素和大于等于给定的$S(1e8)$

trick

先固定好初始的长度,然后左端点享有移动一个单位,相应调整右端点,这样便能在 O(n)取遍序列所有满足的情况。
第一次写的小贴士:找满足的右端点时 r++,那么区间长度是 r-l不需要额外加 1

code

HDU 5672 String

题意

给出长度小于$1e6$的字符串,问有多少子串其中至少有$k$个不同的字母

trick

考虑到现在的区间长度内的信息可以利用,当然是尺取一下:对于满足的串 [l,r], 其后的 len-r+1当然都满足啦, O(n)即可

code

POJ 3320 Jessica's Reading Problem

题意

给出$P(1e6)$页书,每页包含一个知识点,求一段长度最小的连续的区间使得包含所有的知识点。

trick

尺取+map映射+set,$O(n)$,细节看代码

code

HDU 1937 Finding Seats

题意

题意给出平面图$R*C$,选择一个面积最小的子矩阵使得内部点( .)的个数大于等于$k$个

trick

类似的历史信息再利用优化暴力,不妨打前缀和 cnt[i][j]表示从(1,1)到(i,j)的矩形内部点大于等于k的个数
化为经典的尺取做法递进枚举 $O(n^3)$

code

HDU 6103 Kirinriki

题意

定义长度相同的两字符串 A,B,$dis_{A,B} = \sum\limits_{i=0}^{n-1}|A_{i}-B_{n-1-i}|$
问在给定字符串 S下求长度最小的两个不重叠子串使得 dis小于等于 m
多校第 6场给队友写的,一顿操作过,好像是 暴力枚举+优化

trick

这里用的尺取也是暴力枚举中心点的思想
大概的尺取过程,右边就不画了

code

犹疑

天空深处孤寂依然
给你满天的星
和说着星的
一百种理由
使你凝视

发表评论

电子邮件地址不会被公开。 必填项已用*标注