補(bǔ)題鏈接：http://oj.eriktse.com/contest.php?cid=1001

比賽信息

ETOJ的第一場周賽，整體難度偏低，適合基礎(chǔ)薄弱的同學(xué)。

獎勵：第一名一個月大會員。

出題人：eriktse

驗(yàn)題人：Jakon

QQ交流群：600240150

A 帶余除法

簽到語法題。

B 這也能隨機(jī)？

把每一個數(shù)字分解后計(jì)算數(shù)位出現(xiàn)次數(shù)即可，注意特判。

C 最大子段和

模板題，dp。

dp[i]表示到i為止，且以i結(jié)尾的最大子段和，可以從dp[i - 1]轉(zhuǎn)移過來，當(dāng)轉(zhuǎn)移過來比0還小，就單獨(dú)成為一個子段。

因?yàn)檫@個轉(zhuǎn)移過于簡單，所以可以直接用一個變量保存。

下面用兩種寫法：

寫法一：

寫法二：

D 聯(lián)通塊問題（1）

并查集模板，計(jì)算每個點(diǎn)對祖先的貢獻(xiàn)即可。

E 小e的書架

有兩種思路來做這題。

思路一：根據(jù)貪心選擇性質(zhì)，顯然應(yīng)該優(yōu)先橫著放，最后一部分選擇豎著放或橫著放。特判“只能橫著放”的情況。對于每種情況，可以直接計(jì)算出所需的最小書架長度。

當(dāng)時，只能橫著放，假設(shè)有$x$個長度為$h$的空間，則有：

故總長度需要滿足：

當(dāng)時，可以選擇全部橫著放，也可以選擇將最后一部分豎著放，類似的分析即可，具體看代碼。

思路二：

二分，確定一個長度后，判斷是否能夠放得下本書。雖然復(fù)雜度不如前一種方法，但是思想值得學(xué)習(xí)。