cff_0102 @ 2024-03-03 13:24:51
t1 有一个2的n+1次方-1个节点（也就是深度为n+1）的完全二叉树，每个叶子结点有一个数（组成2的n次方的排列），每个非叶子节点有一个花费，可以让它从1类点变成2类点。刚开始所有都是1类点，A可以选择总花费不超过m的若干个点让它们变成2类点，接着B要遍历这个二叉树，对于二类点，只能先遍历左儿子再遍历右儿子，对于一类点，可以先左后右也可以先右后左，按遍历到的顺序将叶子结点的值拼起来得到一个序列，B要尽量让它字典序小，A要尽量让它大，两人绝顶聪明，问最后的序列是什么
by CHEN08_94 @ 2024-03-03 13:30:29
《绝顶聪明》
by bengshakala1 @ 2024-03-03 13:36:05
md我花2h写了贪心,dfs没打出来,鬼东西还是多测...还有救么
by 加载中…… @ 2024-03-03 13:40:15
我当背包做打了三个小时的dp（显然tle了）
by bengshakala1 @ 2024-03-03 13:49:10
爆搜那可得O(
by _Ch1F4N_ @ 2024-03-03 13:50:10
@cff_0102 贪心加 dp
by Iniaugoty @ 2024-03-03 13:56:19
@ChiFAN 大佬详细说说？我是这样想到了一个贪心+DP做法但是写挂了，我以为假的
同时对不起，手机端太小了，一开始“回复”点到“举报”上面了
by _Ch1F4N_ @ 2024-03-03 14:01:36
@gty314159 细节有点多，一时半会可能不好说，我考场上到 12:20 过得大样例
by 262620zzj @ 2024-03-03 14:58:15
@ChiFAN 是优化掉K？
by _Ch1F4N_ @ 2024-03-03 15:01:28
@262620zzj 这个部分直接贪心选，因为是字典序
by XZhuRen @ 2024-03-03 15:04:41
叠甲： 我考场上没调完（初三生退役四个月打比赛连链式前向星都忘了），但是我觉得我思路没问题：
参考简单分治（线段树）的模板，易发现：每一个节点，对应的叶子节点是一个区间（这不是废话吗）
所以预处理：记对于每一个节点开一个vector名为mm，mm[i][j]表示：在节点i,使权值为j的节点，能第一个被Bob访问，在此子树中需要花费的最少权值和（如果大于k或不可能就不记）。通过树形DP求解，利用归并排序+前缀和优化。
然后有一个dfs(r,now),表示当前在r节点，要去取权值为now的叶子。易发现，now必须取能取的之中最大的now，才能使Alice满意。所以在向左右叉的过程中，不断遍历当前节点到下一个子树，下一个能取的now最大值（注意判断花费），继续进行DFS。这一段是DFS+分类讨论解决。（注意如果花费的可以使上一个点取消花费需要重减去权值）
DFS过程中每到达一个叶子就输出。
轻喷