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

今天90+100+50=240

還不錯。

第一題：4809. 【NOIP2016提高A組五校聯考1】挖金礦

本想着用dp，先将第一層的必須選了，然後設f[i]表示選i個數的最大價值，最後答案就是MAX{ ( sum+f[i] ) / ( i+n ) }。但是發現這樣時間是O(n^2m^2)的，想了很久終于看到平均值就想到了二分答案，然後将每個數減去平均值，最後隻要選出若幹個數看看總和是否大于0即可。

第二題：4810. 【NOIP2016提高A組五校聯考1】道路規劃

我們發現要符合題目必須第一行選的數的順序和第二行是恰好相反的，是以我們将第二行的數編号後對應到第一行做一遍最長不下降子序列即可。

第三題：4811. 【NOIP2016提高A組五校聯考1】排隊

多種解法。

有一點要發現的是，每個點的優先級是确定的，是以我們先處理出來。

對于第一問可以用連結清單找到前x個未打标記的數并打上标記，第二問跳倍增找到目前點到根節點的路徑中最上面一個被打标記的點，然後直接将它變為0。最後我們記錄一個head，表示每次跳連結清單時的起始位置，若修改的點在head前面，那麼就将head變為修改的點的位置，否則就跳head直到next[head]>x>head，然後将x和前後的連結清單接起來，最後将head變回原先的位置即可。

對于修改的數如果不多是沒事的，如果多的話未打标記的數就會少，是以總時間複雜度是能過的。

第一題精度問題沒有拿滿分，需要注意。

第三題沒有想到，還需努力。