代码源挑战赛 Round 76 题解 - 代码源竞赛平台

T1

100%

设总亮度为 $T=A+B$。相机记录的亮度不能超过 $S$，所以两项输出依次为

$$\min(T,S),\qquad \max(T-S,0).$$

无论总亮度是否达到上限，这两个数之和都为 $T$。

时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。

T2

100%

模拟题意即可。以下是一种实现方式：

把字符串 $S$ 再接到自身后面，得到长度为 $2n$ 的字符串 $T$。这样，即使一段连续格子跨过圆环的起点，也能在 $T$ 中表示为普通的连续片段。

枚举原圆环的每个起点 $i$，统计 $T$ 中从位置 $i$ 开始的 $k$ 个字符里有多少个黑格。若数量等于 $x$，答案加一。因为 $k\le n$，最后一个起点所需的片段也不会越过 $T$ 的末尾；每个起点恰好检查一次。

共有 $n$ 个起点，每次统计 $k$ 个字符，时间复杂度为 $O(nk)$，利用前缀和可以做到 $O(n)$。

T3

100%

从右往左给二进制位编号 $0,1,\ldots,w-1$。设第 $j$ 位所在的整列中共有 $c_j$ 个 1，则这一列对所有行的总得分贡献为 $c_j2^j$。交换两列时，只会交换它们对应的 $c_j$；因此读入矩阵后，只需保留每一列的 1 的数量。

枚举所有不同的位 $i<j$。对每一对，临时交换 $c_i,c_j$，再遍历全部 $w$ 位，按

$$\sum_{t=0}^{w-1}c_t2^t$$

计算交换后的总得分，用它更新最大值，最后恢复这两个计数。每一对可选列都恰好计算一次，因此最大值就是答案。题目要求必须交换，所以不能把未交换时的得分直接作为答案；例如样例 2 的得分会在交换后下降。

读入和计数需要 $O(hw)$ 时间；共有 $O(w^2)$ 对列，每对重新计算总分需要 $O(w)$ 时间。总时间复杂度为 $O(hw+w^3)$，空间复杂度为 $O(w)$。由于 $w\le20$，直接重算即可。

T4

子任务 $1$

逐一枚举交换位置，按交换后的顺序尝试安排所有工作。设上一项的时刻为 $t$，当前区间为 $[l,r]$，我们需要把当前工作安排尽量早，也就是 $\max(l,t+1)$，尽量早的好处是尽量不对后面的选择造成影响。若它超过 $r$，则本次交换无解。

这样得到的是每项工作在此前选择下能达到的最早时刻。把某项工作推迟只会使后续工作更难安排，所以一旦这种贪心安排失败，就不存在其他可行安排。共有 $n-1$ 个交换位置，每次扫描 $n$ 项，时间复杂度为 $O(n^2)$。

子任务 $2$

此时每项工作的时刻固定为 $t_i=l_i=r_i$。预处理原顺序中违反 $t_i<t_{i+1}$ 的相邻位置的前缀数量。

交换位置 $k$ 只会改变三处相邻关系：原下标为 $k-1,k,k+1$ 的关系。先用前缀数量确认其他位置都满足严格递增，再检查下列存在的关系：

$$t_{k-1}<t_{k+1},\qquad t_{k+1}<t_k,\qquad t_k<t_{k+2}.$$

当 $k=1$ 或 $k=n-1$ 时，省略越界的比较。预处理后每个位置只需 $O(1)$ 时间，故时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

100%

可以发现子任务 $1$ 每次交换都重新贪心扫描，重复处理了大量未改变顺序的前缀和后缀。对原顺序预处理两个量：

• $P_i$：前 $i$ 项可行时，第 $i$ 项能安排的最早时刻；前缀无解则标记为不可行。
• $Q_i$：第 $i$ 到第 $n$ 项可行时，第 $i$ 项能安排的最晚时刻；后缀无解则标记为不可行。

取 $P_0=-1$、$Q_{n+1}=10^9+1$。从左到右、从右到左分别计算

$$P_i=\max(l_i,P_{i-1}+1),\qquad Q_i=\min(r_i,Q_{i+1}-1).$$

若 $P_i>r_i$，该前缀及更长前缀均不可行；若 $Q_i<l_i$，该后缀及更长后缀均不可行。这两种界分别由“尽量早”和“尽量晚”的贪心安排得到。

考虑交换位置 $k$。不受交换影响的前缀 $1,\ldots,k-1$ 与后缀 $k+2,\ldots,n$ 必须可行。原第 $k+1$ 项在前缀之后最早可以安排在

$$u=\max(l_{k+1},P_{k-1}+1);$$

原第 $k$ 项在后缀之前最晚可以安排在

$$v=\min(r_k,Q_{k+2}-1).$$

交换合法当且仅当 $u\le r_{k+1}$、$v\ge l_k$ 且 $u<v$。若存在合法安排，其两项时刻必然分别不早于 $u$、不晚于 $v$，所以这些条件必要；反过来，按前缀的最早安排、时刻 $u,v$ 和后缀的最晚安排拼接，便得到一组严格递增的合法时刻。

两次预处理和枚举交换位置都只需线性时间，总时间复杂度为 $O(n)$。

T5

100%

加入一盏新灯时，新形成的三灯窗口能否满足要求，取决于此前最后两盏是否同色；计算可选颜色数还需知道已使用的颜色种数。设 $dp[i][j][t]$ 为前 $i$ 盏灯满足所有已形成的三灯要求、恰好用了 $j$ 种颜色的方案数。其中 $t=1$ 表示最后两盏同色，$t=0$ 表示最后两盏异色。

先处理前三盏灯。根据 $b_1$，只有以下初始状态非零：

• $b_1=1$：三盏同色，$dp[3][1][1]=m$。
• $b_1=2$：恰有两种颜色。若后两盏同色，有 $m(m-1)$ 种；若后两盏异色，分别可能是第一、二盏同色或第一、三盏同色，共有 $2m(m-1)$ 种。因此 $dp[3][2][1]=m(m-1)$，$dp[3][2][0]=2m(m-1)$。
• $b_1=3$：三盏颜色两两不同，$dp[3][3][0]=m(m-1)(m-2)$。

此后按 $i=4,5,\ldots,n$ 的顺序加入第 $i$ 盏灯。当前需要满足的窗口是 $(a_{i-2},a_{i-1},a_i)$，对应题面中的 $b_{i-2}$；代码把这个值存放在下标为 $i$ 的位置。从已用 $j$ 种颜色的状态出发，分类如下：

• 若 $b_{i-2}=1$，原来最后两盏必须同色，新灯也只能沿用该颜色：$dp[i][j][1]\mathrel{+}=dp[i-1][j][1]$。
• 若 $b_{i-2}=2$ 且原来最后两盏异色，新灯只能选这两种颜色之一。选倒数第二盏的颜色，得到 $dp[i][j][0]\mathrel{+}=dp[i-1][j][0]$；选最后一盏的颜色，得到 $dp[i][j][1]\mathrel{+}=dp[i-1][j][0]$。
• 若 $b_{i-2}=2$ 且原来最后两盏同色，新灯必须改用另一种颜色。选此前用过的其他颜色有 $j-1$ 种，得到 $dp[i][j][0]\mathrel{+}=(j-1)dp[i-1][j][1]$；选从未用过的颜色有 $m-j$ 种，得到 $dp[i][j+1][0]\mathrel{+}=(m-j)dp[i-1][j][1]$。
• 若 $b_{i-2}=3$，原来最后两盏必须异色，新灯还必须与它们都不同。选此前用过的其他颜色有 $j-2$ 种，得到 $dp[i][j][0]\mathrel{+}=(j-2)dp[i-1][j][0]$；选新颜色有 $m-j$ 种，得到 $dp[i][j+1][0]\mathrel{+}=(m-j)dp[i-1][j][0]$。

每次选择的新灯颜色恰好属于上述一种情况，因此转移既不会遗漏合法方案，也不会重复计数。只关心颜色数不超过 $k$ 的状态，最终答案为

$$\bigl(dp[n][k][0]+dp[n][k][1]\bigr)\bmod 998244353.$$

每层有 $O(k)$ 个状态，每个状态只产生常数次转移，时间复杂度为 $O(nk)$。

T6

100%

如果不考虑操作，如果不操作，断开 $d$ 条异色边后恰有 $d+1$ 个连通块。可以发现，我们的目标就是尽量让异色的边尽量多。设一开始的异色边数量为 $D$。

先考虑如果给定路径 $P$，那么答案该如何计算。

对于每一条边 $(u,v)$，我们考虑给它加上边权（设为 $w{(u,v)}$）：同色边权为 $+1$，异色边权为 $-1$。

翻转路径 $P$ 时，一条边对答案有贡献仅在恰好一个端点属于 $P$，且该边对答案的贡献是 $w(u,v)$。故路径的增益是所有这类边的权重的和。设 $G(P)$ 表示操作路径 $P$ 后异色边的增加量，它可以表示成：

$$G(P)=\sum_{u\in P \cap v \not\in P} w{(u,v)}$$

这个东西看起来不好算，但是我们可以用 “与 $P$ 恰好只有一个公共点的边 = 与 $P$ 内相连的点的边 - $P$ 内部的边”。等式右边的两项是好算的。

设 $a_u$ 表示所有与 $u$ 相连的边的边权和，那么 $G(P)$ 就可以写成

$$G(P)=\sum_{u\in P} a_u - 2\sum_{(u,v) \in P} w(u,v)$$

其中这个 $2$ 是因为 $P$ 内的边被计算了 $2$ 次，所以扣掉的时候要 $\times 2$。

于是问题就变成了：给定一个树，点有点权（$a_u$），边有边权（$-2w(u,v)$，注意这里的边权和上面一开始给定的边权不太一样），求最大权路径。大体求法与求直径是类似的：

任选一点为根。设 $H_u$ 为起点在 $u$、终点位于 $u$ 子树内的非空路径能取得的最大增益。若 $v$ 是 $u$ 的儿子，从 $u$ 进入 $v$ 子树的额外贡献为 $H_v-2w(u,v)$；也可以停在 $u$。所以

$$H_u= a_u+\max\left(0,\max_{v\text{ 为 }u\text{ 的儿子}}\left(H_v-2w(u,v)\right)\right).$$

任意路径在根树上有唯一的最高点 $u$，并且至多进入 $u$ 的两个儿子子树。把这些儿子提供的额外贡献与 $0$ 比较，取最大的两个值 $x_u,y_u$；以 $u$ 为最高点的最优路径增益便是 $a_u+x_u+y_u$。枚举最高点覆盖全部路径，最终答案为

$$D + 1 + \max\left(0,\max_u(a_u+x_u+y_u)\right).$$

总时间复杂度为 $O(n)$。