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

T1

100%

输入 $n$ 后根据题意判断即可

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

T2

100%

输入所有网格后，枚举每个网格，若当前的网格 $s[i][j]$ 是墙，则计算上右下左四个位置的墙的个数，四个位置分别为 $s[i-1][j]$，$s[i][j+1]$，$s[i+1][j]$，$s[i][j-1]$，若周围只有一个墙，则答案加 1。

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

T3

100%

一次操作会把选定区间内的所有灯变亮，不会使原本亮着的灯熄灭。因此可以枚举操作区间，并计算操作后仍然亮着的灯数。

预处理两个数组：

• $pre[i]$：区间 $[1,i]$ 中字符 o 的数量；
• $suf[i]$：区间 $[i,n]$ 中字符 o 的数量。

枚举操作区间的右端点 $i$，令 $j=\max(0,i-m)$，并选择区间 $(j,i]$，即 $[j+1,i]$。该区间长度为 $i-j\le m$。执行操作后：

• 区间 $(j,i]$ 内的 $i-j$ 盏灯全部亮起；
• 区间左侧原本亮着的灯有 $pre[j]$ 盏；
• 区间右侧原本亮着的灯有 $suf[i+1]$ 盏。

因此，此时亮灯总数为 $(i-j)+pre[j]+suf[i+1]$。

枚举所有 $1\le i\le n$，取最大的 $res$ 即为答案。

当 $i\ge m$ 时，枚举到的是所有长度恰好为 $m$ 的区间；当 $i<m$ 时，枚举到的是从位置 $1$ 开始、长度小于 $m$ 的区间。由于扩大操作区间不会减少亮灯数量，所以一定存在一个最优方案使用长度 $m$ 的区间，上述枚举不会漏掉最优解。即使不执行操作最优，任取一个区间也不会使亮灯数减少。

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

T4

100%

首先我们无需将 1 修改为 0，因为每个子串都是以 1 为结尾，因此 1 的个数越多越好。

接下来我们只需要考虑将哪些位置的 0 修改为 1 即可。可以通过线性 dp 的方式来计算。

设 $dp[i]$ 表示将前缀 $s[1..i]$ 变为合法字符串（$i$ 位置一定是 1）的最小代价。转移时考虑最后一个子串的种类：

• 最后一个子串为 1，则 $dp[i]$ 从 $dp[i-1]$ 转移
• 最后一个子串为 01，则 $dp[i]$ 从 $dp[i-2]$ 转移
• 最后一个子串为 001，则 $dp[i]$ 从 $dp[i-3]$ 转移

取其中的最小代价进行转移，并且若 $s[i]$ 本身是 0，则还需加上 $i$ 位置的翻转代价 $a_i$，因此:

$$dp[i]=\min (dp[i-1],dp[i-2],dp[i-3]) + a_i [s_i=0]$$

需要注意前两个位置的转移。

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

T5

100%

模拟样例可以发现，每个点的父节点是固定的。考虑一个数 $x$，设其质因子降序序列为 $(p_1,p_2,\dots,p_k)$，其中 $p_1 \geq p_2 \geq \dots \geq p_k$。

令 $y=x/p_k$，则 $\text{LCA} (x,y)=y$，又因为 $y$ 是由 $x$ 删掉了最小的质因子产生的，因此 $y \sim x$ 中的数字不可能出现在 $x$ 和 $y$ 两点的简单路径上，即 $y$ 是 $x$ 的直接父亲。

因此我们可以得到求出每个点 $x$ 的父亲的方法，设 $\text{minp}[x]$ 为 $x$ 的最小质因子：

$$fa[x]=x/\text{minp}[x]$$

其中 $fa[1]=0$。

$\text{minp}[x]$ 可以通过线性筛或埃式筛求出。

时间复杂度 $O(n)$ （线性筛）。

T6

20%

$n \leq 15$ 可以通过二进制枚举的方式，枚举一个集合，没有选的点集构成另一个集合，判断两个集合是否都为团，若合法则统计答案。

100%

题目要求将所有点分成两个有序集合 $S_1$，$S_2$，且两者都是团（任意两点间都有边）。

在补图中，团会变成独立集（任意两点之间都没有边）。原图的划分（$S_1$，$S_2$）合法，当且仅当在补图中 $S_1$ 和 $S_2$ 都是独立集。

因此整个补图必须是二分图，能被二分图染色，如果存在奇环，则不存在合法划分。如果补图不是二分图，那么答案为 $0$。

对补图的每个联通分量进行二分图染色，并记录两种颜色的大小（$siz_1，siz_2$）和点权和（$sum_1，sum_2$）。

然后问题转化为：有若干组，每组有两个选项，必须选择其中一个，问所有选择方案中，$S_1$ 的大小恰好为 $k$ 时的权值和。

很明显是一个背包的模型，可以设 $dp[i][j]$ 表示前 $i$ 个连通分量，当前选了的点集大小为 $j$ 的权值和，然后考虑每一组选第一部分还是第二部分进行转移。

由于我们需要求划分大小为 $k$ 的所有方案的权值和，因此还需要额外维护 $cnt[i][j]$，表示前 $i$ 个连通分量，当前选了的点集大小为 $j$ 的方案数，这样在第 $i$ 个联通分量选择某一部分时，将这部分的权值乘前面的方案数，才能得到这一部分的贡献。

最终转移时，枚举当前联通分离的两个部分的 $siz$ 和 $sum$：

$$\begin{aligned} dp[i][j] +&= dp[i-1][j-siz] + cnt[i-1][j-siz] \times sum \\ cnt[i][j] +&= cnt[i-1][j-siz] \end{aligned}$$

注意过程中，以及 $sum$ 要取模。

时间复杂度 $O(n^2)$，空间可以将两个数组进行滚动优化。