- 搬题人
- 比赛:feecle6418
- 排列:cdw
- 选择: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(n2) 的(复杂度分析同树形背包)。
注意到,除了与主角有关的结点外,二叉树的每个结点内的选手对应了 a 序列的一个区间。如果说我们知道所有合法区间 [l,r] 对应的 f 数组,那单次算答案是 O(n) 的(只需要主角每次都赢,而每次打的区间之间是独立的,把概率相乘即可)。而哪些区间可能被对应呢?实际上只有 O(n) 种 [l,r] 可能被对应:只有 [X×2Y+1,(X+1)×2Y],或者 [X×2Y,(X+1)×2Y−1] 两种区间可能被对应(分别是主角在其之后和之前的情况)。则对这些 [l,r] 预处理出对应的 dp 数组的值即可,复杂度还是 O(n2)。
排列
来源:
- Petrozavodsk Winter 2021 Day 2: UPC Contest, Problem B
- https://qoj.ac/contest/530/problem/864
算法 1:随机调整,使得冲突的对数最小化,期望得分 0∼100 分 因为我忘了所以没给这档分,想尝试的同学可以试试
算法 2:根据题解的第 67 和 70∼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) 。