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

T1

100%

左侧机器涂 $[1,a]$，右侧机器涂 $[n-b+1,n]$，两段重合的长度为

$$t=\max(0,\ a+b-n).$$

$a+b$ 中，恰被一台机器涂的方格算了 $1$ 次，被两台都涂的方格算了 $2$ 次。设恰被一台涂的有 $x$ 个，被两台涂的有 $t$ 个，则 $x+2t=a+b$，所以

$$x=a+b-2\max(0,\ a+b-n).$$

或者也可以写成 $n - |a + b - n|$。

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

T2

100%

全员到场时应发 $1+2+\cdots+n=\dfrac{n(n+1)}2$ 颗糖。少发的恰好是缺席同学的编号 $x$，所以

$$x=\frac{n(n+1)}2-s.$$

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

T3

100%

保留球的颜色一定落在某个区间 $[x,x+k]$ 内。因为 $c_i\ge1$，把该区间内的球全部保留既不破坏合法性，又让删除费用更少，所以最优解必是“保留某个颜色区间内的所有球”。

令 $w_x$ 为删除 $x$ 这个颜色需要花费的金币数，$P_x$ 为 $w_x$ 的前缀和，$C$ 为删除所有球花费的金币数量。保留 $[x,x+k]$ 内所有球能省下的费用为 $P_{\min(n,x+k)}-P_{x-1}$，因此

$$\text{答案}=C-\max_{1\le x\le n}\bigl(P_{\min(n,x+k)}-P_{x-1}\bigr).$$

至少保留一个球的要求自动满足：存在含球的区间，其费用和为正，所以最大值必在非空区间取得。$k=0$ 时公式同样成立。

$w_x$ 可以利用计数排序求出。

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

T4

100%

注意到值域只有 $1 \sim 5$。枚举中间下标 $j$，设 $y=a_j$，用 $L_x$ 表示 $j$ 左侧值为 $x$ 的个数，$R_z$ 表示 $j$ 右侧值为 $z$ 的个数。则 $j$ 的贡献为

$$\sum_{\substack{1\le x,z\le5\\ x>z>y\\ (x+z)\bmod y=0}}L_x\cdot R_z.$$

其中 $L_x$ 和 $R_z$ 都可以用前缀和计算得到。

具体实现上只需要先枚举 $j$，再枚举 $x$ 和 $z$ 的值即可。

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

T5

100%

本题对任意合法输入都有解，不会输出 $-1$。

做法是把大小关系建成有向图，再拓扑排序。

「$p_u<p_v$」记为一条有向边 $u\to v$。若图无环，任取一个拓扑序，按拓扑序依次赋值 $1,2,\ldots,n$，所有边表示的大小关系都会成立。

考虑逐步加入新位置。

从 $i=1$ 开始，不妨设 $p_1<p_2$，连边 $1\to2$。第 $i$ 条记录涉及位置 $i,i+1,i+2$，其中 $i,i+1$ 之间的大小关系在此前已经由已加的边（直接或经传递）确定，只有新位置 $w=i+2$ 与它们的关系需要新加边。

用布尔量 $b$ 表示当前是否有 $p_i<p_{i+1}$（初始为真）。按 $m_i$ 与 $le$ 分类，目标是让 $p_{m_i}$ 成为三者的中位数：

$b$	$m_i$	需要的大小关系	新加的边	新的 $b$（即 $p_{i+1}<p_{i+2}$ 是否成立）
真	$i$	$w<i<i+1$	$w\to i$	假
	$i+1$	$i<i+1<w$	$(i+1)\to w$	真
	$i+2$	$i<w<i+1$	$i\to w$，$w\to(i+1)$	假
假	$i$	$i+1<i<w$	$i\to w$	真
	$i+1$	$w<i+1<i$	$w\to(i+1)$	假
	$i+2$	$i+1<w<i$	$(i+1)\to w$，$w\to i$	真

表中每一行只加了必要的边，其余关系可由已有的 $p_i,p_{i+1}$ 之间的关系通过传递得到。例如「真 / $i$」一行，$w\to i$ 加上 $i\to\cdots\to i+1$，自然推出 $w<i+1$。

可能有疑问的地方（正确性）：

• 每一步新加的边都至少有一端是新位置 $w$，另一端是旧位置，且表中给出的三个位置之间的大小关系互相一致（是一个全序），因此不会产生环。归纳可知整个图始终无环。
• 每一步之后，$i,i+1,i+2$ 三者两两之间的大小关系都被图（直接或传递）确定，且 $p_{m_i}$ 是中位数，所以第 $i$ 条记录成立；同时新的 $le$ 恰好记录了 $p_{i+1}$ 与 $p_{i+2}$ 的大小关系，供下一步使用。
• 后续加边只会增加约束，不会改变已有位置之间已确定的大小关系，所以前面的记录不会被破坏。

因此对于任何满足 $i\le m_i\le i+2$ 的输入，都可以得到合法排列。

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

T6

100%

先考虑 $f(S[l,r])$ 怎么计算。对子串 $S[l,r]$，位置 $t\ (l\le t<r)$ 能切开，当且仅当 $S[l,t]$ 与 $S[t+1,r]$ 没有公共字母。所有能切开的位置可以同时切开：若某字母出现在两个不同的段里，它必然跨过某个切点，与该切点两侧无公共字母矛盾。所以

$$f(S[l,r])=1+\text{(子串内部可切位置的个数)}.$$

考虑算每个切割位置的贡献，故答案 $=\dfrac{n(n+1)}2+\sum_{t}(\text{位置 }t\text{ 在多少个子串中可切})$，前一项是每个子串的基础贡献 $1$。

固定切点 $t$ 统计。 令 $last_c$ 为字母 $c$ 在 $S[1,t]$ 中最后一次出现的位置（没有则为 $0$）。固定右端点 $r>t$，令

$$B=\max_{c\in S[t+1,r]}last_c.$$

右侧每个字母在左侧的所有出现位置都必须被排除，排除其最后一次出现就等价于排除全部出现，所以 $t$ 可切当且仅当 $l>B$，合法的 $l$ 有 $t-B$ 个。

$B$ 只会在 $r$ 第一次遇到某个新字母时变化，所以右端点至多分成 $26$ 组。设 $S[t+1,n]$ 中出现的字母按第一次出现位置从小到大排列为 $c_1,\ldots,c_s$，首次位置 $q_j=first_{c_j}$，并令 $q_{s+1}=n+1$。当 $q_j\le r<q_{j+1}$ 时，右侧字母集合恰为 $\{c_1,\ldots,c_j\}$，

$$B_j=\max_{h\le j}last_{c_h}, \qquad C_t=\sum_{j=1}^{s}(q_{j+1}-q_j)(t-B_j).$$

按顺序扫一遍，边扫边维护前缀最大值，即可在 $O(26)$ 内算出 $C_t$。最终

$$\text{答案}=\frac{n(n+1)}2+\sum_{t=1}^{n-1}C_t.$$

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