p_b_p_b的博客

博客

Public Round #9 题解

2023-05-14 17:03:33 By p_b_p_b

比赛

来源:

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

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

排列

来源:

算法 1:随机调整,使得冲突的对数最小化,期望得分 0100因为我忘了所以没给这档分,想尝试的同学可以试试

算法 2:根据题解的第 677073 页, 若已有长为 n 的排列, 可以构造长为 3n+1, 3n+5, 3n+9 的排列, 那么从长为 1,5,9 的排列即可构造长度任意的排列.

算法 3:分 n\equiv 0\pmod 4n\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) 的,并且搬题人并没有想到如何把它和最朴素的暴力区分开。

因此我们需要最后一个性质:对任意 i1,2,\cdots,i 的加入顺序与 i+1,\cdots,n 无关。这是因为无论是加入 x 还是加入 y\max(x,y)+1,\cdots,n 造成的影响都是相同的,因此 \max(x,y)+1,\cdots,nx,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)

评论

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

发表评论

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