POJ 2019-白红宇

POJ 2019

阅读量：5242 次

发布时间：2019-06-14

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

简单的RMQ，可我怎么写都WA。不明白，找了一个和我相似的贴过了，要赶着去外婆家。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #define eps 1e-5#define MAXN 255#define MAXM 111111#define INF 1000000000using namespace std;int mx[MAXN][MAXN][8], mi[MAXN][MAXN][8];int n, b, q, a, c;void rmqinit(){ int l = int(log(double(n)) / log(2.0)) ; for(int k = 1; k <= n ; k++) for(int j = 1; j <= l; j++) for(int i = 1; i + (1 << (j - 1))- 1 <= n; i++) { mx[k][i][j] = max(mx[k][i][j - 1], mx[k][i + (1 << (j - 1 ))][j - 1]) ; mi[k][i][j] = min(mi[k][i][j - 1], mi[k][i + (1 << (j - 1 ))][j - 1]) ; }}int rmqmax(int lx, int ly, int rx, int ry) // lx, ly为左上角的点 rx ry为右下角的点{ int l = int(log(double(ry - ly + 1)) / log(2.0)); int ret = -1; for(int k = lx; k <= rx ; k++) ret = max(ret, max(mx[k][ly][l], mx[k][ry - (1 << l) + 1][l])); return ret;}int rmqmin(int lx, int ly, int rx, int ry) // lx, ly为左上角的点 rx ry为右下角的点{ int l = int(log(double(ry - ly + 1)) / log(2.0)); int ret = INF; for(int k = lx; k <= rx ; k++) ret = min(ret, min(mi[k][ly][l], mi[k][ry - (1 << l) + 1][l])); return ret;}int main(){ while(scanf("%d%d%d", &n, &b, &q) != EOF) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { scanf("%d",&a); mx[i][j][0] = mi[i][j][0] = a ; } rmqinit(); while(q--) { scanf("%d%d", &a, &c) ; int rx = a + b - 1; if(rx > n) rx = n; int ry = c + b - 1; if(ry > n) ry = n; printf("%d\n", rmqmax(a, c, rx, ry) - rmqmin(a, c, rx, ry)) ; } } return 0;}

MINE：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;int num[255][255];int f1[255][255][30];int f2[255][255][30];int n,b,q;const int inf=1000000000;int rmq_max(int p,int i, int j) { int k = (int)(log(double(j-i+1)) / log(2.0)), t1; t1 = max(f1[p][i][k], f1[p][j - (1<