or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
stack
Competitive programming 2
2021/12/13
最大子矩陣
題目給你 \(N \times M ( N, M \le 2000)\) 的矩陣,上面有一些格子有障礙物,
要找出一個子矩陣,沒有任何障礙物。
問你所有合法的子矩陣中,最大面積為多少?
以上圖為例,假設黑色為障礙物,則合法中最大的子矩陣為紅色框起來的,面積為6
想法1
暴力窮舉所有矩陣判斷合不合法 \(O(N^6)\)
想法2
窮舉矩陣內的每一格判斷是否有障礙物 \(O(N^2)\)計算前綴和,左上到每個點為右下的矩形裡面的障礙物數量
如果要計算區間內的障礙物數量,用排容原理
假設要求 [2,2] 到 [3,4] 子矩陣的障礙物數量
則為 prefix[3][4] - prefix[3][1] - prefix[1][4] + prefix[1][1]
複雜度 \(O(N^4)\)
想法3
DP
先 \(O(N^2)\) 計算出每格往上最高可以到多高
之後窮舉以每格為右下角的所有可能矩形
每次往左判斷從起始格到當前往上最高可以多高
以 [3,4] 為例
往左 1 格高度最高可以為 2
往左 2 格高度最高可以為 2
往左 3 格高度最高可以為 1
複雜度 \(O(N^3)\)
但…還不夠 \(N^3 = 8 \cdot 10^9 \to TLE\)
正解
先 DP 每個點往上最多可以幾格
我們需要用到 stack 來做
一樣窮舉以每個點當右下,然後順便更新答案
其實對於每一列都可以轉換成一下問題
做法如下
每次遇到一個更高的高度把它放進stack
而遇到較低的就更新答案
\(O(N^2)\)
凸包
你有n個點,然後你要找出一個凸多邊形可以圍住這n個點且面積最小,
這個凸多邊形稱為凸包
你也可以想成凸包是用一條橡皮筋把牆壁上的圖釘圈起來的範圍
Andrew's Monotone Chain
(競賽常用的做法)
作法為分別求出上下凸包,求完之後再和再一起,
上半凸包+下半凸包=完整的凸包
先求下凸包
如何判斷合法
首先先觀察凸包,若我們從左到右依序看點,會發現下一個向量都是在前一個向量的逆時鐘方向
像是 \(\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刪掉,一直刪到合法為止,
再把新的點加進去凸包
排序 \(O(NlgN)\) + 找凸包 \(O(N)\)
複雜度 \(O(NlgN)\)
Question Time and Practice
Homework Link
提交期限到下星期一 12/20 23:59 截止