A. 字符串重組

給定一個(gè)字符串，判斷能不能經(jīng)過(guò)重排序編程 "Baidu".

思路：把輸入的字符串和 "Baidu" 都排序一下再比較，相等就可以，不相等就不行。

B. 構(gòu)造字符串

給定一個(gè)數(shù) x，要用 r，e，d三種字符構(gòu)造一個(gè)字符串，它的回文子串的數(shù)量恰好為 x, 要求字符串的長(zhǎng)度小于??.而 x 的范圍是?

思路：不難發(fā)現(xiàn)，如果用 red 為循環(huán)節(jié)，構(gòu)造出來(lái)的字符串中，即形如 redredred....，任意長(zhǎng)度大于等于 2 的子串都不是回文字符串，因此，回文字符串只有單個(gè)字符組成的子串，此時(shí)字符串的長(zhǎng)度就是回文子串的數(shù)量。因此，對(duì)于 x 小于? 的輸入是非常簡(jiǎn)單的，只需要用 red 循環(huán)拼出一個(gè)長(zhǎng)度為 x 的字符串即可。

對(duì)于 x 更大的情況，簡(jiǎn)單考慮，多個(gè)重復(fù)字符組成的字符串的回文子串?dāng)?shù)量比較好算，而且數(shù)量增加也比較快，因此考慮優(yōu)先使用相同字符。設(shè)? 為長(zhǎng)度為 n 的全為 d 字符組成的字符串的回文子串?dāng)?shù)量，,?. 由于輸入最大是?, 大概 n 為??以下 就能覆蓋輸入的范圍。因此先預(yù)處理出?, 然后二分找出比 x 小的最大的?, 答案的前半部分就是? 個(gè) d, 而后半部分就比較小了，交給 x 小于? 的情況來(lái)解決。

C. 樹(shù)上同色連通塊

現(xiàn)在有一顆樹(shù)，n 個(gè)節(jié)點(diǎn)，樹(shù)上的節(jié)點(diǎn)染成紅色或者藍(lán)色，定義邊的權(quán)值為，刪除該邊后兩個(gè)子樹(shù)中同色連通塊的大小之差的絕對(duì)值，要求所有邊的權(quán)重之和。

思路：

用? 表示以 i 節(jié)點(diǎn)為根的子樹(shù)中的同色連通塊數(shù)量，則：, 其中 j 是 i 的子節(jié)點(diǎn)。 可以自底向上地求出。

求完? 之后自頂向下地求出答案 ans, 從根節(jié)點(diǎn)開(kāi)始，每次向下遞歸的時(shí)候計(jì)算對(duì)應(yīng)的邊的貢獻(xiàn)：.