20210802模拟赛题解

回家

难度：模板。

通过人数：$6$ 人。

算法一

暴力跳父亲，期望得分 $40$。

算法二

树链剖分，时间复杂度 $\Theta(n)-\Theta(\log n)$。

设 $z=lca(x,y)$，则 $x,y$ 的答案为 $\left \lceil \frac{dep_x-dep_z}{k} \right \rceil+\left \lceil \frac{dep_y-dep_z}{k} \right \rceil $。

期望得分 $100$。

使用倍增的很有可能好像都MLE或者TLE了。

筷子

难度：普及。

通过人数：$18$人。

算法一

暴力枚举每只筷子选不选，找到能取到 $m-1$ 双筷子的最大值，加一就是答案。

时间复杂度 $O(2^{\sum a_i})$。期望得分 $9$ 分。

算法二

考虑DP，设 $f_{i,j}$ 表示前 $i$ 种筷子中能配对出 $j$ 双筷子的最大筷子数量。

时间复杂度 $O(na^3)$。期望得分 $24$ 分。

算法三

考虑在算法二上进行DP优化。做一个类似于前缀最大值的优化的即可。

时间复杂度 $O(na^2)$，期望得分 $43$ 分。

算法四

考虑贪心，直接构造出方案。

设 $b_i$ 为当前第 $i$ 种取的个数模二后的结果。

首先显然是 $n$ 种筷子都取 $1$ 个，让 $b_i$ 都变成一。

然后找到当前还剩下 $\geq 2$ 个筷子的任一种类，取走两个。如果找不到，则剩下的都是只有 $1$ 只筷子，取走一个则产生 $1$ 的贡献。

注意，若不出现找不到 $\geq 2$ 的情况，则答案要减一。因为当 $b_i$ 均为 $1$ 时，随便再选一个，能配对的数都能加一。

可以用堆等数据结构进行维护。

时间复杂度 $O(n\log n+\sum a_i)$。期望得分 $62$ 分。

算法五

算法四中若存在剩下 $1$ 只筷子的，那么筷子数一定数偶数。

于是统计出筷子数为偶数的个数，以及每次能取走两个筷子的次数。分三种情况讨论一下即可。

时间复杂度 $O(n)$，期望得分 $100$ 分。

游戏

难度：提高。

通过人数：$0$ 人。

算法一

暴力枚举每个数，然后暴力判断。

时间复杂度 $O((R-L+1)\log k)$，期望得分 $13$ 分。

算法二

$k\le 9$，对每个 $k$，每隔约 $10^7$ 个数，打一个表记录前缀和即可。找到第一个小于等于 $x$ 的打表的数，剩余的暴力统计。

大约需要记录 $1000$ 个数字。

结合算法一，期望得分 $30$ 分。

算法三

$k<100$，也就是 $k$ 最多只有两位数。

转换成算 $R$ 和 $L-1$ 的前缀和。

考虑数位DP，设 $f_{i,j,limit,flag}$ 为考虑到第 $i$ 位，已经匹配完 $k$ 的第 $j$ 位，是否打破限制，前导零是否还存在时的方案数。

枚举第 $i+1$ 位选了什么，直接转移即可。

时间复杂度 $O(\log R)$。有若干常数。期望得分 $47$ 分，结合算法一可得 $60$ 分。

算法四

写一个KMP，记录 $g_{i,j}$ 表示若 $k$ 的第 $i$ 位为 $j$，则应该失配到的位置。

然后用算法三的数位DP去算即可。

时间复杂度 $O(\log Rk)$，有大概20的常数。期望得分 $100$ 分。

数学

难度：省选。

通过人数：$0$ 人。

算法一

$l=r$，直接排序，输出期望为 $0$。

期望得分 $5$ 分。

算法二

先来看看，这个顺序是怎么样的。

对于一个最终的序列 $p_{1},p_{2}\cdots p_{n}$，若交换两个相邻的数字 $i,j$，则不会使答案变得更优。

设这两个相邻的随机变量为 $x\in [l_i,r_i],y\in[l_j,r_j],x,y\in \mathbb{Z}$，若此时 $x>y$ 的概率不超过 $\frac{1}{2}$，那么不交换的时候答案更优。

若 $x,y$ 是连续的，易知 $E(x)\le E(y)$ 时满足条件，即 $\frac{l_i+r_i}{2}\le \frac{l_j+r_j}{2}$。

由打表或证明可知，$x,y$ 取整数时亦是如此。

于是最终的一个排列就是按 $l_i+r_i$ 从小到大排序后的结果，若 $l_i+r_i$ 相同则随意排列。

期望得分 $20$ 分，与算法一结合可有 $24$ 分。

算法三

考虑如何求期望逆序对的个数。

由期望的线性性，统计出每一对 $i,j(i\le j)$ 是逆序对的期望值，然后全部加起来就是答案。

枚举 $i,j$，再枚举其中一个数字选什么，$O(1)$ 统计出另一个数字的情况数即可。

时间复杂度 $O(n^3)$，期望得分 $40$ 分。

算法四

显然，可以不需要枚举数字选什么，用个等差数列分几种情况讨论一下就可以了。

时间复杂度 $O(n^2)$，期望得分 $60$ 分。

算法五

还是要考虑继续优化求期望逆序对的方法。

我们列出算法三中的几种情况：

若 $r_i>r_j$，有贡献 $\frac{r_i-r_j}{r_i-l_i+1}$。

另外还有：$\frac{\sum_{i=\max\{l_i,l_j\}}^{\min\{r_i,r_j\}}(i-l_j)}{(r_i-l_i+1)(r_j-l_j+1)}$ 的贡献。

第一种只需要将分子拆开，用两个树状数组维护一下即可，很容易算。

重点是在第二种情况。

讨论此时的四种情况，做三维偏序。

1. $l_i\le l_j,r_i\geq r_j$，贡献的分子为 $(r_j-l_j)(r_j-l_j+1)/2$
2. $l_i\le l_j,r_i< r_j$，贡献的分子为 $(r_i-l_j)(r_i-l_j+1)/2$，需要注意要保证 $r_i\geq l_j$。
3. $l_i> l_j,r_i\geq r_j$，贡献的分子为 $(l_i-l_j+r_j-l_j)(r_j-l_i+1)/2$，需要注意要保证 $r_j\geq l_i$。
4. $l_i> l_j,r_i < r_j$，贡献的分子为 $(l_i-l_j+r_i-l_j)(r_i-l_i+1)/2$

将式子展开后，第 $1$ 和第 $4$ 种情况用三维偏序计算：第一维已经排好序了，第二维使用 cdq 分治，第三维用若干树状数组维护一些项的和。第 $2$ 种情况也是类似，只是 $r_i$ 有两个约束条件。可以发现这三种情况可以在同一个cdq里处理，cdq中按照 $l$ 排序，$r$ 这一维在树状数组上处理即可。

但是第 $3$ 种情况并不能和上面的一起做，只能按 $r$ 排序。

再写一次cdq？

由于我们刚开始时按照 $l_i+r_i$ 排序，因此完全不会出现 $l_i> l_j,r_i\geq r_j(i< j)$ ！也就是不可能出现第 $3$ 种情况。

于是就做完了。std一共用了 $7$ 个树状数组。

时间复杂度 $O(n\log ^2n)$。期望得分 $70\sim 100$。