[HAOI2007] 理想的正方形

发表于 | 分类于 >
字数统计 : 1,037   |   阅读时长 ≈ 6 mins.

题目

链接

[HAOI2007]理想的正方形

题意简述

有一个 $n * m \ (n, \ m <= 1000)$ 的整数组成的矩阵。

找出一个 $k * k \ (k <= 100)$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

思路

暴力

首先考虑暴力，也就是暴力枚举起点，暴力求最大值和最小值。
时间复杂度： $O(n^{4})$ 。

二维RMQ

看到要求最大值与最小值，就想起RMQ。
常规二维RMQ空间复杂度太大，需要 $(n^{2}2logk)$ 的空间， 开不下啊2333。
但是这道题很特殊，它的查询的是正方形，因此并不需要二维倍增。
所以就砍下了一维。
下面会给出常规二维RMQ与特殊二维RMQ。
空间复杂度： $O(n^{2}logk)$ 。
时间复杂度： $O(n^{2}logk)$ 。

DP

据说可以用单调队列维护。
我太蒻了，并不会。。。。。

代码

二维RMQ

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
const int kmax_num = 1e3 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n, m, k;
int rmq_max[kmax_num][kmax_num][11][11], rmq_min[kmax_num][kmax_num][11][11];

inline void Init()	{
    for(REG int i = 1; (1 << i) <= n; ++i)
        for(REG int h = 1; (1 << h) <= m; ++h)	{
            if(!i && !h)	continue;
            else	{
                for(REG int row = 1; row + (1 << i) - 1 <= n; ++row)
                    for(REG int col = 1; col + (1 << h) - 1 <= m; ++col)
                if(i)	rmq_max[row][col][i][h] = std::max(rmq_max[row][col][i - 1][h], rmq_max[row + (1 << (i - 1))][col][i - 1][h]),
                        rmq_min[row][col][i][h] = std::min(rmq_min[row][col][i - 1][h], rmq_min[row + (1 << (i - 1))][col][i - 1][h]);
                else	rmq_max[row][col][i][h] = std::max(rmq_max[row][col][i][h - 1], rmq_max[row][col + (1 << (h - 1))][i][h - 1]),
                        rmq_min[row][col][i][h] = std::min(rmq_min[row][col][i][h - 1], rmq_min[row][col + (1 << (h - 1))][i][h - 1]);
            }
        }
    return ;
}

inline int Query(REG int ax, REG int ay, REG int bx, REG int by)	{
    REG int t1 = (int) log2(bx - ax + 1);
    REG int t2 = (int) log2(by - ay + 1);
    REG int m1 = rmq_max[ax][ay][t1][t2];
    REG int m2 = rmq_max[bx - (1 << t1) + 1][ay][t1][t2];
    REG int m3 = rmq_max[ax][by - (1 << t2) + 1][t1][t2];
    REG int m4 = rmq_max[bx - (1 << t1) + 1][by - (1 << t2) + 1][t1][t2];

    REG int m5 = rmq_min[ax][ay][t1][t2];
    REG int m6 = rmq_min[bx - (1 << t1) + 1][ay][t1][t2];
    REG int m7 = rmq_min[ax][by - (1 << t2) + 1][t1][t2];
    REG int m8 = rmq_min[bx - (1 << t1) + 1][by - (1 << t2) + 1][t1][t2];

    return std::max(std::max(m1, m2), std::max(m3, m4)) - std::min(std::min(m5, m6), std::min(m7, m8));
}

二维RMQ-UDP

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e3 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n, m, k;
int rmq_max[kmax_num][kmax_num][11], rmq_min[kmax_num][kmax_num][11];

inline void Init()	{
	for(REG int i = 1; (1 << i) <= k; ++i)	{
		for(REG int row = 1; row + (1 << i) - 1 <= n; ++row)
			for(REG int col = 1; col + (1 << i) - 1 <= m; ++col)
				rmq_max[row][col][i] = std::max(std::max(rmq_max[row][col][i - 1], rmq_max[row + (1 << (i - 1))][col][i - 1]),
												std::max(rmq_max[row][col + (1 << (i - 1))][i - 1], rmq_max[row + (1 << (i - 1))][col + (1 << (i - 1))][i - 1])),
				rmq_min[row][col][i] = std::min(std::min(rmq_min[row][col][i - 1], rmq_min[row + (1 << (i - 1))][col][i - 1]),
												std::min(rmq_min[row][col + (1 << (i - 1))][i - 1], rmq_min[row + (1 << (i - 1))][col + (1 << (i - 1))][i - 1]));
	}
	return ;
}

inline int Query(REG int ax, REG int ay, REG int bx, REG int by)	{
	REG int t1 = (int) log2(bx - ax + 1);
//	REG int t1 = (int) log2(k + 1);

	REG int m1 = rmq_max[ax][ay][t1];
	REG int m2 = rmq_max[bx - (1 << t1) + 1][ay][t1];
	REG int m3 = rmq_max[ax][by - (1 << t1) + 1][t1];
	REG int m4 = rmq_max[bx - (1 << t1) + 1][by - (1 << t1) + 1][t1];

	REG int m5 = rmq_min[ax][ay][t1];
	REG int m6 = rmq_min[bx - (1 << t1) + 1][ay][t1];
	REG int m7 = rmq_min[ax][by - (1 << t1) + 1][t1];
	REG int m8 = rmq_min[bx - (1 << t1) + 1][by - (1 << t1) + 1][t1];

	return std::max(std::max(m1, m2), std::max(m3, m4)) - std::min(std::min(m5, m6), std::min(m7, m8));
}

int main() {
	std::cin >> n >> m >> k;
	For(i,1,n)	For(h,1,m)	std::cin >> rmq_max[i][h][0], rmq_min[i][h][0] = rmq_max[i][h][0];
	Init();

	REG int ans = 0x7fffffff;
	for(REG int i = 1; i + k - 1 <= n; ++i)
		for(REG int h = 1; h + k - 1 <= m; ++h)
			ans = std::min(ans, Query(i, h, i + k - 1, h + k - 1));
	printf("%d\n", ans);
	return 0;
}

杂项

  • 这里的二维 $RMQ$ 要是 $(n \ == \ 0 \ || \ m \ == \ 0)$ 就是一个一维 $RMQ$ 。