尺取法小结


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

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

POJ 3061 Sequence

题意

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

trick

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

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5+7;
int a[maxn];
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n, S, tot = 0;
        scanf("%d%d", &n, &S);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            tot += a[i];
        }
        if (tot <= S) {
            printf("%d\n", tot == S ? n : 0);
            continue;
        }
        int l = 0, r = 0; //初始化尺子
        int sum = 0; // 初始化尺子长度存的信息
        int res = n + 1; //初始化答案inf=n+1
        while (1) {// 尺子不断向右推直到从某个左端起最大能取到的和小于S
            while (r <= n && sum < S) //推尺子右端到满足题意
                sum += a[r++];
            if (sum < S) break;
            res = min(res, r - l); // r已经加过1
            sum -= a[l++]; //推尺子左端一格,同时更新sum
        }
        printf("%d\n", res > n ? 0 : res);
    }
}

HDU 5672 String

题意

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

trick

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

code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
typedef long long ll;
#define clr(a,b) memset(a,b,sizeof(a))
char str[maxn];
int vis[27];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        clr(vis, 0);
        int k; scanf("%s %d", str, &k);
        int len = strlen(str);
        ll ans = 0;
        int l = 0, r = 0;
        int sum = 0;
        for (;;) {
            while (r < len && sum < k) {
                int cur = str[r++] - 'a';
                if (!vis[cur]) sum++;
                vis[cur]++;
            }
            if (sum < k) break; //从某个左端点取遍也不足k个相异字符,推出
            ans += len - (r - 1);// 此处r++后减掉但因为0-base不用再+1
            int cur = str[l++] - 'a';
            vis[cur]--;
            if (!vis[cur]) sum--;
        }
        printf("%lld\n", ans);
    }
}

POJ 3320 Jessica's Reading Problem

题意

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

trick

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

code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int a[maxn];
int main() {
    int p;scanf("%d",&p);
    set<int> all;
    for(int i=0;i<p;i++) {
        scanf("%d",&a[i]);
        all.insert(a[i]);
    }
    int n = all.size();
    map<int,int> cnt; //cnt[知识点]=次数
    int sum  = 0;
    int l = 0, r = 0;
    int res = p;
    for(;;) {
        while(sum < n && r < p)
            if(!cnt[a[r++]]++) sum ++; //该知识点第一次出现
        if(sum < n) break;
        res = min(res, r-l);
        if(!--cnt[a[l++]]) sum--; //右移1位导致该知识点不出现更新sum
    }
    return !printf("%d\n",res);
}

HDU 1937 Finding Seats

题意

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

trick

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

code


\#include <bits/stdc++.h> using namespace std; const int maxn = 333; int mp[maxn][maxn], sum[maxn][maxn]; char str[maxn]; const int inf = 0x3f3f3f3f; int main() { int k, r, c; while (scanf("%d%d%d", &r, &c, &k) != EOF&&r+c+k) { memset(sum, 0, sizeof(sum)); for (int i = 1; i <= r; i++) { scanf("%s", str + 1); for (int j = 1; j <= c; j++) { mp[i][j] = str[j] == '.'; sum[i][j] += sum[i][j - 1] + mp[i][j]; } } for (int i = 2; i <= r; i++) for (int j = 1; j <= c; j++) sum[i][j] += sum[i - 1][j]; //打完前缀和 int ans = inf; for (int i = 1; i <= c; i++) for (int j = i; j <= c; j++) {// 枚举第i列到第j列 int p = 1; //行游标 for (int t = p; t <= r; t++) { while(sum[t][j]-sum[t][i-1]-sum[p-1][j]+sum[p-1][i-1]>=k) ans = min(ans, (j - i + 1) * (t - p + 1)), p++; } } printf("%d\n",ans); } }

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

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
char str[maxn];
int ans;
void solve(int len, int limit) {
    for (int i = 2; i <= len; i++) {
        //遍历右端点,取等号便于处理奇偶mid
        int mid = (i >> 1);
        int l = 0, r = 0;
        int sum = 0;
        for (int j = 0; j < mid; j++) {//遍历左端点
            sum += abs(str[j] - str[i - j - 1]);
            if (sum <= limit)
                r++, ans = max(ans, r);
            else { //相同长度平移
                r--;
                sum -= abs(str[j] - str[i - j - 1]); //还原状态 减掉当前的j
                sum -= abs(str[l] - str[i - l - 1]);// 减去当前的l
                l++, j--; //移动左端点,下一时刻相当于平移
            }
        }
    }
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int m; scanf("%d %s", &m, str);
        ans = 0;
        int len = strlen(str);
        solve(len, m);
        strrev(str); //正反各跑一遍
        solve(len, m);
        printf("%d\n", ans);
    }
}

犹疑

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


KISS