今天剛好筆試有編程題，CF 就先摸了，記一下筆試的除了簽到題之外的題。

A 不知道題目叫什么1

給定一個二叉樹，有 n 個節(jié)點(diǎn)，現(xiàn)在要給二叉樹的節(jié)點(diǎn)賦值上 1 到 n 的值，且兩個節(jié)點(diǎn)之間的值不能相同，要求奇數(shù)層的和與偶數(shù)層的和的差的絕對值小于等于1，給出一個合法的賦值方案，如果不存在合法的賦值方案，返回空樹。

思路：

筆試的時候想了一個錯的思路，現(xiàn)在還沒什么頭豬，先摸了，這幾天事情實在太多了，過幾天有空想想。

B 不知道題目叫什么 2

假設(shè)我們有一個由小寫字母組成的字符串 s，現(xiàn)在定義它的權(quán)值為：字符串 s 中包含的字符的種類數(shù)量乘以字符串的長度，比如，字符串 “ababa” 的權(quán)值為：2 * 5 = 10. 現(xiàn)在要把一個字符串 s 切割為 k 個子串，要求所有切割方案中這 k 個子串的權(quán)值的最大值最小是多少。其中字符串 s 和子串段數(shù) k 是給定的，s 的長度小于

思路:

求最大值的最小，一眼二分。單調(diào)的性質(zhì)是: 對于給定的 k ，如果某個值 maxVal 可以使得字符串 s 存在一個最大子串權(quán)值小于等于 maxVal 的切割方案，那么比 maxVal 更大的值也可以滿足這個性質(zhì)。

那么接下來只需要設(shè)計一個方法判定對于一個給定的 maxVal 和 k，是否存在滿足最大子串權(quán)值小于等于 maxVal 的 k 段切割方案。這可以通過實際上對字符串 s 進(jìn)行一次所有子串權(quán)值都小于 maxVal 的切割操作，再比較這樣切割出來的子串個數(shù)是否小于等于 k 來實現(xiàn)，因為如果能夠用更少的段數(shù)完成合法的切割，用 k 段切出來的最大權(quán)值肯定也是小于等于 maxVal 的。

一次 check 是線性復(fù)雜度，因此這么做二分的復(fù)雜度是 ，對于 5e5 的數(shù)據(jù)范圍是可以接受的。