國家集訓隊作業(yè)出題互測解題報告almost

1、近似平均數(shù)【題意簡述】n Xin (n 1) 的近似平均數(shù)為 i1定義 n 個數(shù)n 1對于給出的長度為 N 的一個序列 A，要求回答Q 個詢問。每個詢問會給出 L, R(1L R b (L a b N)，請找出 a 與R) 使得Aa , Aa1 , . ,Ab的近似平均數(shù)最大。N 105 , Q 3104【算法分析】算法一：對于每一次詢問，枚舉 a 與 b，通過預處理的前綴和計算 Aa Ab 的近似平均數(shù)更新答案。時間復雜度： O(QN 2 )期望得分：10 15算法二：可以事先計算出每一組(a, b) 的由于一些測試點的 N 比較小，計為f ab ， 再通 過動態(tài) 規(guī)劃 得到每 一組 (L,

2、 R) 的gLR ， 轉移 方程 式為 gij=max(gi+1j,gij-1,fij)，該算法可以O(1) 回答所有詢問，但需要 N 2 的空間。時間復雜度： O(N 2 Q)期望得分： 25 35算法三：在算法一中，為了求得最優(yōu)的(a, b)要枚舉它們兩個量，這一點似乎是很不優(yōu)的，1重復查詢了很多已知的信息，有沒有辦法減少枚舉其中的一個呢？是肯定的，這也正是這個問題的關鍵所在，當左界（或右界）確定的時候，范圍內查詢出最優(yōu)的右界（或左界）。可以使用高效的辦法在某個i設 A 序列的前綴和序列為 S，即Si Aj ，把(i, Si ) 看成一個二維坐標系中的點，j 1當左界 a 確定時，在x,

3、y的范圍內尋找最優(yōu)的 b，實際上也就是尋找最優(yōu)的() 使得(a, Sa1 ) 與它的連線斜率最大。這樣一來問題就不那么難辦了，如果能夠事先建立起x, y內的一個凸殼，就可以直接用二分的方法查詢最優(yōu)的右界了。綜上得到了一個較為高效且所需空間很少的算法，對于一組詢問(L, R) ，從 R 開始到 L 為止不斷加入其對應的點，并凸支持查詢操作，用所有查詢中得到的最優(yōu)值作為。時間復雜度： O(QN log N )期望得分： 35 45算法四：嘗試將算法二與算法三融合起來。在算法二中，單次詢問的回答時間可以達到O(1) ，之所以這么快是因為做了很多預處理操作，花了大量的空間來這些預處理計算出的值，但隨著

4、問題規(guī)模的增大，再也無法花費如此多的時間預處理出所有的東西，也沒有足夠的空間將計算出的東西保存下來。但是仔細想想，真的需要事先知道那么多東西嗎？還是可以通過適量地增加查詢的時間來得到一個完美地平衡呢？對，分塊在這里派上用場了，把整個序列 A 均勻地分成T 段，每一段的長度Len N 。以每兩段的分界點為起點，分別往左和往右使用算法三，T可以求得所需要預處理出的 f i j，表示(L, R) (i, jLen) 或( jLen,i) 時的。對于一次查詢(L, R) ，如果 L 與 R 分在了一塊，可以直接用算法三處理，否則我們可以用預處理的 f 解決一大部分問題。若最優(yōu)的(a, b) 滿足a L

5、en ，那么可以通 Len L過 f R 得到 Len L；若最優(yōu)的 (a, b) 滿足 b RL e n， 那么可以通過 L e nf L 得 到，即 Ans M ax f R, f L 。但是當然不可忽RLR Len Len Len 2IOI2012 國家集訓隊作業(yè) almost 解題中學視的是，當最優(yōu)的(a, b) 滿足a 與 L 分在一塊并且 b 與 R 分在一塊時還沒有納入計算，事實上解決方法也很簡單， 再利用算法三建立出 Len R 的凸殼， 枚舉 R Len L LL e n的每個位置作為左界求出最優(yōu)右界更新就行了。 L e n最后，來考慮一下算法的復雜度，預處理部分由于分出了 T 塊，所以總共要往左NT右做 T 次算法三，復雜度為O(TN log N) ；而詢問部分由于每一塊的長度 Len ，因此NQ logNNQN) 。算法總的復雜度為 O( TN )