• 搬题人
  • 比赛：feecle6418
  • 排列：cdw
  • 选择：p_b_p_b
• 组题人
  • p_b_p_b
• 题解：别急

比赛

来源：

• Petrozavodsk Winter 2020 Day 7: Gennady Korotkevich Contest 5, Problem J
• https://qoj.ac/contest/447/problem/1431

考虑怎么算单次答案。可以发现比赛规则等价于，建一棵 $n+1$ 层满二叉树，第 $i$ 轮让从叶子开始数第 $i$ 层两两对战，然后把胜者传到第 $i-1$ 层。那设 $f(x,i)$ 表示这棵二叉树的结点 $x$ 胜者为 $i$ 的概率，算一次答案是 $O(n^2)$ 的（复杂度分析同树形背包）。

注意到，除了与主角有关的结点外，二叉树的每个结点内的选手对应了 $a$ 序列的一个区间。如果说我们知道所有合法区间 $[l,r]$ 对应的 $f$ 数组，那单次算答案是 $O(n)$ 的（只需要主角每次都赢，而每次打的区间之间是独立的，把概率相乘即可）。而哪些区间可能被对应呢？实际上只有 $O(n)$ 种 $[l,r]$ 可能被对应：只有 $[X\times 2^Y+1,(X+1)\times 2^Y]$，或者 $[X\times 2^Y,(X+1)\times 2^Y-1]$ 两种区间可能被对应（分别是主角在其之后和之前的情况）。则对这些 $[l,r]$ 预处理出对应的 dp 数组的值即可，复杂度还是 $O(n^2)$。

排列

来源：

• Petrozavodsk Winter 2021 Day 2: UPC Contest, Problem B
• https://qoj.ac/contest/530/problem/864

算法 1：随机调整，使得冲突的对数最小化，期望得分 $0\sim 100$ 分 因为我忘了所以没给这档分，想尝试的同学可以试试

算法 2：根据题解的第 $67$ 和 $70\sim 73$ 页, 若已有长为 $n$ 的排列, 可以构造长为 $3n+1$, $3n+5$, $3n+9$ 的排列, 那么从长为 $1,5,9$ 的排列即可构造长度任意的排列.

算法 3：分 $n\equiv 0\pmod 4$ 和 $n\equiv 1\pmod 4$ 两种情况, 见题解的第 $74\sim 75$ 页.

选择

来源：

• Moscow Pre-Finals Workshops 2022 Day 1: Opening Contest (TOPC 2016+ Selection) A
• https://qoj.ac/contest/917/problem/3835

Tutorial by p_b_p_b.

本题的证明有一些问题，在下面用黑体标出。

无脑 $O(n^2)$ 的 dp 非常显然，可惜没什么优化空间。

不难发现一个简单的性质：对于任意一个 $k$ 的最优方案，选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置。

那么从简单的情况开始考虑

• $k=1$ 时显然只会选择最大值 $p_{m_1}$ 。
• $k=2$ 时会选择最大值以及 $[1,m-1]$ 的最大值 $p_{m_2}$ 或是 $[m+1,n]$ 的最大值 $p_{m_3}$ ，不妨假设选择的是 $p_{m_2}$ 。
• $k=3$ 时就会发生有趣的事情——假设 $[m+1,n]$ 的次大值是 $p_{m_4},m_4>m_3$ ，那么虽然 $p_{m_1},p_{m_3},p_{m_4}$ 也满足“选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置”的限制，但它一定不会优于 $p_{m_2},p_{m_1},p_{m_4}$ ，更不会优于 $p_{m_2},p_{m_1},p_{m_3}$ 。
  • 这是因为，$p_{m_2},p_{m_1}$ 的组合优于 $p_{m_1},p_{m_3}$ ，而 $p_{m_4}$ 在两边的贡献相同。

简单拓展一下（打表），可以发现第二个性质：对任意一个 $k$ 和一组大小为 $k$ 的最优方案 $S$ ，存在一个大小为 $k+1$ 的最优方案 $T$ ，使得 $S\subset T$ 。证明用类似的调整法即可不会证，肯定需要用到 $x^2+ax+b$ 的性质，但不知道怎么用。

因此我们只需要在每一步贪心加入贡献最大的位置，就已经对每个 $k$ 都是最优的了。

可惜，直接实现仍然是 $O(n^2)$ 的，并且搬题人并没有想到如何把它和最朴素的暴力区分开。

因此我们需要最后一个性质：对任意 $i$ ，$1,2,\cdots,i$ 的加入顺序与 $i+1,\cdots,n$ 无关。这是因为无论是加入 $x$ 还是加入 $y$ 对 $\max(x,y)+1,\cdots,n$ 造成的影响都是相同的，因此 $\max(x,y)+1,\cdots,n$ 对 $x,y$ 的相对顺序没有影响。

于是我们可以从左往右扫，维护当前见到的前缀的加入顺序。设当前做到了第 $i$ 个元素，那么 $1,\cdots,i-1$ 的顺序已经确定为 $p_1,\cdots,p_{i-1}$ ，然后求出 $i$ 应该在什么时候加入即可。

具体地，二分一个 $k$ ，判断已经加入了 $p_1,\cdots,p_k$ 的情况下，加入 $p_{k+1}$ 和 $i$ 哪个更优。但是并不知道为什么这有可二分性。这可以用平衡树维护，复杂度 $O(n\log n)$ 。