APCS 110/11 實作題題解
2021-11-07 16:25:00 by Akira
心得
感覺這次似乎比較有難一點,寫第二題寫了很久 (比其他三題加起來還久),第四題也稍微想了兩三分鐘。
P.S. 打廣告一下,我最近有在接程式設計/解題的家教,有需要的可以聯絡我 FB 或 LINE。
第一題
有一個 N 個非負整數的陣列,不會有兩個相鄰的零。
對與每個零計算其左邊與右邊的較小值,然後把這些值加起來即為答案。
3 <= N <= 100
時間複雜度 O(N)
第二題
十分麻煩的二維模擬題
待補
第三題
題目
給你一堆正整數 N, A[1..N], M, L[1..M], R[1..M], X[1..M]; N, M <= 200000
有 N 個格子 B[1..N] (一開始都是零),首先你要把 B[L[i]..R[i]] 都加上 X[i]。
接下來你要讓 A[1..N] 的每個數字配到 B[1..N] 當中的一個數字 (一對一),使得每個配對當中的兩個數字相乘的總和愈小愈好。
解法
- Prefix Sum 計算每個格子上面的數字
(例如要把 B[15..25] 都加 7,那就把 C[15] += 7; C[25 + 1] -= 7,最後計算 B[i] = B[i-1]+C[i]) - Greedy 配對 (排序後最大配最小 第二大配第二小 依此類推)
時間複雜度 O(NlgN + M)
第四題
題目
有 N 個點 (vertex) 以及 P+1 個邊集 E[0..P]
找出 i=1..P 當中有哪些 i 符合: ((E[0] 與 E[i] 的聯集) 不是二分圖)
保證符合的 i 最多三個
N 不超過 20000; P 不超過 10000; E[0] 最多 200000 條邊; E[1..P] 各最多 20 條邊
解法
使用 BFS 做二分圖判定。
由於不是二分圖的情況最多三個,
可以使用二分搜尋找出 還不確定的邊集們 當中 不是二分圖的最小編號
(重點是 每次做BFS 可以拿一堆邊集的聯集去做 如果結果是二分圖就表示他們全部都是二分圖)
時間複雜度 O((N + |E|) log P)
如果沒有最多三個的條件,也可以使用 disjoint set + undo。
時間複雜度大概是 O(N + |E| log N)
上面的 |E| 是所有邊集的總邊數
[APCS] [APCS 110/11]