[BZOJ1047][HAOI2007]理想的正方形(单调队列,动态规划) 题面 BZOJ 洛谷 题解 直接一个单调队列维护一下没给点和它前面的\(n\)个位置的最大值,再用一次单调队列维护连续\(n\)列的,每个数和前面\(n\)个数的最大值,最小值同理,就做完了. #include<iostream> #include<cstdio> using namespace std; #define MAX 1010 inline int read() { int x=0;bool t

1047: [HAOI2007]理想的正方形 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2857  Solved: 1560[Submit][Status][Discuss] Description 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. Input 第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间

1047: [HAOI2007]理想的正方形 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1402  Solved: 738[Submit][Status] Description 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. Input 第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. Ou

题目:[HAOI2007]理想的正方形 描述: [问题描述] 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. [输入]: 第一行为3个整数,分别表示a,b,n的值 第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. [输出]: 仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值. [输入样例] 5 4 2 1 2 5 6 0 17 16 0 16 17

题目链接 1047: [HAOI2007]理想的正方形 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2369  Solved: 1266[Submit][Status][Discuss] Description 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. Input 第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相

单调队列..先对每一行扫一次维护以每个点(x, y)为结尾的长度为n的最大最小值.然后再对每一列扫一次, 在之前的基础上维护(x, y)为结尾的长度为n的最大最小值. 时间复杂度O(ab) (话说还是deque2048ms快..list3572ms慢死了) #include<bits/stdc++.h> using namespace std; const int maxn = 1009; int X[maxn][maxn], R, C, N; int MN[maxn][maxn], MX[m

http://www.lydsy.com/JudgeOnline/problem.php?id=1047 先用单调队列求出每横着n个最大值 再在里面用单调队列求出每竖着n个的最大值 这样一个位置就代表了一个n*n矩阵的最大值 同理求出最小值 #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 1001 int num[N][N]; int mx1[N

[BZOJ1047][HAOI2007]理想的正方形 题面 bzoj 洛谷 题解 二维\(st\)表,代码是以前的 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> #include<

[HAOI2007]理想的正方形 题目描述 有一个\(a*b\)的整数组成的矩阵,现请你从中找出一个\(n*n\)的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入输出格式 输入格式: 第一行为3个整数,分别表示\(a,b,n\)的值 第二行至第\(a+1\)行每行为\(b\)个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. 输出格式: 仅一个整数,为\(a*b\)矩阵中所有\(n*n\)正方形区域中的最大整数和最小整数的差值"的最小值. 输入输出样例 输入样例

[HAOI2007] 理想的正方形 思路: 正解多个单调队列: 但是我用树套树水了过去: 来,上代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct ReType { int mi,ma; }; struct TreeNodeType { int l,r,lc,rc,ma,mi,mid; };

P2216 [HAOI2007]理想的正方形 题目描述 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入输出格式 输入格式: 第一行为3个整数,分别表示a,b,n的值 第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. 输出格式: 仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值. 输入输出样例 输入样例#1: 5 4 2 1 2 5 6 0 1

[Luogu 2216] [HAOI2007]理想的正方形 题目描述 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入输出格式 输入格式: 第一行为3个整数,分别表示a,b,n的值 第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. 输出格式: 仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值. 输入输出样例 输入样例#1: 5 4 2 1 2

题目链接:P2216 [HAOI2007]理想的正方形 题目描述 有一个 \(a\times b\)的整数组成的矩阵,现请你从中找出一个 \(n\times n\)的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入格式 第一行为3个整数,分别表示a,b,n的值 第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. 输出格式 仅一个整数,为 \(a\times b\)矩阵中所有" \(n\times n\)正方形区域中的最大整数和最小整数的差

[HAOI2007]理想的正方形 题目描述 有一个 \(a \times b\) 的整数组成的矩阵,现请你从中找出一个 \(n \times n\) 的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入格式 第一行为 \(3\) 个整数,分别表示 \(a,b,n\) 的值. 第二行至第 \(a+1\) 行每行为 \(b\) 个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔. 输出格式 仅一个整数,为 \(a \times b\) 矩阵中所有" \(n \times

理想的正方形 bzoj-1047 HAOI-2007 题目大意:有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 注释:$2\le a,b,n\le 10^3$,$n\le min(a,b)$. 想法:我的思路简直要死.通常的,我们优化暴力来完成对题目的求解.首先,想暴力.漂亮的暴力没想到,倒是想到一个a*b*n*n的,就是枚举每一个点,如果这个点可以作为n*n正方形的左上角,我就暴力枚举这个正方形的所有点.时间复杂度:O((a-n

理想的正方形 [题目描述] 一个a*b的矩阵,从中取一个n*n的子矩阵,使所选矩阵中的最大数与最小数的差最小. 思路: 二维的滑动窗口 对于每行:用一个单调队列维护,算出每个长度为n的区间的最大值和最小值,分别存在两个数组fmin和fmax中,fmax[i][j]表示第i行区间[j,j+n-1]的最大值. 对于每列:用一个单调队列维护,算出fmax和fmin数组中纵列每个长度为n的区间的最大值和最小值,分别存在两个数组ffmin和ffmax中, ffmax[i][j]表示以(i,j)为左上端点的

题目就是要求在n*m的矩形中找出一个k*k的正方形(理想正方形),使得这个正方形内最值之差最小(就是要维护最大值和最小值),显然我们可以用单调队列维护. 但是二维平面上单调队列怎么用? 我们先对行处理,将其压缩为一个(n-k+1)*m的矩形:再对列进行处理,最终压缩为一个(n-k+1)*(m-k+1)的矩形,枚举最大与最小之差,更新答案即可. 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e3+1; 4 int

Description 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小.Input 第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔.Output 仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值.Sample Input5 4 21 2 5 60 17 16 016 17 2 12 10 2 11 2 2 2S

题目链接:BZOJ - 1047 题目分析 使用单调队列在 O(n^2) 的时间内求出每个 n * n 正方形的最大值,最小值.然后就可以直接统计答案了. 横向有 a 个单调队列(代码中是 Q[1] 到 Q[a] ),维护每行当前枚举区间的单调队列. 纵向一个单调队列(代码中是 Q[0] ),求出当前枚举区间的每行的单调队列后,就得到了每行的这个区间的最小值(最大值),就相当于一个长度为行数的数组,然后纵向做单调队列,求出的就是正方形的最值了. 代码 #include <iostream> #

题目描述 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小. 输入 第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔.100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000 输出 仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值. 样例输入 5 4 2 1 2 5 6 0 1