今天刚好笔试有编程题，CF 就先摸了，记一下笔试的除了签到题之外的题。

A 不知道题目叫什么1

给定一个二叉树，有 n 个节点，现在要给二叉树的节点赋值上 1 到 n 的值，且两个节点之间的值不能相同，要求奇数层的和与偶数层的和的差的绝对值小于等于1，给出一个合法的赋值方案，如果不存在合法的赋值方案，返回空树。

思路：

笔试的时候想了一个错的思路，现在还没什么头猪，先摸了，这几天事情实在太多了，过几天有空想想。

B 不知道题目叫什么 2

假设我们有一个由小写字母组成的字符串 s，现在定义它的权值为：字符串 s 中包含的字符的种类数量乘以字符串的长度，比如，字符串 “ababa” 的权值为：2 * 5 = 10. 现在要把一个字符串 s 切割为 k 个子串，要求所有切割方案中这 k 个子串的权值的最大值最小是多少。其中字符串 s 和子串段数 k 是给定的，s 的长度小于

思路:

求最大值的最小，一眼二分。单调的性质是: 对于给定的 k ，如果某个值 maxVal 可以使得字符串 s 存在一个最大子串权值小于等于 maxVal 的切割方案，那么比 maxVal 更大的值也可以满足这个性质。

那么接下来只需要设计一个方法判定对于一个给定的 maxVal 和 k，是否存在满足最大子串权值小于等于 maxVal 的 k 段切割方案。这可以通过实际上对字符串 s 进行一次所有子串权值都小于 maxVal 的切割操作，再比较这样切割出来的子串个数是否小于等于 k 来实现，因为如果能够用更少的段数完成合法的切割，用 k 段切出来的最大权值肯定也是小于等于 maxVal 的。

一次 check 是线性复杂度，因此这么做二分的复杂度是 ，对于 5e5 的数据范围是可以接受的。