首页 > 代码库 > POJ--2019--Cornfields【二维RMQ】
POJ--2019--Cornfields【二维RMQ】
链接:http://poj.org/problem?id=2019
题意:给你一个n*n的矩阵,q次询问,每次询问给出左上角的坐标,询问以这个点为左上角的b*b的子矩阵中最大值和最小值的差。
思路:二维RMQ的基本应用,网上找的模板
这道题是USACO的,数据很水,暴力也能过。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 260 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int a[MAXN][MAXN]; int maxm[MAXN][MAXN][11],minm[MAXN][MAXN][11]; void RMQ(int num){ int i,j,k; for(i = 1; i <= num; i++){ for(j = 1; j <= num; j++){ maxm[i][j][0] = minm[i][j][0] = a[i][j]; } } for(i = 1; i <= num; i++){ for(k = 1; (1 << k) <= num; k++){ for(j = 1; j + (1 << k) - 1 <= num; j++){ maxm[i][j][k] = max(maxm[i][j][k-1],maxm[i][j+(1<<(k-1))][k-1]); minm[i][j][k] = min(minm[i][j][k-1],minm[i][j+(1<<(k-1))][k-1]); } } } } int main(){ int i,j,n,b,q; int top,left; scanf("%d%d%d",&n,&b,&q); for(i = 1; i <= n; i++){ for(j = 1; j <= n; j++){ scanf("%d", &a[i][j]); } } RMQ(n); while(q--){ scanf("%d%d", &top, &left); int k = (int)(log(double(b))/log(2.0)); int minans = INF, maxans = 0; int x = left, y = left + b - 1; for(i = top; i < top + b; i++){ maxans = max(maxans,max(maxm[i][x][k],maxm[i][y-(1<<k)+1][k])); minans = min(minans,min(minm[i][x][k],minm[i][y-(1<<k)+1][k])); } printf("%d\n",maxans - minans); } return 0; }
POJ--2019--Cornfields【二维RMQ】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。