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] 當中的一個數字 (一對一)，使得每個配對當中的兩個數字相乘的總和愈小愈好。

解法

1. Prefix Sum 計算每個格子上面的數字
   (例如要把 B[15..25] 都加 7，那就把 C[15] += 7; C[25 + 1] -= 7，最後計算 B[i] = B[i-1]+C[i])
2. 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]