Description

给一棵 $n+1$ 层的完全二叉树（共 $2^{n+1}-1$ 个结点，$2^n$ 个叶子），结点从上到下，从左到右编号为 $1\sim 2^{n+1}-1$，每个非叶结点有一个激活代价 $w_i$，每个叶子有一个权值 $q_i$，所有 $q_i$ 构成 $1\sim 2^n$ 的排列。Alice 和 Bob 在这棵树上玩游戏，Alice 可以用不超过 $K$ 的代价激活一些结点，随后 Bob 会对这棵树进行 dfs。对于 Alice 激活的结点，Bob 必须先走左儿子再走右儿子；其余时候，Bob 可以任意决定 dfs 顺序。

按照 Bob 访问叶子的顺序将所有 $q_i$ 排成序列 $Q$，Alice 希望 $Q$ 的字典序最大，Bob 希望 $Q$ 的字典序最小，问最终的 $Q$ 是什么。

$T$ 组数据。

$1\le T\le 100,1\le n\le 16,1\le \sum 2^n\le 10^5,0\le K\le10^{12},0\le w_i\le 10^{12}$

Read More

约定：题目标题后会用一个 0.0 到 1.0 间的实数表示本题有多少部分由自己解决。0.0 表示完全根据题解完成，1.0 表示完全由自己完成，其余实数则表示部分参考题解。

Read More

D. Jellyfish and Miku

从 $0$ 到 $n$ 的期望步数可以拆成从 $i$ 到 $i+1$，也即通过每条道路所需的期望步数之和。

Read More

ACC NOI 431 B 草莓路径

求一张无向连通图的路径异或最大值，有自环重边，可以多次经过一个点或一条边。

Read More

Description

在 $T\times T$ 的正方形网格上（左下角格点坐标为 $(0,0)$，右上角为 $(T,T)$，共 $(T+1)^2$ 个格点），给定 $n$ 个关键点，保证横纵坐标都互不相同。要求选出尽可能多的关键点，使其按横坐标从小到大排序后，纵坐标也单调增。在此基础上，最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Read More