2021.07.09【NOIP提高B組】模拟 總結

第一題：找規律題，首先把在同一個大三角形的點轉化。然後答案為經過第三個三角形或者不經過。發現跟二的次幂有關系。

第二題：我的做法：設 f i f_i fi​表示前 i i i個字元構成的最短文本長度。有轉移 f i = f j + k + i − j k ( k ∣ ( i − j ) ) f_i=f_j+k+\frac{i-j}{k}(k|(i-j)) fi​=fj​+k+ki−j​(k∣(i−j))。優化一下，用哈希判重。時間複雜度可以做到 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn)。還可以設 f i , j f_{i,j} fi,j​表示以 i i i為結尾的串 i − j + 1 i-j+1 i−j+1到 i i i的最短壓縮答案。轉移可以用 g g g維護，時間 O ( n 2 ) O(n^2) O(n2)。

第三題：疊代加深啟發式搜尋。注意幾點優化：估值函數，考慮優化左上方的聯通塊，每次不遞歸上面。時間複雜度玄學。

第四題：考慮用線段樹維護三個值 l , r , s u m l,r,sum l,r,sum，分别表示區間從左/右開始的最長空連續段和區間的最長空連續段。

pushup

時分類讨論一下，查詢時先看左子樹再看中間最後看右子樹。注意：懶标記用完後要清空。