HDU_2888_Check Corners

来源:http://www.cnblogs.com/edward108/archive/2017/10/10/7643944.html
-Advertisement-
Play Games

Check Corners Time Limit: 2000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3247 Accepted Submission(s): 1173 ...


Check Corners

Time Limit: 2000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3247    Accepted Submission(s): 1173


Problem Description Paul draw a big m*n matrix A last month, whose entries Ai,j are all integer numbers ( 1 <= i <= m, 1 <= j <= n ). Now he selects some sub-matrices, hoping to find the maximum number. Then he finds that there may be more than one maximum number, he also wants to know the number of them. But soon he find that it is too complex, so he changes his mind, he just want to know whether there is a maximum at the four corners of the sub-matrix, he calls this “Check corners”. It’s a boring job when selecting too many sub-matrices, so he asks you for help. (For the “Check corners” part: If the sub-matrix has only one row or column just check the two endpoints. If the sub-matrix has only one entry just output “yes”.)  

 

Input There are multiple test cases. 

For each test case, the first line contains two integers m, n (1 <= m, n <= 300), which is the size of the row and column of the matrix, respectively. The next m lines with n integers each gives the elements of the matrix which fit in non-negative 32-bit integer. 

The next line contains a single integer Q (1 <= Q <= 1,000,000), the number of queries. The next Q lines give one query on each line, with four integers r1, c1, r2, c2 (1 <= r1 <= r2 <= m, 1 <= c1 <= c2 <= n), which are the indices of the upper-left corner and lower-right corner of the sub-matrix in question.   

 

Output For each test case, print Q lines with two numbers on each line, the required maximum integer and the result of the “Check corners” using “yes” or “no”. Separate the two parts with a single space.  

 

Sample Input 4 4 4 4 10 7 2 13 9 11 5 7 8 20 13 20 8 2 4 1 1 4 4 1 1 3 3 1 3 3 4 1 1 1 1  

 

Sample Output 20 no 13 no 20 yes 4 yes  

 

Source 2009 Multi-University Training Contest 9 - Host by HIT  
  • 二維區間max,打二維ST表
  • dp[i][j][e][f]表明從矩陣左上角(i,j)開始寬度範圍是2^e,高度範圍是2^f的矩形

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int max4(int a, int b, int c, int d){
25     return max(max(a,b),max(c,d));
26 }
27 int m, n, fac[9], dp[310][310][9][9];
28 int X1, Y1, X2, Y2, ans, mx, q;
29 int main(){
30     // freopen("in.txt","r",stdin);
31     // freopen("out.txt","w",stdout);
32     for(int i=0;i<9;i++)
33         fac[i]=(1<<i);
34     while(~scanf("%d %d",&m,&n)){
35         for(int i=1;i<=m;i++)
36             for(int j=1;j<=n;j++)
37                 scanf("%d",&dp[i][j][0][0]);
38         int rk=(int)(log((double)m)/log(2.0));
39         int ck=(int)(log((double)n)/log(2.0));
40         for(int e=0;e<=rk;e++)
41             for(int f=0;f<=ck;f++)
42                 if(e || f)
43                     for(int i=1;i+fac[e]-1<=m;i++)
44                         for(int j=1;j+fac[f]-1<=n;j++)
45                             if(!e)
46                                 dp[i][j][e][f]=max(dp[i][j][e][f-1],dp[i][j+fac[f-1]][e][f-1]);
47                             else if(!f)
48                                 dp[i][j][e][f]=max(dp[i][j][e-1][f],dp[i+fac[e-1]][j][e-1][f]);
49                             else
50                                 dp[i][j][e][f]=max4(dp[i][j][e-1][f-1],dp[i+fac[e-1]][j][e-1][f-1],dp[i][j+fac[f-1]][e-1][f-1],dp[i+fac[e-1]][j+fac[f-1]][e-1][f-1]);
51         scanf("%d",&q);
52         while(q--){
53             ans=0;
54             scanf("%d %d %d %d",&X1,&Y1,&X2,&Y2);
55             rk=(int)(log((double)(X2-X1+1))/log(2.0));
56             ck=(int)(log((double)(Y2-Y1+1))/log(2.0));
57             mx=max4(dp[X1][Y1][rk][ck],dp[X2-fac[rk]+1][Y1][rk][ck],dp[X1][Y2-fac[ck]+1][rk][ck],dp[X2-fac[rk]+1][Y2-fac[ck]+1][rk][ck]);
58             if(mx==dp[X1][Y1][0][0]||
59                 mx==dp[X1][Y2][0][0]||
60                 mx==dp[X2][Y1][0][0]||
61                 mx==dp[X2][Y2][0][0]){
62                 ans=1;
63             }
64             printf("%d %s\n",mx,ans?"yes":"no");
65         }
66     }
67     return 0;
68 }

 

 

 


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

-Advertisement-
Play Games
更多相關文章
  • Asp.net Core 由於依賴註入的廣泛使用,配置數據遷移,與Asp.net大不相同,本篇介紹一下Asp.net Core添加數據遷移的過程 添加Nuget包 首先新建一個 Model 類 User: public class User { //用戶編號(自增長主鍵) [Key] public ...
  • 基本結構 規則 1、try語句至少要有一個對應的catch或finally,不允許單獨一個try語句 2、如果到了調用棧頂部,仍然沒有找到匹配的catch語句,就會發生未處理異常 3、找到匹配的catch塊後,會先執行內層的所有finally語句,就是從拋出異常的try語句開始,到匹配異常的catc ...
  • (原文)CNTK v2.2.0提供C#API來建立、訓練和評估CNTK模型。 本節概要介紹了CNTK C#API。 在CNTK github respository中可以找到C#訓練示例。 使用C#/ .NET管理API構建深層神經網路 CNTK C#API 通過CNTKLib命名空間提供基本操作。 ...
  • 預設情況下,每一個MVC請求的HTTP Header中都會包含著當前伺服器的一些信息,出於安全還是性能還是處女座的強迫症等等,都想把這些信息移除掉,增加一些應用程式的神秘感,如下,預設情況下Chrome中截獲的HTTP Header信息: Cache-Control:private, s-maxag... ...
  • AI聖經 深度學習領域奠基性的經典暢銷書!長期位居美國亞馬遜AI和機器學習類圖書榜首!所有數據科學家和機器學習從業者的必讀圖書!特斯拉CEO埃隆·馬斯克等國內外眾多專家推薦! 深度學習是機器學習的一個分支,它能夠使電腦通過層次概念來學習經驗和理解世界。因為電腦能夠從經驗中獲取知識,所以不需要人類 ...
  • 作業1: 需求:輸出一個由 * 符號所組成的矩形,要求每行有50個 * ,一共需要有60行。使用雙重for迴圈完成。 作業2: 需求:輸出一個由 * 符號所組成的三角形,要求第一行一個 * ,第二行 兩個 * 第三行 三個 * 依次類推,最後一行10個 *。使用雙重for迴圈完成。 作業3: 需求: ...
  • A Magic Lamp Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4694 Accepted Submission(s): 1947 Pr ...
  • cookie與session都是保存會話數據的技術 cookie存放在用戶端的磁碟中,瀏覽器一般只允許存放300個cookie,且每一個站點最多存放20個cookie,每個cookie的大小限製為4kb;當用戶需要記住自己的用戶名與密碼的時候,事件發生在用戶本地瀏覽器,所以使用cookie技術。co ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...