BZOJ 1047 [HAOI2007]理想的正方形:二维ST表 or 二维单调队列【统计正方形区域】

题目

题目描述

有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为3个整数,分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式

仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

说明/提示

问题规模

(1)矩阵中的所有数都不超过1,000,000,000

(2)20%的数据2<=a,b<=100,n<=a,n<=b,n<=10

(3)100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100

题解

首先想到 O(a^2n^2) 的暴力,可惜过不了

然后想到能不能优化一下统计最值的过程,于是有了二维st表 O(a^2\log^2a \approx 10^8) 的不TLE但是MLE的做法:对于每一行建一个st表,复杂度 O(a^2\log a);然后建 a\log a 个列st表,对应行st表上的每一个值,复杂度 O(a^2\log^2a);最后 O(a^2) 统计答案(纯属口胡,没有代码)

然后就有了特殊一点的针对正方形的二维st表做法(同样很蠢,但是能过):建立二维st表维护最值:mx[i][j][k]mn[i][j][k],表示左上角为 (i,j),边长为 2^k 的正方形中的最大最小值,初始化 O(a^2\log a),统计答案 O(a^2)

好像还有高级一点的单调队列做法,回头再补吧,先睡觉了qwq

UPD:(二维单调队列做法)

令:
rx[i][j] = max\lbrace w[i][k]\rbrace_{k=j-n+1}^j\\ rn[i][j] = min\lbrace w[i][k]\rbrace_{k=j-n+1}^j\\ cx[i][j] = max\lbrace rx[k][j]\rbrace_{k=i-n+1}^i\\ cn[i][j] = min\lbrace rn[k][j]\rbrace_{k=i-n+1}^i\\
所谓二维单调队列,就是分别对行和列做单调队列

由于这里既要求出最小值,还要求出最大值,所以总共要做四次单调队列

对于每一行,对 w 的值做两次单调队列,求出 rxrn 数组

对于每一列,对 rx(或 rn)的值做两次单调队列,求出 cxcn 数组

具体细节见代码

Code

ST表做法:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_A 1005
#define MAX_L 15
#define INF 1000000000

using namespace std;

int a, b, n, ans = INF;
int lg[MAX_A];
int w[MAX_A][MAX_A];
int mx[MAX_A][MAX_A][MAX_L];
int mn[MAX_A][MAX_A][MAX_L];

inline int max(int a, int b, int c, int d) {
    return max(a, max(b, max(c, d)));
}

inline int min(int a, int b, int c, int d) {
    return min(a, min(b, min(c, d)));
}

void init() {
    lg[0] = -1;
    for (int i = 1; i <= min(a, b); i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            mx[i][j][0] = mn[i][j][0] = w[i][j];
        }
    }
    for (int k = 0; k < lg[min(a, b)]; k++) {
        for (int i = 1; i + (1 << k) - 1 <= a; i++) {
            for (int j = 1; j + (1 << k) - 1 <= b; j++) {
                mx[i][j][k + 1] = max(
                    mx[i][j][k],
                    mx[i + (1 << k)][j][k],
                    mx[i][j + (1 << k)][k],
                    mx[i + (1 << k)][j + (1 << k)][k]);
                mn[i][j][k + 1] = min(
                    mn[i][j][k],
                    mn[i + (1 << k)][j][k],
                    mn[i][j + (1 << k)][k],
                    mn[i + (1 << k)][j + (1 << k)][k]);
            }
        }
    }
}

inline int getmx(int x, int y, int n) {
    int t = lg[n];
    return max(
        mx[x][y][t],
        mx[x + n - (1 << t)][y][t],
        mx[x][y + n - (1 << t)][t],
        mx[x + n - (1 << t)][y + n - (1 << t)][t]);
}

inline int getmn(int x, int y, int n) {
    int t = lg[n];
    return min(
        mn[x][y][t],
        mn[x + n - (1 << t)][y][t],
        mn[x][y + n - (1 << t)][t],
        mn[x + n - (1 << t)][y + n - (1 << t)][t]);
}

inline int getdiff(int x, int y, int n) {
    return getmx(x, y, n) - getmn(x, y, n);
}

int main() {
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    init();
    for (int i = 1; i + n - 1 <= a; i++) {
        for (int j = 1; j + n - 1 <= b; j++) {
            ans = min(ans, getdiff(i, j, n));
        }
    }
    printf("%d\n", ans);
}

单调队列做法:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_A 1005
#define INF 1000000000

using namespace std;

int a, b, n, ans = INF;
int q[MAX_A];
int w[MAX_A][MAX_A];
int rx[MAX_A][MAX_A];
int rn[MAX_A][MAX_A];
int cx[MAX_A][MAX_A];
int cn[MAX_A][MAX_A];

int main() {
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    for (int i = 1; i <= a; i++) {
        int l = 1, r = 1;
        for (int j = 1; j <= b; j++) {
            while (l < r && w[i][j] >= w[i][q[r - 1]]) {
                r--;
            }
            q[r++] = j;
            if (q[l] == j - n) {
                l++;
            }
            rx[i][j] = w[i][q[l]];
        }
        l = 1, r = 1;
        for (int j = 1; j <= b; j++) {
            while (l < r && w[i][j] <= w[i][q[r - 1]]) {
                r--;
            }
            q[r++] = j;
            if (q[l] == j - n) {
                l++;
            }
            rn[i][j] = w[i][q[l]];
        }
    }
    for (int j = n; j <= b; j++) {
        int l = 1, r = 1;
        for (int i = 1; i <= a; i++) {
            while (l < r && rx[i][j] >= rx[q[r - 1]][j]) {
                r--;
            }
            q[r++] = i;
            if (q[l] == i - n) {
                l++;
            }
            cx[i][j] = rx[q[l]][j];
        }
        l = 1, r = 1;
        for (int i = 1; i <= a; i++) {
            while (l < r && rn[i][j] <= rn[q[r - 1]][j]) {
                r--;
            }
            q[r++] = i;
            if (q[l] == i - n) {
                l++;
            }
            cn[i][j] = rn[q[l]][j];
        }
    }
    for (int i = n; i <= a; i++) {
        for (int j = n; j <= b; j++) {
            ans = min(ans, cx[i][j] - cn[i][j]);
        }
    }
    printf("%d\n", ans);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注