尺取

发表于2021-08-26更新于2021-11-21阅读次数

游标卡尺真好玩

尺取法

eMmmmm

适用条件 单调性，区间长度递增，sum递增
具体来说：对于判断条件k，区间长度递增，k也递增。
例如判断条件为区间和sum时，区间长度递增，sum也递增。

模板

优雅-永不过时

  • 求最长不重复子串 xtu 1264

    1
    2
    3
    4
    5
    6
    7
    8
    ll l=0,maxl=0;
    ll cnt[555];vector<string> ans;
    memset(cnt,0,sizeof(cnt));
    for(ll r=0;r<s.length();r++){
        cnt[s[r]]++;
        while(cnt[s[r]]>1)  cnt[s[l++]]--;
        maxl=max(maxl,r-l+1);
    }

  • 求最短序列和>=k Subsequence POJ - 3061

    1
    2
    3
    4
    5
    6
    7
    ll l=1,sum=0,ans=INF;
    for(ll r=1;r<=n;r++){
        sum+=val[r];
        if(sum<k)  continue;
        while(sum>=k)  sum-=val[l++];
        ans=min(ans,r-l+2);
    }

经典例题 最短子序列和>=s

题目链接 https://vjudge.net/problem/POJ-3061
题意 求一段最短的子序列之和>=s
思路 跑尺取即可
核心代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0;i<n;i++){
    sum+=a[i];
    length++;
    if(sum<s){
        continue;
    }  
    else{
        while(sum>=s){
            if(length<min)  min=length;
            if(sum-a[l]<s)  break;
            sum-=a[l];
            l++;
            length--;
        }
    }
}

灵活运用

题目链接 https://www.cnblogs.com/iiyiyi/p/5962512.html
题意 求一段含负数的子序列之和的绝对值最接近t，输出该段子序列之和及左右端点。
思路 与平常子序列之和不同的一点就是含有负数，如何处理负数的问题是关键。因为有负数，导致序列非单调，不能使用尺取法。所以我们需要转化一下，关键又是转化！！！所以我们可以发现这类题的关键都是转化一下数据形式，把数据处理成我们能处理的形式，即可！核心思路都是一样的！这里我们将其转化为前缀和，再将前缀和按升序排列即可跑尺取法了。

灵活运用-结合Hash

题目链接 https://vjudge.net/problem/POJ-3320
题意 求一段最短序列包含所有知识点，知识点用一个整数表示，范围是到2^32
思路 因为知识点范围很大，到2^32，所以我们需要将知识点Hash下，不然存不下，之后就是将知识点数量理解为尺取里的Sum即可。