LCP 72. 補(bǔ)給馬車

【模擬】O(n^2)模擬，當(dāng)數(shù)組長(zhǎng)度大于一半長(zhǎng)度時(shí)，遍歷數(shù)組，找到最小的相鄰的兩個(gè)元素，把總和賦給第一個(gè)，刪掉后一個(gè)，重復(fù)操作直到滿足要求。時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)。

LCP 73. 探險(xiǎn)營(yíng)地

【哈希表 + 遍歷】用哈希表存探測(cè)過(guò)的營(yíng)地，遍歷的時(shí)候記錄探測(cè)到最多新?tīng)I(yíng)地時(shí)的下標(biāo)。

LCP 74. 最強(qiáng)祝福力場(chǎng)

【離散化 + 二維差分】①統(tǒng)計(jì)所有左下和右上坐標(biāo)，由于會(huì)出現(xiàn) 0.5，可以將坐標(biāo)乘 2。②離散化橫縱坐標(biāo)。③二維差分。④復(fù)原，計(jì)算最大值。

【離散化 + 掃描線 + 線段樹(shù)動(dòng)態(tài)開(kāi)點(diǎn)】用二維平面的掃描線算法實(shí)現(xiàn)，首先將每個(gè)力場(chǎng)看做矩形，并按照其左右邊緣的 x 坐標(biāo)排序。接著使用 set 存儲(chǔ)所有可能的 y 坐標(biāo)，并按照從小到大的順序排序，得到所有可能的 y 坐標(biāo)。然后遍歷排好序的力場(chǎng)列表，對(duì)于每個(gè)力場(chǎng)矩形，將其左右兩個(gè)邊界加入線段樹(shù)中。注意，由于力場(chǎng)范圍的邊緣也被力場(chǎng)覆蓋，因此需要將左邊界的值減 1，將右邊界的值加 1。最后，遍歷完所有力場(chǎng)后，從線段樹(shù)中找到最大的值即為答案。

LCP 75. 傳送卷軸

【預(yù)處理 + BFS + DFS + 二分】①遍歷找到起點(diǎn)終點(diǎn)位置；②BFS計(jì)算終點(diǎn)到其余點(diǎn)的最短距離；③剪枝：如果起點(diǎn)到不了終點(diǎn)返回-1；④二分答案maxDis，看能否在被傳送的情況下在maxDis步內(nèi)到達(dá)終點(diǎn)，只要能到達(dá)終點(diǎn)，說(shuō)明答案至多為maxDis，否則答案大于maxDis。

LCP 76. 魔法棋盤

【狀壓DP + 記憶化搜索】分類討論有七種B/R狀態(tài)——TRANS，遍歷棋盤就是不斷生成B/R序列的過(guò)程，向序列末尾添加B和R，這些狀態(tài)就會(huì)互相轉(zhuǎn)換，形成一個(gè)7×2的轉(zhuǎn)換關(guān)系表，7種情況用3個(gè)bit存。寫(xiě)一個(gè)記憶化搜索枚舉r行，再寫(xiě)一格暴搜來(lái)枚舉第r行的B/R狀態(tài)是否合法。