10.22 写题

CF576D Flights for Regular Customers

考虑从小到大加入边,一个众所周知的结论是邻接矩阵的 $k$ 次幂就相当于走 $k$ 次后的路径条数。在这里我们只关心 $k$ 步后能否走到一个点,于是是 $01$ 矩阵。每加入一条边就进行一次矩阵快速幂,然后加入下一条边。

考虑如何计算答案。当且仅当加入一条边后在 $n$ 步内能走到终点,才说明可以走到终点,每加入一条边后判一下能否 $n$ 步内走到终点即可。

CF1187D Subarray Sorting

大概有两个做法,一个比较稳,也就是官方做法。从左到右考虑还原 $b$ 数组,直接判断一下下一个这个值的位置能否交换过来。这里的交换是两两交换,所以不会改变中间的东西的顺序,只要中间的东西都小于这个值即可。大概拿线段树维护一下就好了。

然后是杰哥想的做法,大概是对于每个位置考虑还原后它会到哪里(显然可以看成一个稳定排序,也就是没有交叉),然后对每个数看看是否会有左边的比它小的数移动到右边即可,然后发现就是个前缀最大值。其实这两种做法本质上来说差不多。

CF1399F Yet Another Segments Subset

我们可以把线段之间的包含关系建个图,发现必然是个 $\text{DAG}$ ,然后拓扑排序。考虑设 $dp[u]$ 表示选择 $u$ 这个区间以及一些它的子区间最多能选多少个。转移的时候枚举子区间,设 $f[i]$ 表示右端点最靠右的区间是 $i$ 的时候最多可以选择多少个区间。这个东西随便拿个 BIT 维护个前缀最小值即可。

复杂度 $O(n^2\log n)$。

CF1400E Clear the Multiset

考虑分治。不难发现对于一个区间如果都有值,我们进行 $1$ 操作的时候必然会让最小值变成 $0$ ,然后得到几个子问题。或者说,我们也可以直接对这个区间所有数用 $2$ 操作。分治解决即可。分治时每层复杂度都最坏 $O(n)$ ,复杂度是 $O(n^2)$。

CF1375E Inversion SwapSort

神仙题。这种题往往需要解决一个问题后转化到一个子问题(然后这也是我这辈子想不到的)。

我们考虑把 $n$ 移动到最后一个位置,把所有一端为 $n$ 的操作全部用掉,同时保持前面的数字的相对顺序不变。

具体做法是,把 $(pos[a_n+1],n),(pos[a_n+2],n),\dots,(pos[n],n)$ 依次操作一遍,于是可以发现这些位置相当于是分别减少了 $1$ ,同时归位了 $n$ ,并且用掉了所有关于 $n$ 的逆序对!

然后得到了一个子问题,继续做即可。

文章作者: yijan
文章链接: https://yijan.co/2020/11/08/1022-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog