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

T1

100%

直接计算 $x=10a+b$、$y=10b+a$，判断 $[k\mid x]$ 与 $[k\mid y]$ 是否恰有一个为真，是则输出 Yes，否则输出 No。

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

T2

100%

$n\le300$，枚举所有 $i<j$，共 $O(n^2)$ 对，计算 $s=a_i+a_j$，以 $(|s-w|,\ s)$ 为关键字取字典序最小的一对，输出其 $s$。只要求编号不同，重量相同的两个砝码可以同时选。

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

T3

100%

不同颜色互不影响，且每种颜色至多选一张。由于 $w_i\ge1$，只要某种颜色出现过，选其中权值最大的一张一定最优，这样总和最大，也自然满足"至少选一张"。

开数组 $mx_c$ 记录每种颜色的最大权值，答案为 $\sum_c mx_c$。颜色编号不超过 $n$，可直接用数组。

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

T4

100%

$x\mapsto\lfloor x/d\rfloor$ 单调不降，所以把 $a$ 升序排序后 $c_i=\lfloor a_i/d\rfloor$ 也是升序。$c$ 与 $b$ 的多重集相同，当且仅当两者排序后逐位相等。因此把 $a$、$b$ 分别升序排序，$d$ 合法当且仅当对每个 $i$：

$$\left\lfloor\frac{a_i}{d}\right\rfloor=b_i\iff b_id\le a_i<(b_i+1)d .$$

• $a_i<(b_i+1)d\iff d>\lfloor a_i/(b_i+1)\rfloor$，即 $d\ge\lfloor a_i/(b_i+1)\rfloor+1$；
• $b_id\le a_i$：当 $b_i>0$ 时等价于 $d\le\lfloor a_i/b_i\rfloor$，当 $b_i=0$ 时恒成立。

所以每个 $i$ 给出 $d$ 的一个区间，合法的 $d$ 就是这些区间与 $[1,M]$ 的交集：

$$lo=\max\Bigl(1,\ \max_i\bigl(\lfloor a_i/(b_i+1)\rfloor+1\bigr)\Bigr),\quad hi=\min\Bigl(M,\ \min_{b_i>0}\lfloor a_i/b_i\rfloor\Bigr),$$

答案为 $\max(0,\ hi-lo+1)$。

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

T5

100%

设当前翻转标记为 $f$（初始 $0$），删除原串中的字符 $S_x$，它的当前真实值为 $S_x\oplus f$。若真实值为 $1$，则标记翻转，所以新标记 $f'=f\oplus(S_x\oplus f)=S_x$。也就是说，一次操作后，翻转标记恰好等于刚被删除字符的原始值。

剩余字符串全为 $0$，等价于其中每个原始字符都等于当前标记 $f$。分情况讨论：

• 不操作：需要原串全为 $0$，答案 $0$。
• 剩余为空：总是可行，代价 $n$。
• 操作过且剩余非空：设剩余部分是原串区间 $[l,r]$，则其中字符必须全为同一个值 $v$，且最后一次被删除的字符值也为 $v$。最后一次删除的字符一定紧邻剩余区间，即 $S_{l-1}$ 或 $S_{r+1}$。所以 $[l,r]$ 是某个极长同值连续段的真子段（它被一个同值字符紧邻）。

对长度为 $L$ 的极长连续段，最优是保留其中 $L-1$ 个字符：先把其余字符全部删掉，最后删去段内的一个同值端点字符，此时标记恰为 $v$，操作数为 $n-(L-1)$。$L=1$ 时退化为剩余为空，代价 $n$，公式依然成立。

设 $m$ 为最长连续同值段的长度（$0$ 段与 $1$ 段都算），则

$$ans=\begin{cases}0,&S\text{ 全为 }0,\\ n-m+1,&\text{其他情况}.\end{cases}$$

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

T6

100%

不难发现合法区间的子区间一定合法。

设 $bad(R)$ 为所有右端点 $\le R$ 的"$x,y,x,y$ 模式"中，第一个位置 $i$ 的最大值（没有模式时为 $0$）。以 $R$ 为右端点的合法区间恰为左端点 $L>bad(R)$，共 $R-bad(R)$ 个，所以答案为 $\sum_R(R-bad(R))$。而

$$bad(R)=\max\bigl(bad(R-1),\ g(R)\bigr),$$

其中 $g(l)$ 为最后一个位置恰为 $l$ 的模式中第一个位置 $i$ 的最大值（不存在则为 $0$）。

求 $g(l)$： 设 $y=a_l$，$p$ 为 $y$ 在 $l$ 之前最近的出现位置（不存在则 $g(l)=0$）。考虑模式 $(i,j,k,l)$，其中 $a_i=a_k=x\ne y$，$a_j=y$，$i<j<k<l$：

• 若 $k<p$，则 $(i,j,k,p)$ 也是模式，它的贡献已包含在 $bad(p)\le bad(l-1)$ 中，无需再考虑；
• 若 $k>p$，则 $j\le p<k$，把 $j$ 换成 $p$ 得到模式 $(i,p,k,l)$，$i$ 不变。

所以只需考虑 $j=p$，即 $i<p<k<l$ 且 $a_i=a_k\ne y$。$i$ 取尽量大，不妨设 $i$ 是其颜色在 $p$ 之前的最后一次出现（若不是，则更靠后的出现位置也满足条件且更大）。记 $nx(i)$ 为 $a_i$ 的下一次出现位置，条件化为

$$g(l)=\max\{\,i\ :\ i<p<nx(i)<l\,\}.$$

其中 $nx(i)>p$ 说明 $i$ 是其颜色在 $p$ 之前的最后一次出现，也自然保证 $a_i\ne y$（否则 $nx(i)\le p$）；$p<nx(i)<l$ 说明 $a_i$ 在 $(p,l)$ 内再次出现。

具体实现如下：

用线段树按下标 $i$ 存 $nx(i)$（未加入时为 $0$），维护区间最大值。从左到右处理 $l$：先把 $nx(i)=l-1$ 的那个 $i$（即 $l-1$ 的上一次出现位置，若存在）加入，保证所有 $nx(i)<l$ 的项都已加入；然后在下标范围 $[1,p-1]$ 中，用线段树二分找到最大的、值 $>p$ 的下标，它就是 $g(l)$（找不到则 $g(l)=0$）。更新 $bad(l)$ 并累加 $l-bad(l)$。

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