p_b_p_b的博客

博客

Public Round #9 题解

2023-05-14 17:03:33 By p_b_p_b
  • 搬题人
    • 比赛:feecle6418
    • 排列:cdw
    • 选择:p_b_p_b
  • 组题人
    • p_b_p_b
  • 题解:别急

比赛

来源:

考虑怎么算单次答案。可以发现比赛规则等价于,建一棵 $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)$。

排列

来源:

算法 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$ 页.

选择

来源:

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)$ 。

评论

__2018ty22__
T3有弱化版 CF573E 做法一样
  • 2023-07-16 21:30:38
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。