CSP-S 2022 做题记录

· · 个人记录

T1

题目大意

给定 n（5 \le n \le 2500）个点 m（1 \le m \le 10^4）条边的无向简单图，结点依次编号为 1\sim n 的整数．编号为 i 的结点有 a_i（1 \le a_i \le 10^{18}）的整数点权．定义一个五元组 (c_1,c_2,c_3,c_4,c_5) 是「符合条件的」的，当且仅当：

定义一个五元组的权值为五个点的点权之和，求出权值最大且符合条件的五元组的权值，保证存在至少一组符合条件的五元组．

简要做法

首先以每个点为开始跑 BFS，求出任意两个点之间的最短路．

考虑在固定 c_3,c_4 两个点的条件下找出权值最大的 c_2 和 c_5．发现 c_2 与 1、c_3 的距离，c_4 与 1、c_5 的距离不能超过 K．考虑对于每个结点，预处理出一个集合代表该点作为 c_3（或 c_4）时，有哪些点可以作为 c_2（或 c_5）．然后枚举预处理出的集合，依次检查选出的 c_2 和 c_5 是否与已有的点重复，并更新答案．

上述做法时间复杂度为 O(nm + n^4)．无法通过本题．需要进一步优化．

我们发现处理 c_2 与 c_5 的时候，没有必要依次检查集合中的所有元素．根据鸽巢原理，不妨设当前处理的是 c_2，则该点只可能会和 c_3,c_4,c_5 重复．因此我们可以只保留集合中权值最大的四个不同的结点，则一定存在一个结点不与这三个结点重复．处理 c_5 时的情况同理．由于对于每对 c_3,c_4 只需枚举常数对 c_2,c_5，时间复杂度为 O(nm + n^2)．可以通过本题．

T2

题目大意

给定长度为 n（1 \le n \le 10^5）的整数数组 A（-10^9 \le A_i \le 10^9）和长度为 m（1 \le m \le 10^5）的整数数组 B（-10^9 \le B_i \le 10^9）．给出 q（1 \le q \le 10^5）次询问，每次询问给定整数 l_1,r_1,r_2,r_2（1 \le l_1 \le r_1 \le n，1 \le l_2 \le r_2 \le m），你需要求出：

\max_{i=l_1}^{r_1} \min_{j=l_2}^{r_2} A_i \cdot B_j.

简要做法

不难发现选出的 A_i 与 B_j 只会是以下四种情况中的一种：

证明平凡．

维护区间非负数与非正数 RMQ，依次枚举 4\times 4 = 16 种情况检查即可．

若使用 Method of Four Russians 技巧维护区间 RMQ，则时间复杂度为 O(n+m+q)．

T3

题目大意

维护有向图 G = (V,E)（1 \le |V| \le 5\times 10^5，1 \le |E| \le 5 \times 10^5）．每条边有「被标记」和「不被标记」两种状态，初始所有边均为「被标记」状态．维护 q（0 \le q \le 5\times 10^5）个操作，分为若干种：

每次操作后，判断 G 中所有「被标记」的边对应的生成子图是否为一个基环内向树森林．

简要做法

有向图是内向基环树森林的一个充要条件是所有点出度均为 1．考虑维护每个结点的出边数量，发现由于有 4 操作存在，较难维护．

考虑更换维护方式．维护所有被标记的边的起点的组成的可重集合，则有向图是内向基环树森林的一个充要条件是每个结点恰好在该集合种出现一次．对于每个结点 u，维护其所有被标记的入边的起点组成的可重集合 S_u，则答案集合 A 为所有可重集合的 Sum^{[1]}．此时，题目中的四种操作变为对于某个集合的添加元素、删除元素、清空、还原初始状态四种操作．

考虑采用哈希来维护答案集合．考虑对于原图中的每个结点 u 创建随机的权值 a_u．定义对于可重点集的哈希函数 H(S) = \sum_{u\in S} a_u．则题目中的四种操作可转化为为对哈希值的加减运算：

时间复杂度 O(n+m+q)．

T4

题目大意

给定结点数为 n（1 \le n \le 2\times 10^5）的无根树．结点依次编号为 1\sim n 的整数．编号为 i 的结点有权值 v_i（1 \le v_i \le 10^9）．给定 m（1 \le m \le 2 \times 10^5）次询问，每次询问给定 a,b（1\le a,b \le n）．定义一个长度为 s 的结点序列 \{c_1,c_2,\cdots,c_s\} 是符合条件的，当且仅当：

定义一个结点序列的权值为序列中所有结点的点权 v_i 之和．对于每次询问，输出权值最小且符合条件的权值序列的权值．

简要做法

考虑如果只有一次询问时如何做．考虑设 a,b 路径上从 a 到 b 方向上所有点的编号依次为 c_1,c_2,\cdots,c_s．我们大胆猜测一个结论：一个符合条件的结点序列一定是这个序列的子序列，且相邻两项的下标之差 \le K．考虑 DP，设 \operatorname{dp}(u) 为 u 结尾的所有符合条件的结点序列的权值最小值，转移即可．

但是很遗憾，上所做法在 K=3 时是错误的，考虑下列数据：

6 1 3
9 9 9 9 9 9 1
1 2
2 3
3 4
4 5
3 6
5 1

上述做法得到的一种最优序列为 \{5,3,1\}，但是显然序列 \{5,6,1\} 要比它更优．考虑更改 DP 状态，使它允许走到路径外的结点，设 \operatorname{dp}(u,i) 表示当前处理到了结点 u，选中的最后一个结点距离 u 的 \operatorname{dis} 为 i 的所有符合条件的结点序列的权值最小值．在 K=3 时，则有转移：

\begin{aligned} \operatorname{dp}(u,2) &\gets \operatorname{dp}(u',1)\\ \operatorname{dp}(u,1) &\gets \min\{\operatorname{dp}(u',0),\operatorname{dp}(u',1)+ M_u\}\\ \operatorname{dp}(u,0) &\gets \min_{i=0}^{K-1} \operatorname{dp}(u',i) + a_u \end{aligned}

其中 M_u 表示所有与结点 u 距离为 1 的结点的权值的最小值．

考虑如何处理多次询问．将上述 DP 转化为可区间合并的信息 D=(u,v,F)，然后使用树上倍增维护．其中 u,v 为树链的起止点，F 为一个二维 DP 数组，F(i,j) 表示选中的第一个结点与结点 u 的距离为 i，最后一个结点与结点 v 的距离为 j，所有符合要求的序列的权值最小值．合并两个信息 D_1 与 D_2 时进行分类讨论：

FOR (l1, 0, 2)
  FOR (r1, 0, 2)
    FOR (l2, 0, 2)
      if (r1 + l2 + 1 <= K)
        FOR (r2, 0, 2) {
          to_min(res.F[l1][r2], d1.F[l1][r1] + d2.F[l2][r2]);
        }
res.l = d1.l;
res.r = d2.r;

查询时将链 a,b 拆分为两条单链 a,\mathit{lca} 与 \mathit{lca},b，按照顺序合并各部分，最后输出 D_F(0,0) 即可．

时间复杂度 O(K^4 (n+m) \log n)．

注释