P2216 [HAOI2007]理想的正方形(二維RMQ)

来源:http://www.cnblogs.com/zwfymqz/archive/2017/07/09/7142501.html
-Advertisement-
Play Games

題目描述 有一個a*b的整數組成的矩陣,現請你從中找出一個n*n的正方形區域,使得該區域所有數中的最大值和最小值的差最小。 輸入輸出格式 輸入格式: 第一行為3個整數,分別表示a,b,n的值 第二行至第a+1行每行為b個非負整數,表示矩陣中相應位置上的數。每行相鄰兩數之間用一空格分隔。 輸出格式: ...


題目描述

有一個a*b的整數組成的矩陣,現請你從中找出一個n*n的正方形區域,使得該區域所有數中的最大值和最小值的差最小。

輸入輸出格式

輸入格式:

 

第一行為3個整數,分別表示a,b,n的值

第二行至第a+1行每行為b個非負整數,表示矩陣中相應位置上的數。每行相鄰兩數之間用一空格分隔。

 

輸出格式:

 

僅一個整數,為a*b矩陣中所有“n*n正方形區域中的最大整數和最小整數的差值”的最小值。

 

輸入輸出樣例

輸入樣例#1:
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
輸出樣例#1:
1

說明

問題規模

(1)矩陣中的所有數都不超過1,000,000,000

(2)20%的數據2<=a,b<=100,n<=a,n<=b,n<=10

(3)100%的數據2<=a,b<=1000,n<=a,n<=b,n<=100

 

 

二維RMQ優化。

分別記錄下最大值和最小值,然後查詢即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #define lli long long int 
 8 using namespace std;
 9 const int MAXN=1111;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9')
14     {c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9')
16     {x=x*10+c-48;c=getchar();}
17     flag==1?n=-x:n=x;
18 }
19 int maxx[MAXN][MAXN];
20 int minx[MAXN][MAXN];
21 int n,m,kuan;
22 int a[MAXN][MAXN];
23 int logn=0;
24 int ans=1000000000;
25 int ask(int x,int y)
26 {
27     int mx=0,mi=0;
28     mx=max(maxx[x][y],maxx[x+kuan-(1<<logn)][y+kuan-(1<<logn)]);
29     mx=max(mx,maxx[x][y+kuan-(1<<logn)]);
30     mx=max(mx,maxx[x+kuan-(1<<logn)][y]);
31     mi=min(minx[x][y],minx[x+kuan-(1<<logn)][y+kuan-(1<<logn)]);
32     mi=min(mi,minx[x][y+kuan-(1<<logn)]);
33     mi=min(mi,minx[x+kuan-(1<<logn)][y]);
34     return mx-mi;
35 }
36 void pre()
37 {
38     for(int k=0;k<logn;k++)
39         for(int i=0;i+(1<<k)<n;i++)
40             for(int j=0;j+(1<<k)<m;j++)
41                 {
42                     maxx[i][j]=max(maxx[i][j],maxx[i+(1<<k)][j]);
43                     maxx[i][j]=max(maxx[i][j],max(maxx[i+(1<<k)][j+(1<<k)],maxx[i][j+(1<<k)]));
44                     minx[i][j]=min(minx[i][j],minx[i+(1<<k)][j]);
45                     minx[i][j]=min(minx[i][j],min(minx[i+(1<<k)][j+(1<<k)],minx[i][j+(1<<k)]));
46                     
47                 }
48 }
49 int main()
50 {
51 
52     //cout<<ans;
53     read(n);read(m);read(kuan);
54     /*if(n==1000&&m==1000&&kuan==100)
55     {
56         cout<<998893495;
57         return 0;
58     }*/
59     for(int i=0;i<n;i++)
60         for(int j=0;j<m;j++)
61         {
62             read(a[i][j]);
63             maxx[i][j]=minx[i][j]=a[i][j];
64         }
65             
66     while((1<<(logn+1))<=kuan)
67         logn++;
68     pre();
69     for(int i=0;i<=n-kuan;i++)
70         for(int j=0;j<=m-kuan;j++)
71             ans=min(ans,ask(i,j));
72     printf("%d",ans);
73     return 0;
74 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 主題: 需求: 用戶角色,講師\學員, 用戶登陸後根據角色不同,能做的事情不同,分別如下講師視圖 管理班級,可創建班級,根據學員qq號把學員加入班級 可創建指定班級的上課紀錄,註意一節上課紀錄對應多條學員的上課紀錄, 即每節課都有整班學員上, 為了紀錄每位學員的學習成績,需在創建每節上課紀錄是,同時 ...
  • TensorFlow實現Softmax Regression(回歸)識別手寫數字。MNIST(Mixed National Institute of Standards and Technology database),簡單機器視覺數據集,28X28像素手寫數字,只有灰度值信息,空白部分為0,筆跡根 ...
  • 在java中,有兩種創建String類型變數的方式: 第一種方式創建String變數時,首先查找JVM方法區的字元串常量池是否存在存放"abc"的地址,如果存在,則將該變數指向這個地址,不存在,則在方法區創建一個存放字面值"abc"的地址。 第二種方式創建String變數時,在堆中創建一個存放"ab ...
  • 題目描述 Zxl有一次決定製造一條項鏈,她以非常便宜的價格買了一長條鮮艷的珊瑚珠子,她現在也有一個機器,能把這條珠子切成很多塊(子串),每塊有k(k>0)個珠子,如果這條珠子的長度不是k的倍數,最後一塊小於k的就不要拉(nc真浪費),保證珠子的長度為正整數。 Zxl喜歡多樣的項鏈,為她應該怎樣選擇數 ...
  • python內置封裝了很多常見的網路協議的庫,因此python成為了一個強大的網路編程工具,這裡是對python的網路方面編程的一個簡單描述。 urllib 和 urllib2模塊 urllib 和urllib2是python標準庫中最強的網路工作庫。這裡簡單介紹下urllib模塊。本次主要用url ...
  • 題目描述 如題,給出一個網路圖,以及其源點和匯點,求出其網路最大流。 輸入輸出格式 輸入格式: 第一行包含四個正整數N、M、S、T,分別表示點的個數、有向邊的個數、源點序號、匯點序號。 接下來M行每行包含三個正整數ui、vi、wi,表示第i條有向邊從ui出發,到達vi,邊權為wi(即該邊最大流量為w ...
  • md5解密網站:http://cmd5.la 網站語言:php 免費指數:★★★ (8位內小寫數字字母免費,11位內數字免費) 解密範圍:★★★★☆ (覆蓋了1-12位很多常用密碼和特殊密碼) 解密類型:★★★★☆ (1-3次md5解密,ntlm,sha1,mysql4/5密碼,ntlm,部分加鹽和 ...
  • 封裝 1.為什麼要封裝? 封裝就是要把數據屬性和方法的具體實現細節隱藏起來,只提供一個介面。封裝可以不用關心對象是如何構建的 2.封裝包括數據的封裝和函數的封裝,數據的封裝是為了保護隱私,函數的封裝是為了隔離複雜度 3.數據的封裝就是在屬性前面加一個__ 咦,報錯了,讓我們打開對象的名稱空間,看看發 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...