本文共 1889 字，大约阅读时间需要 6 分钟。

[HAOI2007]理想的正方形 解题报告

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。

input

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

output

1

思路：

这个题有一种很妙的处理方法。

先上代码：

for (int k = 2; k <= K; k++)        for (int i = 0; i+1 < a; i++)            for (int j = 0; j+1 < b; j++) {
                    maxv[i][j] = max(grid[i][j], max(maxv[i+1][j+1], max(maxv[i+1][j], maxv[i][j+1])));                minv[i][j] = min(grid[i][j], min(minv[i+1][j+1], min(minv[i+1][j], minv[i][j+1])));            }    int ans = INF;    for (int i = 0; i <= a-n; i++)        for (int j = 0; j <= b-n; j++)            ans = min(ans, maxv[i][j]-minv[i][j]);

maxv,minv分别代表这个以i,j为左上角的长度为k的矩阵中最大于最小值分别是多少，grid代表这个数是多少，而循环最外面的k就是非常关键的一步啦。

每次循环可以将k的范围增加1.可以发现,每次k增大的时候,都会与k-1的值有关,所以k要放外面。这样处理，刚好可以将每个子矩阵的最大与最小值求出来。这是一种很妙的处理方法。至少在矩阵中。。

然而这样会T飞!!!

冷静分析一波

会发现，这样的复杂度太高了。而我们的目的是求矩阵的最大值和最小值，所以可以用一波ST表的思想 设MIn[i][j][k],Max[i][j][k]代表以I,j为左上角，大小为2^k的矩阵中的最小值与最大值。

while((1<<(t+1) <=k)) t++;//求出2的k次方的指数界限for(int k=0;k < t;k++)        for(int i=0;i+(1<
   
    
     < m;j++)            {
                    Max[i][j] = max(Max[i][j],max(Max[i+(1<
     
      <
     
    
   

查询有点妙

inline int query(int x,int y){
        int nmin=INF,nmax=-INF;    nmax=max(Max[x][y],max(Max[k+x-(1<
   
    <
   

因为(1<<t) <= 2^k

所以x-(1<<t)+k是为了保证查询范围可以被完全覆盖。 可以自己举一个K为奇数的例子模拟一下

完整代码

#include
   
    using namespace std;#define maxn 1005#define maxm 10005#define INF 1000000005int n,m,k,t;int a[maxn][maxn],Min[maxn][maxn],Max[maxn][maxn];int ans;inline int query(int x,int y){
        int nmin=INF,nmax=-INF;    nmax=max(Max[x][y],max(Max[k+x-(1<
    
     <
     
      < t;k++)        for(int i=0;i+(1<
      
       
        < m;j++)            {
                    Max[i][j] = max(Max[i][j],max(Max[i+(1<
        
         <
        
       
      
     
    
   

转载地址：http://zyuci.baihongyu.com/