散文網(wǎng) » 科技 »學(xué)習(xí) » [AtCoder is All You Need]ABC 276 F - Solution

[AtCoder is All You Need]ABC 276 F - Solution

2022-11-05 22:52 作者:故寓諸無(wú)竟 0人讀過(guò) | 我要投稿

我加了一個(gè)假問(wèn)題

問(wèn)題簡(jiǎn)述

????????給定一個(gè)長(zhǎng)為 $n$ 的序列 $a$ 。考慮其前綴序列 $a_%7B1%5Csim%20i%7D$ ，從中放回地隨機(jī)抽樣兩次，記這兩次所得元素的最大值的期望為 $b_i$ 。求整個(gè)序列 $b$ 。

????????原題目鏈接：https://atcoder.jp/contests/abc276/tasks/abc276_f

思路1

????????最開(kāi)始不知道為什么，認(rèn)為只需要求 $b_n$ 。這樣的話隨便怎么亂搞都可以，所以我直接求了分布函數(shù)（，如果 $Z%3Dmax%5C%7BX%2CY%5C%7D$ ，那么 $F_Z(z)%20%3D%20F_X(z)%20F_Y(z)$ 。不出意外各大高校概率統(tǒng)計(jì)都會(huì)說(shuō)這個(gè)。這里由于 $X$ 和 $Y$ 是同一個(gè)分布，所以 $F_Z(z)%20%3D%20F_X%5E2(x)$ ），然后直接 $E%5BZ%5D%20%3D%20z%5Cbar%7BF%7D_Z(z)$ ，就得到了一個(gè)優(yōu)秀的 $O(%5Cmax%5C%7Ba%5C%7D-%5Cmin%5C%7Ba%5C%7D)$ 的算法（指算 $b$ 的一個(gè)元素，所以總共是 $O(n(%5Cmax%5C%7Ba%5C%7D%20-%20%5Cmin%20%5C%7Ba%5C%7D))$ ，太高了）。

思路2

????????然后意識(shí)到不對(duì)勁。

????????事實(shí)上， $b_i$ 可以寫(xiě)成和 $a$ 下標(biāo)相關(guān)的表達(dá)式：

$b_i%20%3D%20E%5BZ%5D%20%3D%20%20%5Cfrac%7B1%7D%7Bi%5E2%7D%20%5Csum_%7Bj%3D1%7D%5Ei%20%5Csum_%7Bk%3D1%7D%5E%7Bi%7D%20%5Cmax%20%5C%7Ba_j%2Ca_k%20%5C%7D%20$

????????通常面對(duì)這種表達(dá)式，考慮兩個(gè)期望之間的差異比較合適，不難得到：

$b_i%20%3D%20%5Cfrac%7B(i-1)%5E2%7D%7Bi%5E2%7Db_%7Bi-1%7D%20%2B%20%5Cfrac%7B1%7D%7Bi%5E2%7D%20%5Cleft(%202%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%5C%7B%20a_j%2Ca_i%20%5C%7D%20%2B%20a_i%20%5Cright)$

????????快速計(jì)算上式的瓶頸在于 $2%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%20%5C%7B%20a_j%2Ca_i%20%5C%7D$ 項(xiàng)，不難想到分成過(guò)大和過(guò)小的兩部分計(jì)算：

$2%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7D%20%5Cmax%5C%7B%20a_j%2C%20a_i%20%5C%7D%20%3D%202%5Cleft(%20a_i%20%5Ccdot%20%7C%5Cmathcal%7BG%7D(i%2Ca_i)%7C%20%2B%20%20%5Csum_%7Bj%3D1%2Ca_j%5Cge%20a_i%7D%5E%7Bi-1%7Da_j%20%5Cright)$

????????其中 $%5Cmathcal%7BG%7D%20(i%2Ca_i)%20%3D%20%5C%7B%20j%20%7C%201%5Cle%20j%20%3C%20i%2C%20a_j%20%3C%20a_i%20%5C%7D$ 。一部分是比 $a_i$ 小元素的數(shù)目，一部分是比 $a_i$ 大的元素的和。

????????臨場(chǎng)想了一下，能不能繞過(guò)數(shù)據(jù)結(jié)構(gòu)，但最終還是繞不過(guò)去。我選擇了線段樹(shù)，當(dāng)然Fenwick樹(shù)（樹(shù)狀數(shù)組）也可以。時(shí)間復(fù)雜度為 $O(n%20%5Clog%20%5Cleft(%20%5Cmax%5C%7Ba%5C%7D%20-%20%5Cmin%5C%7Ba%5C%7D%5Cright))$ 。

后記

????????本場(chǎng)的實(shí)況錄制地址：https://www.bilibili.com/video/BV1dR4y1f7z9

????????做簡(jiǎn)單題目一卡一卡的，希望未來(lái)會(huì)更好；希望未來(lái)不要看錯(cuò)題。

標(biāo)簽：