---

---

尺取法 解题报告

PKU 2100 Graveyard Design

链接：PKU 2100 Graveyard Design
题意：给定一个数 $n(n\le 10^{14})$，求所有满足 $n={\sum }_{k=i}^j{k}^2$ 的 $(i,j)$。

• 可以把 $i,j$ 看成是 $[1,\sqrt{n}]$ 内的数，并且永远满足 $i\le j$，维护一个区间平方和 $s$，然后执行如下操作：
• 1）初始化令 $s=0,i=1,j=0$；
• 2）自增 $j$，并且令 $s=s+j^2$；
• 3）若 $s>n$，则 $s=s-i^2$，$i$ 自增；重复这一步直到 $s<=n$ 满足后跳 3）；
• 4）若 $s=n$，则当前的 $(i,j)$ 是一组可行解，记录；
• 5）回到 2）；
• 最后输出所有可行解。

PKU 3061 Subsequence

链接：PKU 3061 Subsequence
题意：给定 $n(n<10^5)$ 个正数 $a_i(a_i\le 10^4)$ 和一个正数 $p(p<10^8)$。找到一个最短的连续子序列，满足它的和 $s\ge p$。

• 可以把 $i,j$ 看成是 $[1,n]$ 的下标，并且永远满足 $i\le j$，维护一个区间和 $s$，然后执行如下操作：
• 1）初始化令 $s=0,i=1,j=0$；
• 2）自增 $j$，并且令 $s=s+a_j$；
• 3）若 $s\ge n$，更新可行解 $(i,j)$，则 $s=s-a_i$，$i$ 自增；重复这一步直到 $s<n$ 满足后跳 2）；
• 最后输出长度最小的可行解。

PKU 2739 Sum of Consecutive Prime Numbers

链接：PKU 2739 Sum of Consecutive Prime Numbers
题意：给定一个数 $n(n\le 10^4)$，求所有满足 $n={\sum }_{k=i}^j{p}_k$ 的 $(i,j)$ 的对数（其中 $p_k$ 代表第 $k$ 个素数）。

• 可以把 $i,j$ 看成是第几个素数的下标，维护一个素数和 $s$，然后执行如下操作：
• 1）筛选素数 $p_i$ 后，初始化令 $s=0,i=1,j=0$；
• 2）自增 $j$，并且令 $s=s+p_j$；
• 3）若 $s>n$，则 $s=s-p_i$，$i$ 自增；重复这一步直到 $s<=n$ 满足后跳 3）；
• 4）若 $s=n$，则当前的 $(i,j)$ 是一组可行解，记录计数器 $cnt$；
• 5）回到 2）；
• 最后输出计数器 $cnt$ 即可。

PKU 3320 Jessica’s Reading Problem

链接：PKU 3320 Jessica’s Reading Problem
题意：给定 $n(10<n<100000)$ 个数 $a_i(a<2^{31})$ 。找到一个最短的连续子序列，满足它包含所有的数。

• 首先把所有的数进行离散化，使得每个数都能准确映射到下标 $[1,t]$；
• 然后把 $i,j$ 看成是第$i$个数的下标，维护一个哈希表，然后执行如下操作：
• 1）初始化令 $s=0,i=1,j=0$；
• 2）自增 $j$，并且自增 $hash[a_j]$，如果 $hash[a_j]=1$ 则自增 $s$；
• 3）若 $s=t$，记录 $(i,j)$ 作为其中一个可行解，并且自减 $hash[a_i]$，$i$ 自增；如果$hash[a_i]=0$，则自减 $s$，重复这一步直到 $s<t$ 则跳 2）；
• 最后输出长度最小的 $(i,j)$ 即可。

HDU 2158 最短区间版大家来找碴

链接：HDU 2158 最短区间版大家来找碴
PKU 3320 Jessica’s Reading Problem 加强版，做法类似。

HDU 2369 Broken Keyboard

链接：HDU 2369 Broken Keyboard
题意：给定一个长度为 $n(n\le 10^6)$ 的字符串 和 $m$，求不同字符数不超过 $m$ 最长子串。

• 可以把 $i,j$ 看成是第几个字符的下标，维护一个哈希表 $hash$，然后执行如下操作：
• 1）初始化令 $s=0,i=1,j=0$；
• 2）自增 $j$，并且自增 $hash[a_j]$，如果 $hash[a_j]=1$ 则自增 $s$；
• 3）若 $s>n$，自减 $hash[a_i]$，$i$ 自增；如果$hash[a_i]=0$，则自减 $s$，重复这一步直到 $s\le n$；
• 4）若 $s\le n$，则当前的 $(i,j)$ 是一组可行解，记录最大值；
• 5）回到 2）；
• 最后输出最大区间的值即可。

HDU 2668 Daydream

链接：HDU 2668 Daydream
题意：给定一个长度为 $n(n\le 10^7)$ 的字符串，求所有字符都不相同的最长子串。

• 可以把 $i,j$ 看成是第几个字符的下标，维护一个哈希表 $hash$，然后执行如下操作：
• 1）初始化令 $i=0,j=-1$；
• 2）自增 $j$，并且自增 $hash[a_j]$；
• 3）如果 $hash[a_j]>1$ ，则自减 $hash[a_i]$，$i$ 自增；
• 4）如果 $hash[a_j]=1$，则更新 $(i,j)$ 长度；
• 5）回到 2）；
• 最后输出最大的区间的值即可。

HDU 5672 String

链接：HDU 5672 String
题意：给定一个长度为 $n（10\le n\le 10^6）$ 字符串 $s$，问有多少子串包含至少 $k(1\le k\le 26)$ 个不同字符。

• 用两个指针 $(i,j)$ 代表某个阶段下子串指向的下标；
• 对于某个子串，如果已经有 $k$ 个不同字符，那么当前的区间 $(i,j)$ 一定是满足条件的子串，并且 $(i,j+1)，(i,j+2)，(i,len-1)$ 也都是满足条件的子串，计数器加 $len-j$；
• 然后自增 $i$ 继续判断可行性即可。

HDU 5056 Boring count

链接：HDU 5056 Boring count
题意：对于一个字符串，如果它的每个字母数都小于等于 $k$，则称其为 $good$ 串。给定一个长度为 $s(1\le s\le 10^5)$ 且只包含小写字母的字符串，求它的 $good$ 串的数量。

• 用两个指针 $(i,j)$ 代表某个阶段下子串指向的下标；
• 如果某个子串 $s[i:j]$ 满足条件，那么可以得出：以 $j$ 为右端点的情况下，左端点只要大于等于 $i$，那么这个串一定是 $good$ 串，所以以 $j$ 为右端点，满足条件的个数为 $j-i+1$；
• 所以整个调整过程就是：$j$ 自增的过程，如果满足每个字母数都小于等于 $k$ 的情况下，累加 $j-i+1$；否则，自增 $i$，继续判断可行性。

HDU 6205 card card card

链接：HDU 6205 card card card
题意：给定一个 $n(n\le 10^6)$ 个元素的环形序列，求它的最大子序列。

• 由于是环形的，所以可以先拷贝一份，然后进行双指针 $(i,j)$ 移动，只有当条件满足时左指针才右移，条件为：
• 求和小于零 或者 $j-i+1>n$；
• 中途记录最大值即可。

HDU 6103 Kirinriki

链接：HDU 6103 Kirinriki
题意：定义两个长度均为 $n(n\le 5000)$ 的字符串的距离为：$$di{s}_{A,B}=\sum _{i=0}^{n-1}|A_i-B_{n-1-i}|$$求找出最长的两个子串，满足他们不相交，且距离小于等于 $m$。

• 朴素方法为枚举长度，然后 $A$ 串的起点，$B$ 串的终点，模拟算一遍得出最优解，算法时间复杂度 $O(n^4)$。
• 定义两个双指针 $(a_l,a_r)$，$(b_l,b_r)$；
• 1）枚举 $k=n-1\to 0$
• 2）初始化 $d=0$，$a_l=0,a_r=-1$ 并且向右移动 $a_r$ 指针；$b_r=k,b_l=k+1$ 并且向左移动 $b_l$ 指针；
• 3）每次 $a_r$ 指针 右移，$b_l$ 指针左移，如果 $b_l>a_r$ 则 $d=d+dis(A_{a_r},B_{b_l})$；否则跳出循环，回到 2）；
• 4）如果 $d>m$，$d=d-dis(A_{a_l},B_{b_r})$，并且 $a_l$ 右移，$b_r$ 指针左移；
• 5）如果 $d\le m$，则更新当前 $maxlen=max(maxlen,a_r-a_l+1)$ 为最优长度。
• 然后把字符串反序，再做一次如上操作。
• 最后，输出 $maxlen$ 即可。

HDU 6119 小小粉丝度度熊

链接：HDU 6119 小小粉丝度度熊
题意：给定 $n(n\le 10^5)$ 个区间，区间之间可能重叠，现在给出 $m$ 个数，希望把区间补成连续区间，问最多能够补成多大的连续区间。

• 首先，先按照区间左端点排序，然后利用贪心将所有区间转换成不相交区间；
• 然后计算相邻两个不相交区间之间需要补多少数，可以利用前缀和，用 $O(1)$ 的时间求出 $[i,j]$ 区间之间要补多少数才能连续，然后利用双指针进行求和单调性求解即可。

HDU 1937 Finding Seats

链接：HDU 1937 Finding Seats
题意：给定一个 $n\times m(n,m\le 300)$ 的 01 矩阵和一个数，求一个面积最小的子矩阵，保证它和大于等于 $k$ 。

• 首先用 $su{m}_{ij}$ 计算出矩阵的前缀和。
• 枚举 $l，r$ 作为子矩阵的左右端点，然后对上下端点采用双指针，从而转化成一维的求和单调性问题。

HDU 5178 pairs

链接：HDU 5178 pairs
题意：在 $x$ 轴上有 $n$ 个点 $(x_i,0)(i=0,1,2,\dots ,n-1)$，求有多少整数对 $(a,b)$ 满足 $|x_b-x_a|\le k(a<b)$。

• 首先对所有数按照 $x$ 轴递增排序；
• 然后用两个指针 $(i,j)$ 代表下标，并且不断自增 $j$ 下标；
• 当 $x_j-x_i>k$ 时，自增 $i$ 下标；否则以 $j$ 结尾的满足条件的区间个数就是 $j-i$，直接累加；

PKU 2566 Bound Found

链接：PKU 2566 Bound Found
题意：给定一个 $n(n\le 100000)$ 和 $k$，然后是 $n$ 个数字 $x_i(|x_i|\le 10000)$ 组成的序列，再给出 $k$ 个数 $t_l$，要求对于每个 $t_l$，求出绝对值最接近 $t_l$ 的区间。

• 尺取法的前提是满足单调性，$x_i$ 有可能是负数，所以这题需要进行一个思路转换。
• 首先记录下前缀和 $su{m}_i$，注意，需要将 $su{m}_0=0$ 也加入进来。
• 问题就转变成了求满足条件 $|su{m}_j-su{m}_i|<t_l$ 的最大的 $|su{m}_j-su{m}_i|$，这时候需要满足的是 $i<j$，如果能够做到 $su{m}_i<su{m}_j$ 恒成立，那么我们就可以采用尺取法了。
• 所以可以对前缀和进行排序，注意排序的时候需要记录下原下标。
• 然后就是对排序后的数组 $su{m}_i$ 进行尺取法了。

HDU 5806 NanoApe Loves Sequence Ⅱ

链接：HDU 5806 NanoApe Loves Sequence Ⅱ
题意：给定 $n(n\le 200000)$ 个数，求第 $k$ 大的数 $\ge m$ 的区间的个数。

• 将原数组中 $\ge m$ 的数变成 1，其它为 0，然后求出前缀和 $su{m}_i$。
• 利用尺取法维护两个指针 $(i,j)$，如果某种情况下 $su{m}_j-su{m}_i\ge k$，则所有区间 $[i+1,k](j\ge k\ge n)$ 都满足上文所给的条件。所有以 $i+1$ 为左端点的满足条件区间数就是 $n-j+1$ 个；累加到答案。
• 并且 $su{m}_j-su{m}_i\ge k$ 时，左指针 $i$ 自增。