2022.11.23

hexagon · 2022-11-23 18:30:27 · 个人记录

首先是昨天的考试题，然后是几道车上想的题。

A

如果把矩阵看作是一张图的邻接矩阵，那么这张图要满足从任意点出发的最长路径小于 k 。也就是要把图分成 k 层，每层之间没有连边，编号较小的层可以向编号较大的层连边，问最多能连多少边。

可以发现一定是把所有点尽量均匀地分成 k 层最优，算一下就好了。时间复杂度 O(1) 。

B

很有趣的题。

最直观的想法是直接二分，检查一个区间 [l,r] 的边是否会导致清空的时间复杂度是 O((r-l)\log {(r-l)}) ，总时间复杂度是 O(kn\log n) ，其中 k 是清空的次数，当 k 较大时就无法通过。

由于检查一个区间的复杂度和长度有关，想到每次二分时，可以先检查一下长度为 \sqrt n 的区间。若这个区间会被清空，则说明实际答案的长度在 [1,\sqrt n] 之间，单次时间复杂度为 O(\sqrt n \log \sqrt n) ；否则长度在 [\sqrt n +1,n] 之间，虽然这样单词复杂度较之前没有变化，但由于出现这种情况不会超过 \sqrt n 次，故总的时间复杂度是 O(n\sqrt n\log n) 。

另外还有一个 O(n\log^2 n) 的做法，每次先不断地暴力将右端点增加 2^0,2^1,2^2,... ，直到当前区间会被清空。这样答案的右端点的位置就一定在上个右端点到当前右端点的区间中，直接在这个区间中二分即可。可以用均摊证明这样的复杂度是 O(n\log^2 n) 的。

C

首先可以想到 dp(l,r,u,d) 表示一个子矩形的答案。然后转移就是枚举分界线，时间复杂度 O(n^5) 。固定前两维后，发现后两维是一个具有决策单调性的区间 dp ，时间复杂度 O(n^4) ，但这样空间都开不下。

然后发现答案最大也是 \log 级别的，于是可以记 dp(o,u,d,l) 表示当答案为 o 时，上界为 u ，下界为 d ，左边界为 l ，右边界的最大值是多少。

考虑两种转移：

• 竖着切开，dp_{o,u,d,l}=dp_{o-1,u,d,dp_{o-1,u,d,l}} ，时间复杂度 O(n^3\log n) 。
• 横着切开，转移点具有决策单调性，时间复杂度 O(n^3\log n) 。

D

设 dp(i,x) 表示考虑到 i ，a_i=x 的方案数。感觉上 a_i 的取值应该不多，但实际上可以构造出数据使得 a_i 远大于序列的最大值。

可以发现，如果一个数 \times 2 后大于了序列的最大值，那么它后面的数一定都会有一次 \times 2 ，这个代价是可以预先计算的。于是我们重新记 dp(i,x) 表示考虑到 i ，a_i=x 且小于等于序列的最大值的答案，g(i,x) 表示考虑到 i ，i 这个数被右移了 j 位，当前 a_i>m 的最小操作次数。其中 dp 的第二维是 O(\log^2) 的。时间复杂度 O(n\log^2 n) 。

CF383E

假设字母全集是 s ，f_x 为集合 x 的答案。对于一个包含字母集合是 t 的串，根据题意，若一个集合 h 满足 h\cap t\neq \emptyset ，则这个串对 f_h 有 1 的贡献。也就相当于其对 f_t(t\subset s) 有 1 的贡献，对 f_t(t\subset h) 有 -1 的贡献，FWT 即可。

CF375D

直接树上启发式合并。

CF396A

每个质因子都是独立的，分别用插板法统计方案。

CF398B