P2216-[HAOI2007]理想的正方形

不念不忘少年蓝@ 2023-06-01 08:53 5阅读 0赞

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 typedef double db;
     5 #define INF 0x3f3f3f3f
     6 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     7 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 int a,b,n;
    24 int Log[1003];
    25 int maxx[1003][1003][11];
    26 int minn[1003][1003][11];
    27 void searchLog()
    28 {
    29     Log[0] = -1;
    30     _for(i,1,max(a,b)+1)
    31         Log[i] = Log[i/2]+1;
    32 }
    33 int query(int x,int y)
    34 {
    35     int xl = x+n-1,yl = y+n-1;
    36     int s = Log[n];
    37     int MAX = max(maxx[x][y][s],max(maxx[xl-(1<<s)+1][yl-(1<<s)+1][s],
    38     max(maxx[xl-(1<<s)+1][y][s],maxx[x][yl-(1<<s)+1][s])));
    39     
    40     int MIN = min(minn[x][y][s],min(minn[xl-(1<<s)+1][yl-(1<<s)+1][s],
    41     min(minn[xl-(1<<s)+1][y][s],minn[x][yl-(1<<s)+1][s]))); 
    42     return MAX-MIN;
    43 }
    44 int main()
    45 {
    46     a = read(),b = read(), n = read();
    47     searchLog();
    48     _for(i,1,a+1)
    49         _for(j,1,b+1)
    50             minn[i][j][0] = maxx[i][j][0] = read();
    51     
    52     _for(r,1,Log[n]+1)
    53         for(int i = 1;i + (1<<r) - 1 <= a;i ++)
    54             for(int j = 1;j + (1<<r) -1 <= b;j ++)
    55             {
    56                 maxx[i][j][r] = max(maxx[i][j][r-1],max(maxx[i][j+(1<<r-1)][r-1],
    57                 max(maxx[i+(1<<r-1)][j][r-1],maxx[i+(1<<r-1)][j+(1<<r-1)][r-1])));
    58                 
    59                 minn[i][j][r] = min(minn[i][j][r-1],min(minn[i][j+(1<<r-1)][r-1],
    60                 min(minn[i+(1<<r-1)][j][r-1],minn[i+(1<<r-1)][j+(1<<r-1)][r-1])));
    61             }
    62     
    63     int ans = INT_MAX;
    64     _for(i,1,a-n+2)
    65         _for(j,1,b-n+2)
    66             ans = min(ans,query(i,j));
    67     write(ans);
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/Asurudo/p/11446892.html