题目
1081 - Square Queries
| Time Limit: 3 second(s) | Memory Limit: 64 MB |
Little Tommy is playing a game. The game is played on a 2D N x N grid. There is an integer in each cell of the grid. The rows and columns are numbered from1 toN.
At first the board is shown. When the user presses a key, the screen shows three integersI, J, S which designates a square(I, J) to(I+S-1, J+S-1) in the grid. The player has to predict the largest integer
found in this square. The user will be given points based on the difference between the actual result and the given result.
Tommy doesn't like to lose. So, he made a plan, he will take help of a computer to generate the result. But since he is not a good programmer, he is seeking your help.
Input
Input starts with an integer T (≤ 3), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers
N (1 ≤ N ≤ 500), Q (0 ≤ Q ≤ 50000). Each of the next N lines will containN space separated integers forming the grid. All the integers will be between0 and105.
Each of the next Q lines will contain a query which is in the formI J S (1 ≤ I, J ≤ N and 1 ≤ I + S, J + S< N and S > 0).
Output
For each test case, print the case number in a single line. Then for each query you have to print the maximum integer found in the square whose top left corner is(I, J) and whose bottom right corner is(I+S-1, J+S-1).
Sample Input |
Output for Sample Input |
|
1
4 5 67 1 2 3 8 88 21 1 89 12 0 12 5 5 5 5 1 1 2 1 3 2 3 3 2 1 1 4 2 2 3 |
Case 1: 88 21 12 89 88 |
Note
Dataset is huge. Use faster i/o methods.
实现方法一：四维变三维
思路
我想到的方法是怎么样能够把数组开的小一些，因为如果用以前的模板按照模板标准开dp数组，我要开一个 500 * 500 * 9 * 9 的数组，也就是20250000=。=
简直是凶残， 20,250,000 的数据，太庞大了有没有！
超内存有没有！MLE！！！
但是如果能够降一维（其实当时我觉得是要能降一点点就够了=_=），但问题是怎么降维度？
我们以前讨论的从一维RMQ中的ST算法升级到二维RMQ中的ST算法，运用的是分类分治的方法（参见我以前的博文：http://blog.csdn.net/polossk/article/details/12240503）
“（以下为引用，懒得再手写了=_=）
ST算法的核心就在于“二分”，当然不是传统意义上的二分了，毕竟是二维的，要分类来进行二分处理。
简单地说，定义dp[row][col][i][j] 表示[row,row+2^i-1] x [col,col+2^j-1] 二维区间内的最小值。
那么，有：
dp[row][col][i][j]
= min( [row,row+ 2^(i-1)-1] x [col,col+2^j-1] ,
[row+2^(i-1),row+2^i-1] x [col,col+2^j-1] )
（左半区的最小值 和 右半区的最小值）
= min( dp[row][col][i-1][j] , dp[row + (1<<(i-1))][col][i-1][j] )
（左半区的最小值 和 右半区的最小值，相当于固定了y轴坐标不变，将区域分割成左右两个区）
同样的，也有：
dp[row][col][i][j]=
= min( [row,row+ 2^i-1] x [col,col+2^(j-1)-1] ,
[row,row+2^i-1] x [col+2^(i-1),col+2^j-1]
)
（上半区的最小值 和 下半区的最小值）
= min( dp[row][col][i][j-1] ,
dp[row][col + (1<<(i-1))][i][j-1] )
（上半区的最小值 和 下半区的最小值，相当于固定了x轴坐标不变，将区域分割成上下两个区）
”
既然是运用分类分治的方法把二维的问题分成了垂直划分和水平划分，我们就肯定能用一个简单的综合法把这些划分再还原成原状态，额(⊙o⊙)…有点绕嘴，这样，请好好看看我们的思路：
对于一维RMQ问题，ST算法的思路是二分，相当于
大问题 -> 两个小问题
结合上一维的情况，如果用x轴来表示一维，那么就是
大线段 -> 两个小线段
没错吧。
那么二维RMQ问题呢？如果你选择ST算法迭代ST算法，那么你很可能是走了这条路：
大问题 -> 分类讨论；
结合二维的情况，如果求解一个矩形内的最值，那么就是
大矩形 ->分割！ -> 在x轴的问题，那就在x轴上二分；在y轴的问题，那就在y轴上二分
但实际上我觉得，对于这道题目，因为所有访问的矩形全是正方形！注意全是正方形，所以我觉得这条路也没有错
大问题 ->四个小问题
结合我们的实际问题那就是：
大矩形 ->四个小矩形 -> 综合计算
状态转移方程就是
dp[row][col][k] 表示[row,row+2^k-1] x [col,col+2^k-1] 中的最大值
dp[row][col][k] = max(
dp[row][col][k-1],
dp[row+(1<<(k-1))][col][k-1],
dp[row][col+(1<<(k-1))][k-1],
dp[row+(1<<(k-1))][col+(1<<(k-1))][k-1]
);
注意！这个思想只是因为正方形的访问才能使用！切记切记！
代码示例
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f_max(int x,int y){return x>y?x:y;}
int f_max(int a,int b,int c,int d){
return f_max(f_max(a,b),f_max(c,d));
}
int N,Q,num[500][500];
int dp[500][500][10];
void get_data(){
int i,j,k,l;
scanf(" %d %d",&N,&Q);
for(i=0;i<N;i++){
for(j=0;j<N;j++){
scanf(" %d",&num[i][j]);
dp[i][j][0]=num[i][j];
}
}
for(k=1,l=2;l<=N;k++,l<<=1){
for(i=0;i+l-1<N;i++){
for(j=0;j+l-1<N;j++){
dp[i][j][k]=f_max(
dp[i][j][k-1],
dp[i+(l>>1)][j][k-1],
dp[i][j+(l>>1)][k-1],
dp[i+(l>>1)][j+(l>>1)][k-1]
);
}
}
}
}
void run(){
int xi,xj,xl,k,l;
while(Q--){
scanf(" %d %d %d",&xi,&xj,&xl);xi--;xj--;
k=log(xl*1.0)/log(2.0);l=1<<k;
printf("%d\n",f_max(
dp[xi][xj][k],
dp[xi][xj+xl-l][k],
dp[xi+xl-l][xj][k],
dp[xi+xl-l][xj+xl-l][k]
)
);
}
}
void solve(int i){
get_data();
printf("Case %d:\n",i);
run();
return;
}
int main(){
int i=0,t;
scanf("%d",&t);
while (t--){
solve(++i);
}
return 0;
}
实现方法二：节约内存，手写unsigned int17_t
思路
这个方法是在网上游荡时发现的，真是神一样的方法！原地址：http://www.java123.net/detail/view-349945.html
首先我们很快就会发现数据的大小在0到100000之间（All the integers will be between0 and105），所以这位大牛突发奇想：
--->请看表格
| 数据类型 | 数据大小 |
| short | -32768 ~ +32767 |
| unsigned short | 0 ~ 65535 |
| bit + unsigned short | 0 ~ 131071 |
那么如果来一个unsigned int17_t，问题解决！
果然是大神的办法。那么如何实现呢？
同时开
unsigned short dt[501][10][501][10];
bitset<500*10*500*10+10> de;
然后增加函数trans，用于计算数组下标，函数如下：
int tr(int i,int j,int k,int l)
{
return (i-1)*10*500*10+j*500*10+(k-1)*10+l;
}
之后就是模板问题和细节处理了=。=
代码如下：
#include<cstdio>
#include<algorithm>
#include<vector>
#include<bitset>
using namespace std;
int tr(int i,int j,int k,int l)
{
return (i-1)*10*500*10+j*500*10+(k-1)*10+l;
}
unsigned short dt[501][10][501][10];
bitset<500*10*500*10+10>de;
int fc[510],n;
void upd(int i,int j,int k,int l,int i2,int j2,int k2,int l2,int i3,int j3,int k3,int l3)
{
if(de[tr(i2,j2,k2,l2)]==de[tr(i3,j3,k3,l3)])
{
de[tr(i,j,k,l)]=de[tr(i2,j2,k2,l2)];
if(dt[i2][j2][k2][l2]>dt[i3][j3][k3][l3])
dt[i][j][k][l]=dt[i2][j2][k2][l2];
else dt[i][j][k][l]=dt[i3][j3][k3][l3];
}
else if(de[tr(i2,j2,k2,l2)]>de[tr(i3,j3,k3,l3)])
{
dt[i][j][k][l]=dt[i2][j2][k2][l2];
de[tr(i,j,k,l)]=de[tr(i2,j2,k2,l2)];
}
else
{
dt[i][j][k][l]=dt[i3][j3][k3][l3];
de[tr(i,j,k,l)]=de[tr(i3,j3,k3,l3)];
}
}
void build()
{
for(int j=0; (1<<j)<=n; ++j)
for(int i=1; i+(1<<j)-1<=n; ++i)
for(int l=0; (1<<l)<=n; ++l)
for(int k=1; k+(1<<l)-1<=n; ++k)
{
if(!l&&j)upd(i,j,k,l,i,j-1,k,l,i+(1<<(j-1)),j-1,k,l);
if(l)upd(i,j,k,l,i,j,k,l-1,i,j,k+(1<<(l-1)),l-1);
}
fc[1]=0;
for (int i=2;i<=n;++i)fc[i]=fc[i-1]+((1<<(fc[i-1]+1))<=i);
}
int ty(int i,int j,int k,int l)
{
return (int(de[tr(i,j,k,l)])<<16)+dt[i][j][k][l];
}
int q1d(int i,int j,int c,int d)
{
return max(ty(i,j,c,fc[d-c+1]),ty(i,j,d-(1<<fc[d-c+1])+1,fc[d-c+1]));
}
int q2d(int a,int b,int c,int d)
{
return max(q1d(a,fc[b-a+1],c,d),q1d(b-(1<<fc[b-a+1])+1,fc[b-a+1],c,d));
}
int main()
{
int T;
scanf("%d",&T);
for (int kase=1;kase<=T;kase++)
{
de.reset();
int q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
int t;
scanf("%d",&t);
de[tr(i,0,j,0)]=(t>>16);
dt[i][0][j][0]=(t&((1<<16)-1));
}
build();
printf("Case %d:\n",kase);
for(int i=1;i<=q;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
printf("%d\n",q2d(a,a+c-1,b,b+c-1));
}
}
return 0;
}
总结
一直以来都有这样一句话：“空间换时间，时间换空间”。RMQ问题的ST算法也不例外。为了达到O(1)查询，把O(n * m)的内存扩大至O(n * m * logn * logm)。典型的空间换时间应用。然而对于这种时间要求很紧张，空间要求也紧张的题目，在保证时间复杂度不增加的条件下，我们只能选择进行空间压缩。当然，深入内存，像解法二一样写一个int17_t虽然没有错，但是对于我这种初学者显然要求太高了。最简单当然也是最节约内存的方法是降维度，二维变一维，三维变二维，大多是这种方法。
可以让大家看看内存优化的效率：
这三次提交分别对应，没有优化内存，方案一降维度优化内存，方案二int17_t优化内存。
内存很明显的变化有没有！！！
但是就算法的适应性而言，方案一很显然没有方案二用的广泛，严格的讲，方案二是真真正正的从内存角度考虑，切切实实的把内存利用好，方案一是因为这道题目中的特殊条件“正方形查询”才有的方法，所以在更一般的二维RMQ问题ST算法应用中，我个人更倾向于结合题中所给数据的范围来规划你的内存使用。但是对于明确的有特殊类型访问的的问题，显然要老老实实地从算法的基础开始思维，才能得到更好地解。
以后也要多多练习数据结构方面的题目，熟能生巧~