hw2出題互測幾乎平均數(shù)almost

1、幾乎平均數(shù)almost【題意簡述】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，通過預(yù)處理的前綴和計算 Aa Ab 的幾乎平均數(shù)更新答案。時間復(fù)雜度： O(QN 2 )期望得分：10 15算法二：可以事先計算出每一組(a, b) 的由于一些測試點的 N 比較小，計為f ab ， 再通 過動態(tài) 規(guī)劃 得到每

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

3、是，在x, y的范圍內(nèi)尋找最優(yōu)的 b，實際上也就是尋找最優(yōu)的() 使得(a, Sa1 ) 與它的連線斜率最大。這樣一來問題就不那么難辦了，如果能夠事先建立起x, y內(nèi)的一個凸殼，就可以直接用二分的方法查詢最優(yōu)的右界了。綜上得到了一個較為高效的方法且所需空間很少的算法，對于一組詢問(L, R) ，從 R 開始到 L 為止不斷加入其對應(yīng)的點，并凸支持查詢操作，用所有查詢中得到的最優(yōu)值作為。時間復(fù)雜度： O(QN log N )期望得分： 35 45算法四：算法三中的優(yōu)化經(jīng)做到極限了，目測至少需要枚舉兩個邊界中的一個？我想應(yīng)該是否定的（人類的智慧是無窮的），但是請恕筆者愚鈍，我沒能想出一個不用枚舉邊

4、界的更好的算法，而是借鑒了算法二的一點思路來解決這道問題。在算法二中，單次詢問的回答時間可以達到O(1) ，之所以這么快是因為做了很多預(yù)處理操作，花了大量的空間來這些預(yù)處理計算出的值，但隨著問題規(guī)模的增大，再也無法花費如此多的時間預(yù)處理出所有的東西，也沒有足夠的空間將計算出的東西保存下來。但是仔細想想，真的需要事先知道那么多東西嗎？還是可以通過適量地增加查詢的時間來得到一個完美地平衡呢？對，分塊在這里派上用場了，把整個序列 A 均勻地分成 n 段，每一段的長度也是n 。對于分出的每一段，事先根據(jù)算法三求好凸包，再枚舉序列中的每一個位置作為左界（右界）求出右界（左界）在這一段時的最優(yōu)取值，接下來

5、用做一次類似算法二中的動態(tài)規(guī)劃，即可求得最終所需要預(yù)處理出的 f i j ，表示(L, R) (i, j n ) 或( j n, i) 時的。對于一次查詢(L, R) ，如果 L 與 R 分在了一塊，可以直接用算法三處理，否則我們可以用預(yù)處理的 f 解決一大部分問題。若最優(yōu)的(a, b) 滿足a L n n ，那么可以通過2 L R R ；若最優(yōu)的(a, b) 滿足b f R 得到 n n ，那么可以通過 f L n 得n L R 到，即 Ans M ax f R, f L。但是當然不可忽視的是，當最優(yōu)的 n n (a, b) 滿足 a 與 L 分在一塊并且b 與 R 分在一塊時，還沒有納入計算，事實上解決方法 R L n n R 的凸殼，枚