发表更新OI / 题解

「HAOI 2007」理想的正方形

给定 n×mn\times m 整数矩阵，选取 k×kk\times k 正方形区域，使其中「最大值减最小值」最小

首先是一个很数据结构的做法，维护一个二维 ST 表即可

其次是一个有趣的做法

令 ci,j=max⁡j−k<l≤jai,lc_{i,j} = \max_{j - k < l \le j} a_{i, l} 处理出长度为 kk 的行最大

然后在 ci,jc_{i,j} 的基础上求列最大

形式化地讲 di,j=max⁡i−k<l≤icl,jd_{i,j} = \max_{i-k<l\le i} c_{l, j}

然后 di,jd_{i,j} 就是右下角在 (i,j)(i,j) 的 k×kk\times k 正方形的最大值，即 max⁡i−k<p≤i,j−l<q≤jap,q\max_{i-k<p\le i, j-l<q\le j}a_{p, q}

最小值同理

维护定长区间最值可以用单调队列

deque 真的好慢啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse")
// #pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-ftree-pre")
// #pragma GCC optimize("-ftree-vrp")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("-falign-jumps")
// #pragma GCC optimize("-falign-loops")
// #pragma GCC optimize("-falign-labels")
// #pragma GCC optimize("-fdevirtualize")
// #pragma GCC optimize("-fcaller-saves")
// #pragma GCC optimize("-fcrossjumping")
// #pragma GCC optimize("-fthread-jumps")
// #pragma GCC optimize("-funroll-loops")
// #pragma GCC optimize("-fwhole-program")
// #pragma GCC optimize("-freorder-blocks")
// #pragma GCC optimize("-fschedule-insns")
// #pragma GCC optimize("inline-functions")
// #pragma GCC optimize("-ftree-tail-merge")
// #pragma GCC optimize("-fschedule-insns2")
// #pragma GCC optimize("-fstrict-aliasing")
// #pragma GCC optimize("-fstrict-overflow")
// #pragma GCC optimize("-falign-functions")
// #pragma GCC optimize("-fcse-skip-blocks")
// #pragma GCC optimize("-fcse-follow-jumps")
// #pragma GCC optimize("-fsched-interblock")
// #pragma GCC optimize("-fpartial-inlining")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("-freorder-functions")
// #pragma GCC optimize("-findirect-inlining")
// #pragma GCC optimize("-fhoist-adjacent-loads")
// #pragma GCC optimize("-frerun-cse-after-loop")
// #pragma GCC optimize("inline-small-functions")
// #pragma GCC optimize("-finline-small-functions")
// #pragma GCC optimize("-ftree-switch-conversion")
// #pragma GCC optimize("-foptimize-sibling-calls")
// #pragma GCC optimize("-fexpensive-optimizations")
// #pragma GCC optimize("-funsafe-loop-optimizations")
// #pragma GCC optimize("inline-functions-called-once")
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

// #define DEBUG 1  //调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    inline char gc() {
#if DEBUG  //调试，可显示字符
        return getchar();
#endif
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? -1 : *p1++;
    }
    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
    template <class T>
    inline void read(T &x) {
        register double tmp = 1;
        register bool sign = 0;
        x = 0;
        register char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }
    inline void read(char *s) {
        register char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }
    inline void read(char &c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }
    inline void push(const char &c) {
#if DEBUG  //调试，可显示字符
        putchar(c);
#else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }
    template <class T>
    inline void write(T x) {
        if (x < 0) x = -x, push('-');  // 负数输出
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }
    inline void write(const char *s) {
        while (*s != '\0') push(*(s++));
    }
    template <class T>
    inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;

int a[1010][1010], c1[1010][1010], c2[1010][1010], d1[1010][1010], d2[1010][1010];

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    int n, m, k;
    io.read(n), io.read(m), io.read(k);
    std::deque<pii> mx, mn;
    // first->time, second->value
    rep(i, 1, n) {
        mx.clear(), mn.clear();
        rep(j, 1, m) {
            io.read(a[i][j]);
            while (mx.size() && mx.front().first <= j - k) mx.pop_front();
            while (mn.size() && mn.front().first <= j - k) mn.pop_front();
            while (mx.size() && mx.back().second <= a[i][j]) mx.pop_back();
            while (mn.size() && mn.back().second >= a[i][j]) mn.pop_back();
            mx.push_back({j, a[i][j]});
            mn.push_back({j, a[i][j]});
            c1[i][j] = mx.front().second;
            c2[i][j] = mn.front().second;
        }
    }
    rep(j, 1, m) {
        mx.clear(), mn.clear();
        rep(i, 1, n) {
            while (mx.size() && mx.front().first <= i - k) mx.pop_front();
            while (mn.size() && mn.front().first <= i - k) mn.pop_front();
            while (mx.size() && mx.back().second <= c1[i][j]) mx.pop_back();
            while (mn.size() && mn.back().second >= c2[i][j]) mn.pop_back();
            mx.push_back({i, c1[i][j]});
            mn.push_back({i, c2[i][j]});
            d1[i][j] = mx.front().second;
            d2[i][j] = mn.front().second;
        }
    }
    int ans = 2147483647;
    rep(i, k, n) rep(j, k, m) ans = std::min(ans, d1[i][j] - d2[i][j]);
    io.write(ans);
    return 0;
}

「HAOI 2007」理想的正方形

https://gesrua.xyz/archives/题解/省选/理想的正方形

作者

Gesrua

发布于

2019-08-16

更新于

2020-11-21

许可协议

#

分类

×