2022.11.15 模拟题解

· · 个人记录

A

直接模拟。

B

先不区分每个点具体是谁，这样两个点相遇后就直接穿过去了，于是我们可以通过二分得到第 l 次和第 r 次事件的时间以及地点。

现在的问题是对于一组时间和地点，求出这次事件原本对应着哪两个点。注意到随着时间的移动，所有点位置的相对顺序是不会改变的，于是我们只用求出当前时刻，这个碰撞地点前有多少个点就好了。

最后把所有时间按照题目要求排序并输出，时间复杂度 O(n\log^2 n) 。

C

对于 ca=0 或 cb=0 的情况单独处理。 然后发现存活到最后的点一定是一段前缀的 B ，一段后缀的 A ，且两者存在唯一分界线，于是可以拆成两部分 dp ，然后再乘起来。

一开始想的是，对于前一部分，设 dp(i,j,k) 表示当前到 i ，有 j 个 B 存活了下来，还有 k 个向右的 A 没有被抵消。直接转移 n^4 ，前缀和可以优化到 n^3 ，但由于状态数过多，难以继续优化。

但是把问题倒着做就可以简化状态数，设 dp(i,j) 表示从分界点到 i ，有 j 个 B 存活了下来的方案数。这样的 dp 设计虽然要在每个分界点都 O(n^2) 的算一次，但实际上可以优化。

我们发现对于不同的分界点，初始状态不同，但转移相同，最终状态也相同。不难想到可以反过来转移，每个点的状态变成了到达最终状态的方案数，于是 O(n^2) dp 一次就好了。

时间复杂度 O(n^2) 。

D

难写且卡常。

先二分答案 k ，然后考虑通过依次添加元素至末尾的方式构造答案。则对于每一个没有被加入的区间都有一个限制 l_i 表示这个区间需要在 i 步内加入。最初所有 l_i=n 。如果答案合法，那么过程中必须要满足：

\sum_{j}{[l_j\leq i]}\leq i

考虑当前最小的 x 满足 \sum_j{[l_j\leq x]}=x ，当前选取的区间必须要满足 l_i\leq x 。又因为题目中第二段的限制，当前选择的区间的右端点越大，会被限制的区间就会越多。综上所述，我们应该加入的区间是满足 l_i\leq x 中右端点最大的一个。

然后用线段树和堆模拟这个过程，时间复杂度 O(n\log n)。