创建一个哈夫曼树，不同的是一个节点可以有kkk个子节点，并且根节点没有任何编码。 考虑我们构造编码的过程，每次可以选择kkk个子树，将它们合并为一个大的树，并且给子树们的根节点编号钦定为0,1,...k−10,1,...k-10,1,...k−1，此时每个子树深度增加111，这棵树的深度变为max⁡(maxdep(subtreei))+1\max(maxdep(subtree_i))+1m...

传送门 注意到题目条件如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。 不妨考虑对树的节点进行一些安排，使得我们按照dfsdfsdfs顺序找到的第一个点就是球落到的点。 不要考虑编号最小的节点在的方向，而是考虑从一个点下落的时候，他会选择哪一条边，使得这条路径可以到达编号最小的点。 没错，假设现在的节点是uuu，它的子节点为vvv，它选择的路径就是子树最小值最小的vvv 于是...

传送门 强烈谴责出题者，题面都花了好几分钟读。 题意： 给你Ai\\{ A_i\\}Ai​，让你从集合S={x∣x=∑k=ijA[k],j−i+1∈[L,R]}S=\{x|x= \sum _{k=i} ^{j} A[k] , j-i+1 \in[L,R] \}S={x∣x=∑k=ij​A[k],j−i+1∈[L,R]}选出kkk个数，使他们的和尽可能大。 首先考虑一件事，如何表示[i,j]...

传送门 如果是一条链，我们将这条链从111节点提起来，显然我们不能选择同时选择左半部分或者右半部分的两个点放在一组，于是我们有如下思路：左半部分的点和右半部分的点两两配对，剩下的点（包括111）自成一组。 考虑如何使结果最小，肯定是左半部分最大值和右半部分最大值配对，第二大值互相配对，第三大值互相配对…… 正确性怎么证明，考虑我们把x1,y1x_1,y_1x1​,y1​和x2,y2x_2,y...