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

第一題：把所有質數找出來，然後兩兩乘一下，用字首和即可。歐拉篩：設目前第 j j j個質數為 p j p_j pj​，則當 i ≡ 0 ( m o d    p j ) i\equiv 0(\mod p_j) i≡0(modpj​)時，就不用再篩了。原因： i p j + 1 ≡ 0 ( m o d    p j ) ip_{j+1}\equiv0(\mod p_j) ipj+1​≡0(modpj​)，是以這個數在用 p j p_j pj​篩時就已經被篩了。因為每個數被篩一次，是以時間 O ( n ) O(n) O(n)。

第二題：一個貪心：任意相鄰的兩個企鵝比對是最優的。是以我們先求出最多能有多少個組比對，假設為 x x x，如果 2 x ≥ k 2x\geq k 2x≥k，說明我們直接放就行了，答案為 ⌈ k 2 ⌉ \lceil\frac k 2\rceil ⌈2k​⌉。否則我們就把剩下的繼續放，就是 x + ( k − 2 x ) x+(k-2x) x+(k−2x)。比對的求法：可以貪心，從下往上，遇到沒有比對的就直接比對；也可以動态規劃，設 f i , 0 / 1 f_{i,0/1} fi,0/1​分别表示目前子樹的答案（這個節點選還是不選）。轉移的話也是沒有比對就比對。

實話說這道題目考察了動态規劃和貪心。

第三題：狀壓一下，跑一遍搜尋或者 S P F A SPFA SPFA。時間是一樣的。

第四題：有一個貪心：從小到大周遊，我們從左到右找到一合法位置，從右到左找到一個合法位置（合法位置指的是滿足是第 b + 1 b+1 b+1個空位，因為空位的都是比它大的，空位沒放）。然後看一看哪個比較小即可。用資料結構優化，因為空位個數是遞增的，是以二分就行了。因為要查詢加二分，是以大概就是 O ( n ( log ⁡ 2 n ) 2 O(n(\log_2^n)^2 O(n(log2n​)2。

這一題這個貪心思路要仔細想一想。