changed 4 years ago
Linked with GitHub

stack

Competitive programming 2

2021/12/13


  • 最大子矩陣
  • 凸包

最大子矩陣

題目給你 \(N \times M ( N, M \le 2000)\) 的矩陣,上面有一些格子有障礙物,
要找出一個子矩陣,沒有任何障礙物。

問你所有合法的子矩陣中,最大面積為多少?

以上圖為例,假設黑色為障礙物,則合法中最大的子矩陣為紅色框起來的,面積為6


想法1

暴力窮舉所有矩陣判斷合不合法 \(O(N^6)\)

  • 窮舉左上角 \(O(N^2)\)
  • 窮舉右下角 \(O(N^2)\)
  • 窮舉矩陣內的每一格判斷是否有障礙物 \(O(N^2)\)

想法2

  • 窮舉左上角 \(O(N^2)\)
  • 窮舉右下角 \(O(N^2)\)
  • 窮舉矩陣內的每一格判斷是否有障礙物 \(O(N^2)\)

計算前綴和,左上到每個點為右下的矩形裡面的障礙物數量

如果要計算區間內的障礙物數量,用排容原理

假設要求 [2,2] 到 [3,4] 子矩陣的障礙物數量

則為 prefix[3][4] - prefix[3][1] - prefix[1][4] + prefix[1][1]


  • 窮舉左上角 \(O(N^2)\)
  • 窮舉右下角 \(O(N^2)\)

複雜度 \(O(N^4)\)


想法3

DP

\(O(N^2)\) 計算出每格往上最高可以到多高

之後窮舉以每格為右下角的所有可能矩形

每次往左判斷從起始格到當前往上最高可以多高

以 [3,4] 為例
往左 1 格高度最高可以為 2
往左 2 格高度最高可以為 2
往左 3 格高度最高可以為 1


  • 窮舉右下角 \(O(N^2)\)
  • 窮舉左界 \(O(N)\)

複雜度 \(O(N^3)\)

還不夠 \(N^3 = 8 \cdot 10^9 \to TLE\)


正解

先 DP 每個點往上最多可以幾格

我們需要用到 stack 來做

一樣窮舉以每個點當右下,然後順便更新答案


其實對於每一列都可以轉換成一下問題

做法如下
每次遇到一個更高的高度把它放進stack

而遇到較低的就更新答案

\(O(N^2)\)


凸包

你有n個點,然後你要找出一個凸多邊形可以圍住這n個點且面積最小,
這個凸多邊形稱為凸包

你也可以想成凸包是用一條橡皮筋把牆壁上的圖釘圈起來的範圍



Andrew's Monotone Chain

(競賽常用的做法)


作法為分別求出上下凸包,求完之後再和再一起,
上半凸包+下半凸包=完整的凸包


先求下凸包

  1. 先將全部點照\(x\)大小排序,再排\(y\)大小
  2. 依序嘗試將點加入凸包判斷是否合法
  3. 不合法刪掉前面最後一個點,合法則將點加進凸包

如何判斷合法

首先先觀察凸包,若我們從左到右依序看點,會發現下一個向量都是在前一個向量的逆時鐘方向
像是 \(\overrightarrow{P_2 P_3}\) 會在 \(\overrightarrow{P_2 P_4}\) 的逆時鐘方向


\(\overrightarrow{P_{i} P_{i+1}}\) 若是在\(\overrightarrow{P_{i} P_{i+2}}\) 的逆時鐘方向,則\(\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} > 0\)

因此如果 \(\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} \le 0\) 代表前一個點會在凸包裡面,
而不會在凸包上,就可以把前一個點刪掉,再把新的點加進去凸包裡面


而實作可以用一個stack去維護,
一開始先把前兩個點直接加進去stack之後每一個點\(P_i\)都去判斷,
向量是不是往逆時針方向 ( \(\overrightarrow{P_{i-2} P_{i-1}} \times \overrightarrow{P_{i-2} P_{i}} > 0\) )
若非法則把stack的top刪掉,一直刪到合法為止,
再把新的點加進去凸包


struct Pt{ int x,y; Pt(){} Pt(int _x,int _y){ x=_x,y=_y; } friend bool operator<(const Pt& lhs,const Pt& rhs){ return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x; } friend Pt operator-(const Pt& lhs,const Pt& rhs){ return Pt(rhs.x-lhs.x,rhs.y-lhs.y); } friend int cross(const Pt& o,const Pt& a,const Pt& b){ Pt lhs = o-a, rhs = o-b; return lhs.x*rhs.y - lhs.y*rhs.x; } }; vector<Pt> convex_hull(vector<Pt> hull){ sort(hull.begin(),hull.end()); int top=0; vector<Pt> stk; for(int i=0;i<hull.size();i++){ while(top>=2&&cross(stk[top-2],stk[top-1],hull[i])<=0) stk.pop_back(),top--; stk.push_back(hull[i]); top++; } for(int i=hull.size()-2,t=top+1;i>=0;i--){ while(top>=t&&cross(stk[top-2],stk[top-1],hull[i])<=0) stk.pop_back(),top--; stk.push_back(hull[i]); top++; } stk.pop_back(); return stk; }

排序 \(O(NlgN)\) + 找凸包 \(O(N)\)
複雜度 \(O(NlgN)\)


Question Time and Practice

Homework Link

提交期限到下星期一 12/20 23:59 截止

Select a repo