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

T1

数据范围 $n \le 1000$ ，非常小，可以直接从 $1$ 遍历到 $n$ 。

对于每个数字，将其转化为字符串或通过不断取模分离出每一位数字，判断每一位是否是 $3$ 的倍数（即是否为 $0, 3, 6, 9$ ）。如果所有位都满足条件，则计数器加一。

T2

数据范围 $n \le 5000$ ，可以使用 $O(n^2)$ 的算法。

我们需要枚举所有的子数组 $[l, r]$ 。第一层循环枚举左端点 $l$ 从 $1$ 到 $n$ 。第二层循环枚举右端点 $r$ 从 $l$ 到 $n$ 。

在第二个循环中，我们可以求出当前区间 $[l, r]$ 的最大值和最小值。每次 $r$ 移动一位，更新最大值和最小值。

然后判断是否满足条件。如果满足条件，答案加一。

时间复杂度 $O(n^2)$ 。

T3

对于每个位置 $(i, j)$ ，暴力遍历第 $i$ 行和第 $j$ 列的所有元素求和。时间复杂度 $O(nm(n+m))$ ，在 $n,m \le 100$ 时可通过。

第 $i$ 行或第 $j$ 列的元素之和 = 第 $i$ 行元素之和 + 第 $j$ 列元素之和 - 重复计算的 $A_{i,j}$ 。

我们可以先预处理出每一行的和，存入数组 $Row[i]$ ，以及每一列的和，存入数组 $Col[j]$ 。预处理的时间复杂度为 $O(nm)$ 。

对于每个位置 $(i,j)$ ，直接计算 $B_{i,j} = Row[i] + Col[j] - A_{i,j}$ 。

总时间复杂度 $O(nm)$ 。

T4

对于每一天 $j$ ，向后遍历 $i > j$ ，找到第一个 $P_i > P_j$ 的位置，将 $P_i - P_j$ 累加到第 $i$ 天的答案中。时间复杂度 $O(n^2)$ 。

这是一个经典的"寻找右边第一个比自己大的数"的问题，可以使用单调栈来解决。

我们维护一个单调递减的栈，栈中存储的是《买入但尚未卖出》的日子的下标。从第 $1$ 天遍历到第 $n$ 天，设当前为第 $i$ 天，股价为 $P_i$ ：

当栈不为空且栈顶下标 $top$ $t o p$ 对应的股价 $P_{top} < P_i$ $P_{t o p} < P_{i}$ 时，说明第 $top$ $t o p$ 天买入的股票在第 $i$ $i$ 天第一次遇到更高的价格，此时应该卖出。
- 计算利润： $profit = P_i - P_{top}$ 。
- 将利润累加到第 $i$ 天的答案中： $ans[i] += profit$ 。
- 弹出栈顶。
重复步骤 $1$ 直到栈为空或栈顶股价 $\ge P_i$ 。
将当前下标 $i$ 压入栈中。

遍历结束后，栈中剩余的下标表示这些天买入的股票在后续没有遇到更高的价格，不会产生交易，无需处理。

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

T5

考虑动态规划。设 $dp[i][j]$ 表示在数组 $A$ 的前 $i$ 个数中选择了子序列 $B[1\dots j]$ ，且以 $A[i]$ 结尾（即 $A[i]$ 匹配 $B[j]$ ）的方案数。

转移方程：如果 $A[i] == B[j]$ ，则可以从 $A$ 中下标 $p \le i-K$ 的任意位置转移过来，即 $dp[i][j] = \sum_{p=1}^{i-K} dp[p][j-1]$ 。如果 $j=1$ 且 $A[i]==B[1]$ ，则 $dp[i][1] = 1$ 。

直接计算的时间复杂度为 $O(n^2 m)$ ，可通过 $n \le 200$ 。

注意到转移方程中的求和 $\sum_{p=1}^{i-K} dp[p][j-1]$ 是关于上一层状态的一个前缀和。我们可以优化 DP。设 $dp[j][i]$ 表示匹配了 $B$ 的前 $j$ 个，以 $A[i]$ 结尾的方案数。同时维护前缀和 $S[j][i] = \sum_{k=1}^i dp[j][k]$ 。转移时用 $S[j][i]$ 进行转移即可。

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

T6

对于每次修改，我们考虑重新计算整个数组 $a$ 和 $b$ 之间的最大相似度。

为了计算当前的相似度，我们可以使用滑动窗口算法：

初始时，统计第一个窗口（下标 $1 \sim k$ ）内两个数组各元素的出现次数，计算交集大小 $S$ 。
窗口向右移动一位（从 $i$ $i$ 到 $i+1$ $i + 1$ ）：
- 相应减少 $a_i,b_i$ 所产生的贡献，移除下标 $i$ 处的元素 $a_i, b_i$ ，更新计数数组，再加上此时 $a_i,b_i$ 所产生的贡献。
- 相应减少 $a_{i + k},b_{i + k}$ 所产生的贡献， $a_{i+k}, b_{i+k}$ ，更新计数数组，再加上此时 $a_i,b_i$ 所产生的贡献。

利用上述方式来维护交集大小即可。

单次重新计算的时间复杂度为 $O(n)$ ，总时间复杂度为 $O(nq)$ ，可以通过子任务 1。

每次修改只交换了 $a_w$ 和 $a_{w+1}$ ，这只会影响两个长度为 $k$ 的滑动窗口的权值：

以 $w$ 结尾的窗口（下标 $[w-k+1, w]$ ）。
以 $w+1$ 开头的窗口（下标 $[w+1, w+k]$ ）。

其余所有窗口的内部元素集合均没有发生改变，因此权值不变。我们只需要快速更新这两个受影响窗口的权值，并维护全局最大值。

具体来说，我们可以用 vector<int> pos[2][val] 记录每个数值在数组 $a$ 和 $b$ 中出现的所有下标位置。此时可以利用 $30$ 分做法的方法来维护出被影响的两个窗口的 $f$ 值。不同的是求区间中某个数字出现的个数可以在 pos 上二分来求，交换之后需要更新 pos 中的数字编号即可。

时间复杂度 $O(n + q \log n)$ 。

题目定义的权值 $\sum_{b=0}^{29}|\{\lfloor\dfrac{a_i}{2^b}\rfloor\}|$，可以理解成是选中的 $n$ 个数在高度为 $30$ 的 01-Trie 上所覆盖的节点总数。

根据求和的线性性质，总权值等于每一层被覆盖节点数的总和。考虑二叉树的某一层（对应二进制第 $b$ 位，该层的节点代表长度为 $2^b$ 的值域区间）：

该层总共有 $2^{30-b}$ 个节点。
其中部分节点所代表的区间完全落在了禁止区间内，这些节点是不可用的。
剩余的节点是可用的。
因为我们总共可以选择 $n$ 个叶子，在这一层我们最多能覆盖 $\min(n, \text{该层可用节点数})$ 个节点。

因此，问题的关键转化为：如何快速维护每一层有多少个“完整块”被禁止区间完全覆盖。

为了计算被覆盖的完整块，我们需要维护所有禁止区间的并集（确保区间不重叠）。

假设当前有一个禁止区间 $[L, R]$ ，我们需要计算它包含了多少个形如 $[k \cdot 2^b, (k+1) \cdot 2^b - 1]$ 的完整块（即树上的节点）。

推导如下：

块的左边界限制：$k \cdot 2^b \ge L \Rightarrow k \ge \lceil \frac{L}{2^b} \rceil$。
块的右边界限制：$(k+1) \cdot 2^b - 1 \le R \Rightarrow (k+1) \cdot 2^b \le R + 1 \Rightarrow k+1 \le \lfloor \frac{R+1}{2^b} \rfloor$。即 $k \le \lfloor \frac{R+1}{2^b} \rfloor - 1$ 。
块的数量：右边界下标 - 左边界下标 + 1。即 $\max(0, \lfloor \frac{R+1}{2^b} \rfloor - \lceil \frac{L}{2^b} \rceil)$。区间合并均摊复杂度 $O(\log q)$ ，每次更新和查询需遍历 30 层。总复杂度 $O(q \cdot (30 + \log q))$ 。