邮局 是决策单调性优化 dp 的经典应用，其属于限制段数的序列划分问题，可以通过二分队列 + wqs 二分的方式做到 $O(n\log L\log n)$，其中 $L$ 指的是坐标的值域，此处不多赘述。

Read More

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