P1 修補圍籬
題解
如果在兩端就直接取旁邊的高度,否則取跟左右邊高度的最小值。
時間複雜度
$O(n)$
AC程式碼
1 |
|
BY peienwu
P2 動線安排(魔王題)
題解
把線分成橫的跟直的就可以好好處理交叉了!
時間複雜度
$O(h(n + m))$
AC程式碼
1 |
|
BY thanksone
P3 生產線
差分作法
題解
用差分的想法加值,再用前綴還原,最後再排序。最後利用Greedy的想法,將每一項最小的工作量乘上最大的時間,總和即為答案。
差分
差分是前綴和的逆運算,也就是說,把兩項的差算出來就是差分。定義如下:
差分的使用時機是區間加值,一個區間內的數字都加上一個定值,這時候就可以使用到差分的技巧。使用方式如下,當我要在區間 $[l,r]$ 的每一個數字都加上一個值$v$,以下步驟:
- 定義一個新的陣列 $b_i$ 表示每一項差分
- 設 $b[l] = b[l] + v,b[r+1] = b[r+1] - v$
- 將差分的每一項加上前一項(做前綴和 $b[i] = b[i]+b[i-1]$),即為原數列
第二步驟可以重複好幾次做,這樣複雜度從原本的$O(n)$就變成了$O(1)$了!
時間複雜度
差分:$O(m)$ 、排序 $O(n\log n)$
總時間複雜度:$O(n\log n + m)$
AC程式碼
1 |
|
BY peienwu
線段樹作法
很奇怪,最近兩次的APCS第三題都有人想要砸資結,特別是線段樹,可能有些人特別偏愛線段樹吧!
題解
線段樹最原本的應該是區間詢問、單點修改,如果要區間修改的話就會用到懶標,所以實作上相對上比較複雜一點。這一題用線段樹的目的是區間加值,加值完過後的排序以及Greedy跟差分的作法是一樣的,用線段樹真的是多此兩舉(實作較複雜、較耗時)!
當然,這一題比較特別只有最後一起做單點查詢,因此不用懶標,最侯直接計算一路去經過的答案也行!下面的程式碼就是把完全包含區間的節點加值,不用使用到懶標,最後一次查詢。
時間複雜度
區間加值 $O(m\log n)$,n個點的詢問 $O(n\log n)$,排序 $O(n\log n)$
總時間複雜度:$O((n+m)\log n)$
AC程式碼
1 |
|
P4 真假子圖
二分搜尋+DFS作法
題解
一開始看到這題,應該很難通靈出二分搜這個作法(我覺得光把題目看懂就有點難度了)。這題有一個條件要特別注意:
保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合
這一題每一個觀察員並可看成不是獨立的(假如一個觀察員不產生矛盾,則他回傳的那一些邊都會被沿用),所以題目 $p$ 筆詢問可以聯集一起處理。
將情報員當成點,合作關係當成邊,那麼合法的圖就會有兩個點集,點集中的點互不相鄰,也就是二分圖。
二分搜第一個使得圖變得不二分的人,把它消失,最多重複3次就做完了。
為什麼可以二分搜?
二分搜是用來找一串01字串的分界點,並且必須具有單調性才能二分搜。這一題之所以會有單調性是因為,當我查詢觀察員$P_i$的回傳資料是否正確時,會將前面 $1$ 到 $i-1$ 的觀察員回傳的所有邊納入考慮。
假設有一個觀察員 $P_j(1\le j < i)$ 回傳的資料是錯誤的,這些邊會導致整張圖變成非二分圖,對於 $j$ 後面的所有點來說,都是非二分圖。這樣就有了以 $j$ 為分界點的單調性,即可二分搜。
二分圖判斷可以用 DFS 做,DFS 的時候把每個點塗上顏色,如果相鄰的點跟自己顏色一樣就表示這不是一張二分圖。
時間複雜度
$O((n + m + pk)\log p)$
AC程式碼
1 |
|
BY thanksone
DSU作法
Idea From Kennyfs
題解
這一題的題目限制有說最多3個錯誤的情報員,因此我們可以用上面二分搜的方式做三次找到答案。如果題目不限制錯誤調查員的數量,也就是用二分搜時間會超時,但是用DSU可以在線性時間內完成!
DSU的目的在處理集合問題,根據下面這個關鍵條件:
保證若調查員的 k 個 pair 的結果和組長存留的 m 個 pair 不會產生矛盾, 則保證調查員的資料一定和原本 A, B 分組吻合
我們只要對每一筆詢問看會不會與組長手中的pair矛盾即可。如果每一次都做DFS,會發現時間複雜度是 $O(pn)$,必然超時。
DSU的想法是,我們將組長手中的圖中上每一個連通塊都分別塗上兩種顏色(必為二分圖,因此將兩邊各塗上不同顏色)。接著,把每個顏色當作初始的並查集中的集合,將每一筆觀察員回傳的邊的兩端指向的集合合併起來,過程中如果發生邊的兩端同屬一個集合,表示這是一個錯誤的觀察員。做完每一個觀察員之後,把所有變更過的還原成初始狀態(組長手中的圖)即可。
舉例
8 5
0 2 1 3 1 2 4 6 5 6
1 2
1 4 0 6
整個過程就是下面這張GIF:
步驟:
- 利用DFS為組長手中的圖上色,每一個連通塊兩色(以編號1,2,3…)
- 將每一個顏色當作並查集元素
- 觀察員輸入的邊兩端 $(u,v)$非同色,表示不發生矛盾,則將u所在集合與v所在集合的對方(連通塊兩色的另一色)合併
- 重複 步驟3 共k次,如果發生$(u,v)$為同一色,則觀察員錯誤。
時間複雜度
$O(n + pk\alpha)$
AC程式碼
1 |
|
BY peienwu