尺取法

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

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

HDU5178 Pairs

题面

有 $n$ 个值 $x_1, x_2, \dots,x_n$，求使得 $|x_b-x_a|\leqslant k,a<b$ 的数对 $(a,b)$ 的个数．

解

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

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

代码

#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

题面

给出 $n$ 个已签到的天数区间，$m$ 张补签卡，求可获得的最大连续签到时长。

解

尺取模板。

天数区间可重叠，须进行合并。

需要注意的是，当已确定最长合法区间 $[l,r]$ 后（即下一个区间与 $r$ 的距离大于剩余的补签卡数量，连不上），应把剩余补签卡全部应用到 $r$ 之后的天数上得到更优解。

代码

边界条件较多。

$R$ 为已加入队列的最后一个区间，判断的是区间 $R+1$ 的合法性。

特判第一个区间，开始时 $sum$ 直接加上第一个已签到区间的长，使用 $0$ 张补签卡。

#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

题面

电影院有 $R$ 行 $C$ 列，用 '.' 表示空座，'X' 表示不可选。

要求选择至少 $K$ 个空座位 $(x_i, y_i)$，使得
$$
(\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

题面

有一数列 $a_1, a_2, \dots, a_n$，求
$$
\sum_{i=1}^{n} \sum_{j=i}^{n} (i + j)(\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor + 1)
$$
的值。特别地，$\log_20=0$。

解

观察上式，对于 $\lfloor\log\rfloor$ 来说，它的一个值可对应很多个真数，考虑分块。

枚举 $\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor$ 的每一个值（1~34）。

令
$$
v =\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor
$$

$$
sum = \sum_{k=i}^{j}a_k
$$

则
$$
sum \in [2^{v-1},2^v)
$$
用尺取求出部分和在此范围的区段 $[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,B$（从 $1$ 编号），长度均为 $n$，定义
$$
dis(A,B) = \sum_{i=1}^n|A_i-B_{n-i}|
$$
字符之差定义为其 ASCII 码的差。

对于一字符串 $S$，找出它的两个不重叠连续子串，他们的 $dis$ 不大于 $m$，求最长合法子串长度。

解

寻找单调性，易得
$$
\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,I$。

$n$ - 数列 $a_1,a_2,…,a_n$

选定一个区间 $[l,r]$，并进行操作，使
$$
v_i =
\begin{cases}
l&v_i<l\\
v_i&l\leqslant v_i \leqslant r\\
r&v_i>r
\end{cases}
$$
要求经过处理后，数列中不同的数的个数 $\leqslant 2^{\lfloor 8I/n\rfloor}$，且使数列中被更改的位置的总数最小，求这个最小值。

解

原题面较长，需耐心看题。

可先将原数列排序并离散化，记下每种数的出现次数，用前缀和优化求和。因顺序已预先排好，直接尺取 $[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

题意简述

现有一数列 $a_1,a_2,…,a_n (1\leqslant a_i \leqslant m)$（更准确地翻译的话，现有一排小方块，第 $i$ 个方块的颜色为 $a_i$），求在最多删去 $k$ 个位置的数后，所能获得的最长连续子段的长度，要求该子段中所有数均相同．

解释

• 可以不删数．
• $1 \leqslant n \leqslant 2 \times 10^5$，$1 \leqslant m \leqslant 10^5$，$0 \leqslant k <n$．
• 样例#1：删去 $5th$ 和 $6th$．
• 样例#2：删去 $4th$ 和 $7th$．
• 样例#3：不变．

解答

枚举每种颜色，这样问题就可被简化为对于每种颜色，求出其修改后的最长合法子段，可用尺取法求解。

尺取法与单调队列有关，应用范围比较小，要求原问题在满足条件的情况下，长度越长，答案越好。利用双指针 $l,r$ 及队列思想，对于同一个 $l$ 让 $r$ 尽可能延伸至最远，得到一个答案区间，$r$ 已到达最远后将与 $l$ 有关的信息弹出，对于多个答案区间找出最优解。

更详细的解释请看这里

代码

将原数列分块，对每种颜色建立链表，枚举时直接访问。

链表的每个节点存储该颜色块的左右端点。

#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 $S$，你需要支持以下 $2$ 种操作：

• $1$
  • 找出 $S$ 的一个子集 $s$，使 $max(s)-mean(s)$ 最大，并输出这个最大值。保留十位小数。
• $2$ $x$
  • 加入一个新数 $x$ 到 $S$ 中，保证加入的数是递增的。

解

思维题。

$max$ 越大越好，$mean$ 越小越好。

结论一：子集 $s$ 中必包含 $\max S$。

结论二：$\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;
}