CCPC江西省賽賽后補(bǔ)題

獨(dú)立思考！

A.

題目大意:給你兩棵樹，讓你用一條邊連起來使得\sum_{i=1}^n \sum_{j=i+1}^n dist(i,j)最小化。

題目思路：畫幾張圖容易猜到：連接兩樹的重心能夠使得上式最小化。所以找兩遍重心。再考慮每條邊的經(jīng)過的貢獻(xiàn)即可。

H.

題目大意：一個(gè)線段[1,n].隨機(jī)選出一個(gè)點(diǎn)當(dāng)作右端點(diǎn)R，再從[1,R]選出一個(gè)點(diǎn)當(dāng)作左端點(diǎn)。?

由上述過程得到獨(dú)立的兩個(gè)線段。問你兩個(gè)線段相交的概率(n<=1e6)

題目分析：

肯定是枚舉第一條線段的右端點(diǎn)。假設(shè)選出了第一條線段[L1,R1].第二條線段相交的情況有兩種:

①\ R2 ∈ [L1,R1].

②\ \ R2∈[R1+1,n] 且 L2∈[1,R1]

枚舉右端點(diǎn)R1，即假設(shè)它是已知值:

對于①:?ans1= \frac{1}{n*R1} \sum_{i=R1}^{1}\frac{R1-i+1}{n}=\frac{sum[1...R1 ]}{n^2*R1}

對于②:ans2= \frac{1}{n} \sum_{i=n}^{R1+1}\frac{1}{n*i}=\frac{inv\_sum[R1+1...n]}{n^2}

所以提前預(yù)處理前綴和，逆元前綴和。對于每組數(shù)據(jù)：O(n)解決..

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容