AT318 A-G 题解

TKXZ133's Blog / 2023-09-05 / 原文

A

枚举 $1\sim n$ 的每个数，判断是否有 $i-M\equiv 0\pmod P$ 即可。

赛时代码

B

暴力覆盖即可，注意 $x,y$ 均是左开右闭。

赛时代码

C

贪心的想，如果要替换 $i$ 项，那必然是替换最大的 $i$ 项，因此只需要对 $f$ 排序，预处理后缀和后再扫一遍取替换前 $i$ 项的最小值即可。

赛时代码

D

状压 DP，设 $f_s$ 表示选择若干边的最大价值，使得 $s$ 状态中的所有点都被选择，那么可以得到转移方程：

\[f_s=\max_{1\le i< j\le n,i\in s,j\in s}(f_{s-\{i\}-\{j\}}+w_{i,j}) \]

赛时代码

E

对于不同的值分别考虑，设当前考虑的值为 $i$，我们考虑一对在序列中相邻的值，其下标分别为 $l,r$，那么它对 $i$ 产生的贡献为：

\[(r-l-1)\times \text{lnum}\times \text{rnum} \]

其中，$\text{lnum}$ 表示在 $l$ 左侧的值为 $i$ 的数的个数，$\text{rnum}$ 表示在 $r$ 右侧的数的个数。

再将所有贡献累加即可。

（注意边界）

赛时代码

F

我们考虑可行性发生变化的点，也就是说，我们需要找出所有满足在这个点可行，在这个点左侧或右侧不可行的所有点，容易发现，这样的点的数量是 $O(n^2)$ 的，且一定等于 $X_i\pm L_j$。

所以我们可以将所有的 $X_i\pm L_j$ 排序，如果两个相邻的点都可行，那么这两个点之间的区间都可行。

因此，我们只对所有这样的点进行一遍暴力 $O(n\log n)$ 的 check，总时间复杂度为 $O(n^3\log n)$。

（还有一些 $\pm 1$ 的边界问题需要注意）

赛后代码

G

考虑网络流，先将所有点拆成入点和出点，入点向出点连流量为 $1$ 的边，对于原图中的边 $e=(u,v)$，从 $u$ 的出点向 $v$ 的入点，$v$ 的出点向 $u$ 的入点连流量为 $+\infty$ 的边。再从源点向 $B$ 连流量为 $2$ 的边，$A,C$ 向汇点连流量为 $1$ 的边，跑一遍 dinic，只需要判断最大流是否为 $2$ 即可。（注意 $B$ 的入点向出点连边权为 $2$ 的边）