# 尺取法

与单调队列相关

要求在满足条件的情况下,长度越长,答案越好(下简称具有单调性).

利用双指针 l,rl,r 及队列思想,对于同一个 llrr 尽可能延伸至最远,得到一个答案区间,rr 已到达最远后将与 ll 有关的信息弹出,对于多个答案区间找出最优解.

# HDU5178 Pairs

# 题面

nn 个值 x1,x2,,xnx_1, x_2, \dots,x_n,求使得 xbxak,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

# 题面

电影院有 RRCC 列,用 '.' 表示空座, 'X' 表示不可选。

要求选择至少 KK 个空座位 (xi,yi)(x_i, y_i),使得

(maxximinxi)(maxyiminyi),1iK(\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=1nj=in(i+j)(log2k=ijak+1)\sum_{i=1}^{n} \sum_{j=i}^{n} (i + j)(\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor + 1)

的值。特别地,log20=0\log_20=0

#

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

枚举 log2k=ijak\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor 的每一个值(1~34)。

v=log2k=ijakv =\lfloor \log_2 \sum_{k=i}^{j} a_k \rfloor

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

sum[2v1,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=1nAiBnidis(A,B) = \sum_{i=1}^n|A_i-B_{n-i}|

字符之差定义为其 ASCII 码的差。

对于一字符串 SS,找出它的两个不重叠连续子串,他们的 disdis 不大于 mm,求最长合法子串长度。

#

寻找单调性,易得

SS,TT: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<lvilvirrvi>rv_i = \begin{cases} l&v_i<l\\ v_i&l\leqslant v_i \leqslant r\\ r&v_i>r \end{cases}

要求经过处理后,数列中不同的数的个数 28I/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(1aim)a_1,a_2,…,a_n (1\leqslant a_i \leqslant m)(更准确地翻译的话,现有一排小方块,第 ii 个方块的颜色为 aia_i),求在最多删去 kk 个位置的数后,所能获得的最长连续子段的长度,要求该子段中所有数均相同.

# 解释

  • 可以不删数.
  • 1n2×1051 \leqslant n \leqslant 2 \times 10^51m1051 \leqslant m \leqslant 10^50k<n0 \leqslant k <n
  • 样例 #1:删去 5th5th6th6th
  • 样例 #2:删去 4th4th7th7th
  • 样例 #3:不变.

# 解答

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

尺取法与单调队列有关,应用范围比较小,要求原问题在满足条件的情况下,长度越长,答案越好。利用双指针 l,rl,r 及队列思想,对于同一个 llrr 尽可能延伸至最远,得到一个答案区间,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
    • 加入一个新数 xxSS 中,保证加入的数是递增的。

#

思维题。

maxmax 越大越好,meanmean 越小越好。

结论一:子集 ss 中必包含 maxS\max S

结论二:xS,xs,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;
}
更新于