A. Valera and Plates

 

題意: Valera 要吃東西,吃 A 時用bowl , 吃 B 時可用bowl/plate 。一開始n 個 bowl 和 m 個 plate 。如果沒有餐具 Valera

 

就要洗餐具,一次只能洗一個。問 Valera 最少要洗幾個。

 

題解: 吃 A 只能用 bowl ,所以先將 bowl 用完。因為 A只能用  bowl ,不夠的話,就要洗。 若還剩下 nb 個 bowl 可留下來裝 B。

 

接下來考慮 B 的情況,若 m + nb 大於 B 的使用量,就不用洗,若小於,就要洗差值。

 

B. Valera and Contest

 

題意: 有 n 個數,已知前 k 大的數合是 sk ,總合是 sn。每個數字一定是在[l,r] 這個範圍。

 

現在想要還原符合條件的n 個數各是多少?

 

題解: 用到平均數的概念, 前 k 大每個數至少是 sk/k ,(sk%k) 個數在加 1。同樣的道理也用在後 (n-k)個數。

 

C. Valera and Elections

 

題意: 有 n 個 district , n - 1 個 road 去連接,這 n 個 district 形成一個 tree  。 road 的 type 分

 

成2種,一種是 good road ,另一是 bad road 。現在有 n 個 candidate 要參與競選,若 ni 當選,則

 

他會去修 district i 到 district 的 road 。問最少幾個人當選,可以讓所有的 road 都修好?

 

題解:將 district 1 當成 root ,接下來可以有以下推論:

 

 f( i ) = 

1. if edge (i,neighbor(i)) is bad 

      A. f(neighbor(i) ) > 0 then add f(neighbor(i))。

      B. f(neighbor(i) ) =  0 then add 1.

2. add f(neighbor(i))

 

文章標籤
全站熱搜
創作者介紹
創作者 lettice0913 的頭像
lettice0913

斑的家

lettice0913 發表在 痞客邦 留言(0) 人氣(3)