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

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

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

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

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

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