首页 算法

尺取法，又称滑动窗口或双指针，是一种在序列上寻找最优解的方法．对于序列的每个左端点 ll，让右端点 rr 尽可能延伸至最远，得到一个答案区间，rr 已到达最远后将与 ll 有关的信息弹出，对于多个答案区间找出最优解．复杂度通常为线性．

不过一些时候这样不能保证求得的是最优解，这时就需要其他思路，或者使用莫队（根号算法）暴力求解．

# HDU5178 Pairs

# 题面

有 nn 个值 x1,x2,…,xnx_1, x_2, \dots,x_n，求使得 ∣xb−xa∣⩽k,a<b|x_b-x_a|\leqslant k,a<b 的数对 (a,b)(a,b) 的个数．

# 解

分析可知 a<ba<b 这一条件只是确保无重复，次序其实对于最终答案没有影响．

考虑先对 xx 排序（因原题目有绝对值，无影响），for​ ll 尺取出最远的 rr， 则 (l,r](l,r] 间的每个数均与 ll 构成合法数对．

# 代码

#include <stdio.h>
#include <algorithm>
const int N = 110000;
typedef long long LL;
int T, n;
LL k, x[N];
int main() {
     
    freopen("hdu5178.in", "r", stdin);
     
    scanf("%d", &T);
     
    while(T--) {
          
        scanf("%d%lld", &n, &k);
          
        for(int i=1; i<=n; ++i) 
            scanf("%lld", x+i);
          
        std::sort(x+1, x+n+1);
          
        LL ans = 0;
        for(int l=1, r=2; l<=n; ++l) {
            for(; r <= n and x[r] - x[l] <= k; ++r);
            ans += r - l - 1;
        }
         
        printf("%lld\n", ans);
    }
     
    return 0;
}
# HDU6119 小小粉丝度度熊
类似 CF1041D Glider
# 题面
给出 nn 个已签到的天数区间，mm 张补签卡，求可获得的最大连续签到时长。
# 解
尺取模板。
天数区间可重叠，须进行合并。
需要注意的是，当已确定最长合法区间 [l,r][l,r] 后（即下一个区间与 rr 的距离大于剩余的补签卡数量，连不上），应把剩余补签卡全部应用到 rr 之后的天数上得到更优解。
# 代码
边界条件较多。
RR 为已加入队列的最后一个区间，判断的是区间 R+1R+1 的合法性。
特判第一个区间，开始时 sumsum 直接加上第一个已签到区间的长，使用 00 张补签卡。
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 110000;
struct node {
    int l, r;
} a[N], b[N];
bool flag[N];
bool cmp(node a, node b) { return a.l < b.l; }
int n, m;
int max(int a, int b) { return a > b ? a : b; }
int main() {
     
    freopen("hdu6119.in", "r", stdin);
     
    while(scanf("%d%d", &n, &m) != EOF) {
          
        for(int i=1; i<=n; ++i) 
            scanf("%d%d", &b[i].l, &b[i].r),
            flag[i] = false;
                
        sort(b+1, b+n+1, cmp);
          
        for(int i=2; i<=n; ++i) {
            if(b[i-1].r >= b[i].l) {
                b[i].l = b[i-1].l;
                b[i].r = max(b[i].r, b[i-1].r);
                flag[i-1] = true;
            }
        }
          
        int tot = 0;
        for(int i=1; i<=n; ++i) {
            if(flag[i]) continue;
            a[++tot].l = b[i].l;
            a[tot].r = b[i].r;
        }
         
        int sum = a[1].r - a[1].l + 1, f = 0, ans = 0;
        for(int L = 1, R = 1; L <= tot; ++L) {
            for(; R + 1 <= tot and f + a[R+1].l - a[R].r - 1 <= m; ++R)
                sum += a[R+1].r - a[R].r,
                f += a[R+1].l - a[R].r - 1;
            ans = max(ans, sum + m - f);
            sum -= a[L+1].l - a[L].l;
            f -= a[L+1].l - a[L].r - 1;
        }
         
        printf("%d\n", ans);
    }
    
    return 0;
}
# HDU1937 Finding Seats
# 题面
电影院有 RR 行 CC 列，用 '.' 表示空座， 'X' 表示不可选。
要求选择至少 KK 个空座位 (xi,yi)(x_i, y_i)，使得
(max⁡xi−min⁡xi)⋅(max⁡yi−min⁡yi),1⩽i⩽K(\max x_i -\min x_i)\cdot(\max y_i -\min y_i),1\leqslant i \leqslant K
最小。
# 解
二维尺取。
枚举题目所求长方形的上下界，尺取求出左右最短距离。用二维前缀和简化空位查找。
# 代码
#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 330;
int row, c, k;
char str[N];
int s[N][N];
int query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}
int main() {
     
    freopen("hdu1937.in", "r", stdin);
     
    while(true) {
         
        scanf("%d%d%d", &row, &c, &k);
        if(row == 0 and c == 0 and k == 0)
            break;
          
        for(int i=1; i<=row; ++i) {
            scanf("%s", str+1);
            int sum = 0;
            for(int j=1; j<=c; ++j) {
                sum += (str[j] == '.' ? 1 : 0);
                s[i][j] = s[i-1][j] + sum;
            }
        } 
        
        int ans = 0x7fffffff;
        for(int up = 1; up <= row; ++up) {
            for(int down = up; down <= row; ++down) {
                for(int l=1, r=1; l<=c; ++l) {
                    for(; r<=c; ++r) {
                        if(query(up, l, down, r) >= k) {
                            ans = min(ans, (down - up + 1) * (r - l + 1));
                            break; 
                        }
                    }
                }
            }
        }
          
        printf("%d\n", ans);
    }
     
    return 0;
}
# HDU5358 First One
# 题面
有一数列 a1,a2,…,ana_1, a_2, \dots, a_n，求
∑i=1n∑j=in(i+j)(⌊log⁡2∑k=ijak⌋+1)\sum_{i=1}^{n} \sum_{j=i}^{n} (i + j)(\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor + 1)
的值。特别地，log⁡20=0\log_20=0。
# 解
观察上式，对于 ⌊log⁡⌋\lfloor\log\rfloor 来说，它的一个值可对应很多个真数，考虑分块。
枚举 ⌊log⁡2∑k=ijak⌋\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor 的每一个值（1~34）。
令
v=⌊log⁡2∑k=ijak⌋v =\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor
sum=∑k=ijaksum = \sum_{k=i}^{j}a_k
则
sum∈[2v−1,2v)sum \in [2^{v-1},2^v)
用尺取求出部分和在此范围的区段 [i,j][i,j]，求出结果加入计数器。
# 代码
#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 110000;
typedef long long LL;
LL cl[40], a[N], s[N];
int T, n;
int main() {
     
    freopen("hdu5358.in", "r", stdin);
     
    cl[0] = -1, cl[1] = 1;
    for(int i=2; i<=34; ++i) cl[i] = ((cl[i-1] + 1) << 1LL) - 1;
     
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i=1; i<=n; ++i) scanf("%lld", a+i);
        for(int i=1; i<=n; ++i) s[i] = s[i-1] + a[i];
         
        LL ans = 0;
        for(LL k=1; k<=34; ++k) {
            LL l = 0, r = 0;
            for(LL i=1; i<=n; ++i) {
                for(l = max(l, i); l <= n and s[l] - s[i-1] <= cl[k-1]; ++l);
                for(r = max(l, r); r <= n and s[r] - s[i-1] <= cl[k]; ++r);
                ans += k * (i * (r-l) + (l+r-1) * (r-l) / 2);
            }
        }
        printf("%lld\n", ans);
    }
     
    return 0;
}
# HDU6103 Kirinriki
# 题面
有两字符串 A,BA,B（从 11 编号），长度均为 nn，定义
dis(A,B)=∑i=1n∣Ai−Bn−i∣dis(A,B) = \sum_{i=1}^n|A_i-B_{n-i}|
字符之差定义为其 ASCII 码的差。
对于一字符串 SS，找出它的两个不重叠连续子串，他们的 disdis 不大于 mm，求最长合法子串长度。
# 解
寻找单调性，易得
∀S′⊆S,T′⊆T:dis(S′,T′)⩽dis(S,T)\forall S' \subseteq S,T'\subseteq T:dis(S',T')\leqslant dis(S,T)
因此子串越长越好。
又∵\because ∀\forall 两个合法子串，其必关于母串的某一位置（或某两位置之间）对称，考虑枚举这一中心点，分上面的两种情况。
注意到对于每个子串，其长度越大越好，同时又有约束上界，可对称尺取。
# 代码
#include <stdio.h>
#include <string.h>
int abs(int x) {
    return x > 0 ? x : -x; 
}
int max(int a, int b) {
    return a > b ? a : b;
}
int T, n, m;
char s[22000];
int main() {
     
    freopen("hdu6103.in", "r", stdin);
     
    scanf("%d", &T);
     
    while(T--) {
        scanf("%d", &m);
        scanf("%s", s+1);
        int n = strlen(s+1), ans = 0;
          
        for(int i=1; i<=n; ++i) {
            int f = 0;
            for(int l1 = i-1, r1 = i-1, l2 = i+1, r2 = i+1; l1 > 0 and l2 <= n; --l1, ++l2) {
                for(; r1 > 0 and r2 <= n and f + abs(s[r1] - s[r2]) <= m; --r1, ++r2) f += abs(s[r1] - s[r2]);
                ans = max(ans, r2 - l2);
                f -= abs(s[l1] - s[l2]);
             }
        }
          
        for(int i=1; i<=n; ++i) {
            int f = 0;
            for(int l1 = i, r1 = i, l2 = i+1, r2 = i+1; l1 > 0 and l2 <= n; --l1, ++l2) {
                for(; r1 > 0 and r2 <= n and f + abs(s[r1] - s[r2]) <= m; --r1, ++r2) f += abs(s[r1] - s[r2]);
                ans = max(ans, r2 - l2);
                f -= abs(s[l1] - s[l2]);
            }
        }
          
        printf("%d\n", ans);
    } 
     
    return 0;
}
# POJ2739 Sum of Consecutive Prime Numbers
尺取水题。
#include <stdio.h>
#include <cmath>
using namespace std;
bool prime(int x) {
    if(x < 2) return false;
    int m = int(sqrt(x));
    
    for(int i=2; i<=m; ++i) 
        if(x % i == 0) return false;
    return true;
}
int x, p[11000];
int main() {
    
    int tot = 0;
    for(int i=1; i<=10000; ++i) {
        if(prime(i)) p[++tot] = i;
    }
    
    while(true) {
        scanf("%d", &x);
        if(x == 0) break;
        int f = 0, ans = 0;
        for(int l=1, r=1; l<=tot; ++l) {
            for(; r <= tot and f + p[r] <= x; ++r) f += p[r];
            if(f == x) ++ans;
            f -= p[l];
        }
        printf("%d\n", ans);
    }
    
    return 0;
}
# CF1198A MP3
# 题面
给出 n,In,I。
nn - 数列 a1,a2,...,ana_1,a_2,...,a_n
选定一个区间 [l,r][l,r]，并进行操作，使
vi={lvi<lvil⩽vi⩽rrvi>rv_i = \begin{cases} l&v_i<l\\ v_i&l\leqslant v_i \leqslant r\\ r&v_i>r \end{cases}
要求经过处理后，数列中不同的数的个数 ⩽2⌊8I/n⌋\leqslant 2^{\lfloor 8I/n\rfloor}，且使数列中被更改的位置的总数最小，求这个最小值。
# 解
原题面较长，需耐心看题。
可先将原数列排序并离散化，记下每种数的出现次数，用前缀和优化求和。因顺序已预先排好，直接尺取 [l,r][l,r]，使区间内的值最大化，用总数相减得出答案。
# 代码
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 440000;
 
int a[N], b[N], cnt[N], s[N], n, I, t;
 
int power(int x) {
    int ans = 1, base = 2;
    for(; x; x >>= 1) {
        if(x & 1) ans *= base;
        if(ans > t) return ans;
        base *= base;
    }
    return ans;
}
 
int main() {
    
    freopen("cf1198a.in", "r", stdin); 
    
    scanf("%d%d", &n, &I);
    for(int i=1; i<=n; ++i) scanf("%d", a+i), b[i] = a[i];
    
    if(8*I > n*((int)log2(n) + 1)) {
        printf("0\n");
        return 0;
    }
    
    sort(b+1, b+n+1);
    t = unique(b+1, b+n+1) - (b+1);
    
    int K = power(8*I/n);
    
    for(int i=1; i<=n; ++i) {
        int p = lower_bound(b+1, b+t+1, a[i]) - b;
        ++cnt[p];
    }
    
    for(int i=1; i<=t; ++i) s[i] = s[i-1] + cnt[i];
    
    int ans = 0x7fffffff;
    for(int l=1, r; l<=t; ++l) {
        r = min(l + K - 1, t);
        ans = min(ans, s[t] - (s[r] - s[l-1]));
    }
    
    printf("%d\n", ans);
    
    return 0;
}
# CF180E Cubes
# 题意简述
现有一数列 a1,a2,…,an(1⩽ai⩽m)a_1,a_2,…,a_n (1\leqslant a_i \leqslant m)（更准确地翻译的话，现有一排小方块，第 ii 个方块的颜色为 aia_i），求在最多删去 kk 个位置的数后，所能获得的最长连续子段的长度，要求该子段中所有数均相同．
# 解释
  • 可以不删数．
  • 1⩽n⩽2×1051 \leqslant n \leqslant 2 \times 10^5，1⩽m⩽1051 \leqslant m \leqslant 10^5，0⩽k<n0 \leqslant k <n．
  • 样例 #1：删去 5th5th 和 6th6th．
  • 样例 #2：删去 4th4th 和 7th7th．
  • 样例 #3：不变．
# 解答
枚举每种颜色，这样问题就可被简化为对于每种颜色，求出其修改后的最长合法子段，可用尺取法求解。
尺取法与单调队列有关，应用范围比较小，要求原问题在满足条件的情况下，长度越长，答案越好。利用双指针 l,rl,r 及队列思想，对于同一个 ll 让 rr 尽可能延伸至最远，得到一个答案区间，rr 已到达最远后将与 ll 有关的信息弹出，对于多个答案区间找出最优解。
更详细的解释请看这里
# 代码
将原数列分块，对每种颜色建立链表，枚举时直接访问。
链表的每个节点存储该颜色块的左右端点。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 220000, M = 110000;
struct node {
    int l, r, next;
} a[N];
int tmp[M], n, m, k, h[M];
int main() {
    
    freopen("cf180e.in", "r", stdin);
    
    scanf("%d%d%d", &n, &m, &k);
    
    int f = 0, tot = 0, ans = 0;
    for(int i=1, c; i<=n; ++i) {
        scanf("%d", &c);
        if(f == c) a[tot].r = i;
        else {
            a[++tot] = (node) {i, i, c, 0};
            if(h[x]) a[tmp[c]].next = tmp[c] = tot;
            else h[x] = tmp[x] = tot;
            f = c;
        }
    }
    
    for(int i=1; i<=m; ++i) {
        if(h[i] == 0) continue; // 无该颜色
        int L = h[i], R = h[i], f = 0, sum = a[h[i]].r - a[h[i]].l + 1;
        for(; L; L = a[L].next) {
            for(; a[R].next and f + a[a[R].next].l - a[R].r - 1 <= k; R = a[R].next) 
                f += a[a[R].next].l - a[R].r - 1, 
                sum += a[a[R].next].r - a[a[R].next].l + 1;    
            ans = max(ans, sum); // 统计
            sum -= a[L].r - a[L].l + 1; // 弹出
            f -= a[a[L].next].l - a[L].r - 1;
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}
# CF939E Maximize!
# 题面
对于一个只包含正整数的 multiset SS，你需要支持以下 22 种操作：
  • 11
    • 找出 SS 的一个子集 ss，使 max(s)−mean(s)max(s)-mean(s) 最大，并输出这个最大值。保留十位小数。
  • 22 xx
    • 加入一个新数 xx 到 SS 中，保证加入的数是递增的。
# 解
思维题。
maxmax 越大越好，meanmean 越小越好。
结论一：子集 ss 中必包含 max⁡S\max S。
结论二：∀x∈S,x∉s,mean(s)>x:mean(s)<mean(s∪{x})\forall x \in S, x\notin s,mean(s) > x:mean(s) < mean(s\cup\{x\})​ 。
证明略。
# 代码
略丑。
为防止 WA，特判了较小的情况，维护的也略微麻烦一点。
#include <stdio.h>
const int N = 550000;
typedef double LF;
int Q, s[N];
int main() {
    
    freopen("cf939e.in", "r", stdin);
    
    int tot = 0, f = 0;
    LF sum = 0, lastans = 0, lasttype = 0;
    
    scanf("%d", &Q);
    
    while(Q--) {
    
        int type;
        scanf("%d", &type);
        
        if(type == 1) {
            scanf("%d", &s[++tot]);
            lasttype = type;
        }
        else {
            
            if(lasttype == 2) {
                printf("%.10lf\n", lastans);
                continue;
            }
            
            if(tot == 1) {
                printf("%.10lf\n", (LF)0);
                lastans = 0;
                lasttype = 2;
                continue;
            }
            
            if(tot == 2) {
                lastans = s[2] - (s[1] + s[2]) / 2.0;
                printf("%.10lf\n", lastans);
                lasttype = 2;
                sum = s[1], f = 1;
                continue;
            }
            
            for(int i=f+1; i<tot; ++i) {
                if((LF)(sum + s[tot]) / i > (LF)s[i]) f = i, sum += s[i];
                else break; 
            }
            
            lastans = s[tot] - (sum + s[tot]) / (f+1);
            printf("%.10lf\n", lastans);
            
            lasttype = type;
        }
    }
    
    return 0;
}
   
 更新于