因為記憶體很小所以不能開陣列儲存數字,只能用 counting sort 解
仔細看就會發現每九個就會重複一輪,所以就有以下的公式解
想法很簡單,先將陣列開兩倍
一個人有兩個點 ,一個是紀錄朋友用的,另外一個是敵人
所以:
換成 code 的話應該會變成這樣:
換個簡單的說法,只要關係線有跨過 就算是敵人
可以把 dsu 的值直接加負號如以下:
本題要找出有幾組 符合 ,也就是「三元逆序數對」。
用迴圈尋找所有的 ,並判斷是否符合 。
每次 尋找有多少的 且 以及 且 ,並將兩者相乘即是以 為中間的三元逆序數對數量,只要枚舉所有的 並加總即可。
有了 Subtask 2 的想法後,可以將其改良,利用 merge sort 計算對於每個數字有多少比自己大的數字在前面,多少比自己小的數字在後面,最後相乘加總即可。
註:因為 到 ,所以需離散化。
假設有點 , 和 相連,但 都沒有和 相連,那麼就得把這些 給加進圖裡 (有 的這個圖)
換句話說,所有含有這種 的連通塊,要和其他連通塊相連形成和諧的連通塊
例如圖中有這 5 個連通塊:
那麼 1 號連通塊滿足上述性質(不和諧),所以從小到大要把 這幾個數字納入 1 號連通圖
接著圖就會變成:
這樣整個圖就和諧了。
實作上會採用 Union-Find forest 作為不同連通塊之間的判斷
首先一個個數字 去檢驗,含有 的連通塊,是否和諧?
也就是對於當前 到該連通塊中最大的數 中所有 ,判斷 是否在連通塊中,不在的話就把 加進去 (加 1 條邊)
mx[Find(l)]
為含有 的連通塊中的最大數,也就是
如何維護連通塊中的最大數請參考標準程式
實作的概念大致上是這樣,可是複雜度還是過高
但可以觀察到:
已經把 1 號連通塊和諧了,那麼下個數就挑 (1 號中最大數 的下個數)
然後嘗試把含有 的 2 號連通塊和諧
雖然它早已和諧
Image Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
也就是說若含 的連通塊已和諧,則下個欲選擇的連通塊可挑含 連通塊中最大數的下個數:
明顯的,在加入一條邊之後或多或少會讓最短路更短
也就是說,只需關心當最短路徑用了新加的邊的狀況
那麼設此邊為 則要讓 盡量長,
而路徑是 或
這裡 是 到 的最短路徑
設 為 的長度
則 的長度就是
若最短路徑是
則長度會有
而任意特殊點對(邊) 都得滿足此不等式,也就是例如有點對
會有三個不等式要滿足,假設為
在特殊點為三個以上,就不會出現等於關係了
會發現這些不等式能化簡成
再化簡
會發現得得到矛盾的結論
所以須從確定的結論往前推,不失一般性的,設有
則回推的不等式為
所以要比較這三者的大小
推廣至一般狀況,若是
則可只比較所有 其中
同樣只關心有加入新邊的情況
設特殊點 滿足 有雙向邊 ,則有三種情況需考慮﹔
由上推得
所以特殊點依照 BFS 的深度排列,比較所有 其中 得解