2024-02-06 00:35 已编辑浙大宁波理工学院 C++

关注

【题解】2024牛客寒假算法基础集训营2

前言

赛中一位同学过了L没过K，这位同学的代码wa在了K的小数据，但由于牛客塞不下那么多组数据，那组数据没加在L和M中，出题人为此谢罪（悲）。过会儿会在L和M中放那组小数据。

然后请大家锐评一下本场比赛与题目，问卷链接：https://www.wjx.cn/vm/OowqS3N.aspx#

难度情况

出题时预估的难度：

通过率 (过题人数/有提交人数:4526) 预测情况： alt

主要偏差大的是：BIJK

B：主要是题意有一些不清，以及可能萌新对循环没那么上手(?)

IJ：似乎很多同学都被无向图和完全图的概念卡了，题目本身难度不大

K：前排大佬想直接冲LM，后排在跟榜，导致中后期才被大家发觉K不难

题目花絮

A：玩红烧天堂玩的。
B：本来是放去年寒假营的，后来删了，就挪到今年了。
C：同IJ，本来想放CF2D
D：玩游戏王玩的。idea 来源已经写在题面里了，就是在知乎上看见一个回答说用魔救拔刀。
EF：idea 源于 2023 ICPC 杭州站 K题，其中 easy 版本由智乃提出。
GH："我想出一个有关线段树的数据结构题"，想了好几天，突然翻到一个以前的idea "查询i在区间[L,R]中 sum(1,i)-sum(i+1,n) 最大"，然后发现还能加强，于是就加强了一下变成这题。easy 版本原本想着：不带修答案不就是查询的区间 $[L,R]$ 的和，减去 $2 \cdot a_R$ ？简单前缀和题.jpg 结果一写发现假了，样例都过不去，然后发现还是一个区间 RMQ 问题无法简化，干脆就带修了。
IJ：去年还是前年脑补出来的题，本来打算再出一场CF，两题合一放2C，后来怕协调员又是 74TrAkToR（我的上一场CF的协调员就是他，把我的题几乎毙光了，然后最近他又一堆负面新闻，所以...），而且也没有很多后补题，就不想出CF了，于是就把这两题放到寒假营了。
KL：CF1575D 超级加强版。去年某天打算出一场小白赛，准备把这题当小白F，然后在出的时候一不小心又被我狠狠的加强了一下，写完std后发现好像不适合放小白F，于是那场小白就被我鸽了（之后qcjj偶尔会拿我鸽小白这件事来diss我）。easy 版本目的是让萌新练练码力。
M：本来是没有这题的，赛前两天一个牛逼验题人说有更快的做法，然后我看了一下 hard 的代码，确实，于是就有了这题。

A. Tokitsukaze and Bracelet

签到题，按题意模拟即可。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154445

B. Tokitsukaze and Cats

不考虑相邻，答案是 $4 \cdot k$ 。

相邻会使答案变小，我们统计每只猫与几只猫相邻，然后把结果求和。

假设结果求和后的变量叫 $cnt$ ，于是答案为 $4 \cdot k - \dfrac{cnt}{2}$ 。显然 $cnt$ 是偶数可以直接除。

时间复杂度 $O(k + n \cdot m)$ 。

当然，如果把 $k$ 只猫的坐标都丢进 set 或者 map，然后枚举每只猫的 $4$ 个方向判断是否有其他猫，时间复杂度可以做到 $O(k \log k)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154466

C. Tokitsukaze and Min-Max XOR

由于求的是子序列，套路的，我们可以对 $a$ 进行排序。

排序后发现，当 $max=a_i,min=a_j$ 时，中间数可以随便选，如果这组 min 与 max 满足条件，那么答案是 $2^{i-j-1}$ ，特别的，当 $i=j$ 时，答案是 $1$ 。

但这个做法既要枚举 min 又要枚举 max，是 $O(n^2)$ 的。遇到这种情况，优化思路大多都是枚举一个，快速查询另一个。由于条件是异或，我们考虑 01字典树 (01 Trie)。把比当前枚举的 $a_i$ 小的数全部插入进 Trie 里，这样每次就能在 $O(\log n)$ 的时间复杂度内求出所有满足条件的 min 的信息。

此时又有新的问题：怎么用 Trie 维护答案信息呢？

对于一个 $a_j$ ，它贡献的答案为 $2^{i-j-1}$ 。我们可以将这个式子拆掉： $2^{i-j-1}=\dfrac{2^{i-1}}{2^{j}}$ ，于是 $i$ 与 $j$ 就分离了。所以我们可以把 $v_i = \dfrac {1} {2^{i}}$ 插入。当 $max=a_i$ 时，在 Trie 中查询 $\sum v_j$ , $(a_j \oplus a_i \leq k)$ ，此时贡献为 $1 + 2^{i-1} \cdot \sum v_j$ 。

$2^i$ 与 $\dfrac {1}{2^i}$ 都可以预处理求出（ $\dfrac {1}{2^i}$ 要用到逆元）。然后枚举 max，每次在 Trie 中查询，总时间复杂度为 $O(n \log n)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154476

D. Tokitsukaze and Slash Draw

Solution 1：dp

验题过程中发现有各种姿势的 dp，这里给大家举个例子。

$mn_i$ 表示在 $\bmod n$ 条件下目标卡片向上移动 $i$ 步的最小 cost 。对于每种操作分别枚举使用了 $j$ 次该操作，卡片向上移动了 $nxt$ 步时的 cost，由于在 $\bmod n$ 条件下操作 $n$ 次后卡片会一定会回到当前位置，所以操作次数 $\geq n$ 次不会更优，因此这个数组可以在 $O(n \cdot m)$ 的时间复杂度内预处理出来。

然后就可以 dp 了。 $dp_{i,j}$ 表示最多移动了 $i$ 步，当前位置在 $j$ 的答案。转移只需要枚举初始在哪，然后通过初始的位置和移动了 $i$ 步计算出移动后的位置，更新 dp 数组即可。最终答案为 $dp_{n,n}$ ：最多移动了 $n$ 步，当前在位置 $n$ 。

时间复杂度 $O(n \cdot m + n^2)$

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154550

Solution 2：最短路

可以发现这题其实是一个起点为 $k$ 终点为 $0$ 在 $\bmod n$ 意义下的最短路。

类似同余最短路 ，我们枚举余数 $i=0, 1, 2, \ldots,n-2, n-1$ ，对于每个操作 $[a,b]$ ，连边 $i \rightarrow (i+a)\bmod n$ ，cost 为 $b$ ，然后直接跑 Dijkstra 即可。

此时如果使用堆优化的 Dijkstra，复杂度会多一个 $\log m$ （虽然也能过）。可以使用普通的暴力 Dijkstra，时间复杂度为 $O(n^2 + m)$ 。由于建图的时间复杂度为 $O(n \cdot m)$ ，所以总时间复杂度与 dp 做法一致。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154497

E. Tokitsukaze and Eliminate (easy)

考虑贪心，模拟每一步，只要每一步都能够消除最多的宝石，总操作次数一定最少。

easy 版本只有两种颜色，也就是说每次操作只有两种选择：要么选择的颜色与最后一个宝石的颜色相同，要么不同。显然，选择与最后一个宝石的颜色不同的颜色，每次能消除最多的宝石。

最后可能会出现"剩下的宝石都是同一种颜色"的情况，这时候选择另一种颜色也没办法消除，只能一个一个消除。

所以根据上面的思路，直接从后往前模拟即可。

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154573

F. Tokitsukaze and Eliminate (hard)

Solution 1：基于 easy 版本思路的拓展

hard 版本颜色不止两种，但根据 easy 版本的贪心思路，我们只需要维护每种颜色的最后一个宝石出现的位置，每次操作选择位置最靠前的那种颜色，这样一次就能消除尽可能多的宝石。

于是我们只需要模拟上述思路即可，模拟的方法有很多，这里介绍一种方法。

我们开 $n$ 个vector 分别存下每种颜色的宝石下标。这些 vector 相当于是一个栈，其实也可以开 $n$ 个stack，一样的，只是个人习惯喜欢用 vector。

第一次我们先遍历 $n$ 种颜色，找到最靠前的下标。接着从后往前遍历宝石，遍历到的宝石一定在对应颜色 vector 的最末尾，消除它，就是把它从 vector 中 pop_back 掉。在这同时维护一个变量，表示此次遍历的宝石所对应的颜色最后一个宝石出现的位置。然后用这个变量进行下一次消除，直到所有宝石都被消除为止。

分析一下时间复杂度。每个位置只会进出一个 vector 各一次，每次消除每个宝石只会被遍历到一遍，所以总时间复杂度为 $O(n)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154596

Solution 2：转化成经典贪心模型

考虑相同颜色的两个相邻宝石，前一个在位置 $x$ ，后一个在位置 $y$ ，颜色为 $c$ 。显然，当位置 $y$ 的宝石未被消除时，不可能选择颜色 $c$ 来消除在位置 $x$ 的宝石。如果我们想要选择颜色 $c$ 来消除位置 $x$ 和 $x$ 之后的的宝石，当且仅当位置 $y$ 的宝石已被消除。也就是说，此时末尾宝石的位置必须要在 $[x,y-1]$ 中。

现在我们对每一个宝石都考虑这件事。 $nex_i$ 表示与第 $i$ 个宝石颜色相同的下一个宝石的位置，那么消除第 $i$ 个宝石与 $i$ 之后的所有宝石，需要末尾宝石在位置在 $[i,nex_i-1]$ 中。

然后你会发现，这么做之后就把这道题转化成了一个经典贪心模型：线段覆盖问题。我们需要选出最少的线段来覆盖 $1$ 到 $n$ 。由于线段是 $[i,nex_i-1]$ ，从前往后处理就能使线段有序，所以不需要排序，时间复杂度同样是 $O(n)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154611

Solution 3：线段树优化dp

没错，你甚至还能写线段树优化dp！

$dp_i$ 表示消除 $i$ 以及 $i$ 之后的宝石的最小操作次数。根据 Solution 2，可以从 $[i,nex_i-1]$ 的 dp 值转移过来。

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154621

G. Tokitsukaze and Power Battle (easy)

显然是一个数据结构题，需要支持两种操作：

1.单点修改

2.区间查询，在查询的区间中选出一个子段，再把子段切成两部分，求前一个部分的和减去后一个部分的和的最大值。

对于查询操作，有两个问题：

怎么选子段？
把子段切成两部分，在哪切？

可以看到 easy 版本中数字都是非负数，稍加思考可以得到两个显然的贪心结论：

假设我们已经选出了一个子段 $[x,y]$ ，那答案必定为 $\sum_{i=x}^{y-1} a_i - a_y$ ，也就是说 easy 版本省去了问题2 "在哪切"。
再多思考一下会发现，问题1 "怎么选" 也得到了简化。因为数字都是非负数，查询求的是前一段和-后一段和最大，所以前一段肯定尽可能长。那么对于查询的区间 $[L,R]$ 来说，肯定选 $[L,y]$ $(L+1 \leq y \leq R)$ 这个子段，那答案就变成了 $\sum_{i=L}^{y-1} a_i - a_y$ 。也就是说只要确定了 $y$ ，就能得出答案。

根据上述两个结论，现在考虑如何求答案。

考虑维护区间中每个 $y$ 的答案 $ans_y$ 。我们发现答案的一部分由区间和构成，所以我们先用前缀和对答案的式子做一些化简变形：

令 $bit_i=\sum_{j=1}^{i} a_j$

$\sum_{i=L}^{y-1} a_i - a_y$

$=\sum_{i=L}^{y} a_i - 2 \cdot a_y$

$=\sum_{i=1}^{y} a_i - \sum_{i=1}^{L-1} a_i - 2 \cdot a_y$

$=bit_y - bit_{L-1} - 2 \cdot a_y$

但这个式子还与 $L$ 有关，无法直接用一个变量维护它的最大值，于是我们可以分开维护：

维护 $mx$ ： $mx_y=bit_y - 2 \cdot a_y$
维护 $bit$

于是 $ans= \max_{i=L+1}^{R} mx_i - bit_{L-1}$ 。

注意此时单点修改 $a_x$ 会对区间 $[x,n]$ 中的 $mx$ 产生修改，所以其实是个区间修改。

我们可以使用线段树维护，支持 "区间加"，"区间求max" 即可。

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154633

H. Tokitsukaze and Power Battle (hard)

hard 版本跟 easy 版本比起来有了负数，easy 版本的两个贪心都无法使用了，此时无从下手。下面将介绍两种做法。

Solution 1：基于"区间查询最大子段和"思想

如果你熟悉线段树，做过"单点修改，查询区间的最大子段和" (洛谷P4513：小白逛公园)，那么这道题对你来说应该并不难。

你会发现，这题查询的东西跟"区间查询最大子段和"就差了一个符号，如果把减号改成加号就完全一致了。于是我们可以考虑用线段树直接维护答案。

首先考虑答案的组成，按减号在哪段进行讨论：

左边包含右端点的最大答案(减号在这整段中)-右边包含左端点的最小子段和
左边包含右端点的最大子段和+中间整段(减号在这整段中)-右边包含左端点的最小子段和
左边包含右端点的最大子段和+右边包含左端点的最大答案(减号在这整段中)
减号就是中间的减号：左边包含右端点的最大子段和-右边包含左端点的最小子段和

然后你发现其实可以上面第2种情况可以归类到第1种和第3种情况，因为：

左边包含右端点的最大答案=左边包含右端点的最大子段和+中间整段
右边包含左端点的最大答案=中间整段-右边包含左端点的最小子段和

所以我们需要维护：

区间和 $sum$
包含区间右端点的最大子段和 $rmx$
包含区间左端点的最小子段和 $lmn$
包含区间左端点或者右端点的最大答案 $lans$ $rans$
包含整段的最大答案 $segans$
区间答案 $ans$

然后写个合并节点的函数用于 pushup 和查询答案。

核心代码就是合并节点的函数 merge_node，其他部分就是输入和线段树模板。

alt

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154669

Solution 2：基于 easy 版本思路的拓展

根据 easy 版本的做法，我们同样先尝试对答案式子做变形，把答案式子用前缀和表示出来，假设答案区间为 $[x,z]$ ，切点为 $y$ ，前缀和为 $bit_i$ ：

$\sum_{i=x}^{y}-\sum_{i=y+1}^{z}$

$=(bit_y-bit_{x-1})-(bit_z-bit_y)$

$=-bit_{x-1} + 2 \cdot bit_y - bit_z$ ( $x-1 \neq y$ and $y \neq z$ )

显然，要使这个式子最大， $bit_{x-1}$ 与 $bit_z$ 都要尽可能小， $bit_y$ 要尽可能大。所以该怎么求呢？

其实，这玩意也可以使用线段树直接维护，我们需要维护：

区间前缀和 $bit$ 的最小值与最大值 $mn$ $mx$
$-bit_{x-1} + 2 \cdot bit_y$ 的最大值 $mxij$
$2 \cdot bit_y - bit_z$ 的最大值 $mxjk$
区间答案 $mxijk$

维护方法与 Solution 1 类似，可以参考下面的 merge_node 函数。

alt

不过此时我们维护的是前缀和 $bit$ ，所以单点修改要变为区间修改，区间修改就必然需要打标记和下放标记。所以对于区间修改，我们需要思考两个问题：

标记与标记如何合并
标记与值如何合并

由于这个区间修改就是普通的区间加，标记与标记直接累加即可，我们需要分析标记与维护的这些值如何合并。

假设现在要让区间加上 $v$ ：

对于最小值与最大值 $mn$ $mx$ ，将变为 $mn+v$ $mx+v$
对于 $-bit_{x-1} + 2 \cdot bit_y$ 的最大值 $mxij$ ，发现 $-bit_{x-1}$ 要变为 $-(bit_{x-1}+v)$ ， $2 \cdot bit_y$ 要变为 $2 \cdot(bit_y+v)$ ，所以对于 $mxij$ 总共多了一个 $v$ 的贡献，要变为 $mxij+v$
同理，对于 $2 \cdot bit_y - bit_z$ 的最大值 $mxjk$ ，要变为 $mxjk+v$
对于区间答案 $mxijk$ ，它所表示的式子为 $-bit_{x-1} + 2 \cdot bit_y - bit_z$ ，你会发现 $v$ 的修改被抵消光了，所以区间答案不变。

标记与值如何合并的问题解决了之后，这题也基本做完了。最后还有一个细节就是，我们维护的是 $bit_{x-1}$ ，这个需要对下标简单处理一下，可以参考代码中的 main 函数。

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154673

总结

Solution 1 的难点在于是否看出这道题是"区间查询最大子段和"的变形（其实我在出题的时候也没看出来，看到 emofunc 验题代码才发现的）。

Solution 2 的难点在于是否能发现 $-bit_{x-1} + 2 \cdot bit_y - bit_z$ 这玩意能够使用线段树直接维护。

总的来说这道题应该还算是比较有 edu 意义的，题解写的比较详细，希望大家都能学会。

I. Tokitsukaze and Short Path (plus)

拆开绝对值可以观察到：

在 $G$ 中， $w_{u,v}=2 \cdot \max(a_u,a_v)$ ，由于 $a_i$ 是正整数，绕路一定会加上正的贡献，所以绕路肯定不优。因此任意两个顶点 $u$ , $v$ 的最短路就是 $w_{u,v}$ ；

如何计算？我们先对 $a$ 数组从小到大排序，然后枚举 $a_i$ 当做当前的 $\max$ ，计算 $a_i$ 对答案的贡献。

答案为 $\sum_{i=1}^n 2 \cdot a_i \cdot (i-1) + 2 \cdot \sum_{j=i+1}^n a_j$

对 $a_j$ 求和的部分可以进行预处理，计算答案部分的时间复杂度为 $O(n)$ 。加上排序，总时间复杂度为 $O(n \log n)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154725

J. Tokitsukaze and Short Path (minus)

拆开绝对值可以观察到：

在 $G$ 中， $w_{u,v}=2 \cdot \min(a_u,a_v)$ ，考虑绕路的情况。假设绕一次路，肯定选 $a_i$ 最小的那个点走，那么此时答案就变成 $4 \cdot \min_{i=1}^n a_i$ ；假设绕两次路，显然边权没有负数，所以必定会加上一个正贡献，一定不如只绕一次路来的优。因此任意两个顶点 $u$ , $v$ 的最短路径要么是 $w_{u,v}$ ，要么是 $w_{u,x}+w_{x,v}$ ，其中 $x$ 满足 $a_x$ = $\min_{i=1}^n a_i$ 。

如何计算？同样的，我们先对 $a$ 数组从小到大排序，然后枚举 $a_i$ 当做当前的 $\max$ ，计算 $a_i$ 对答案的贡献。

计算时需要讨论绕不绕路。令 $pos$ 等于第一个 $i$ 满足 $2 \cdot a_{i} > 4 \cdot a_1$ ，答案为

$\sum_{i=1}^n \begin{cases} 2 \cdot \sum_{j=1}^{i-1} a_j + 2 \cdot a_i \cdot (n-i), & 2 \cdot a_i \leq 4 \cdot a_1 \\ 2 \cdot \sum_{j=1}^{pos-1} a_j + 4 \cdot a_1 \cdot (n-pos), & \text{other} \end{cases}$

对 $a_j$ 求和的部分可以进行预处理，计算答案部分的时间复杂度为 $O(n)$ 。加上排序，总时间复杂度为 $O(n \log n)$ 。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154730

K. Tokitsukaze and Password (easy)

Solution 1：模拟

使用 5 个循环直接枚举 a,b,c,d,_，的值，然后开个 set 暴力判重复值，特别好写。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154775

Solution 2：dfs

直接 dfs 即可。时间复杂度会比 Solution 1 低一些，但细节比较多。

不过这题也算是签到题，时限很宽，样例过了大概就过了。

PS：这题的答案不会超过 $10^9+7$ 。题面中写对它取模是因为要使 easy 版本的题面与 hard 版本的题面保持一致。

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154794

L. Tokitsukaze and Password (hard)

本题是一道 shit，核心考点比较简单，就是细节一堆。

本题的核心是：只要末尾3位能被8整除，这个数就能被8整除。因为1000是8的倍数，那1000的倍数一定是8的倍数，只要除以1000的余数是8的倍数，那么整个数就是8的倍数。

现在我们对4个限制一条一条分析：

"没有前导0"的限制十分好解决；
枚举1000内8的倍数，先把末尾3位确定，这样就解决了"8的倍数"的限制；

3." $x \leq y$ "的限制可以这样：从高位往低位枚举，假设当前位为 $i$ ，比 $i$ 高的位 $j$ 全部满足 $x_j=y_j$ 。如果 $x_i<y_i$ ，比 $i$ 低的位就可以随便填，此时计算贡献，接着令 $x_i=y_i$ ；如果 $x_i=y_i$ ，直接往后遍历；如果 $x_i>y_i$ ，直接不合法 break；

"不同字母代表的数字一定不同" 这条限制只需要每次记录哪些字母已经确定代表什么数字，哪些数字已经被用过。

所以我们可以枚举1000以内8的倍数，代入末尾3位。然后从高位往低位枚举，根据 $x_i$ 与 $y_i$ 的大小关系计算答案。细节比较多，具体可以参考代码。

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

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=67154815

M. Tokitsukaze and Password (hard)

本题是 shit 上加 shit。名副其实的 shit problem！

根据 hard 的做法，发现需要计算答案的只有：

下划线
未填的字母
$x_i \ne y_i$ 的第一个位置

进而发现：未填的字母最多只有 $10$ 个； $x_i \ne y_i$ 的第一个位置计算完后就直接 break 了；下划线计算贡献的式子可以合并。所以只需要合并下划线的计算，每次计算最多跳 $10$ 次位置，就能大大降低计算答案的时间复杂度。

我们可以预处理出每种字母出现的位置，用一个 vector 数组 $pos_i$ 表示；以及每种字母填了之后不等于 $y_i$ 的位置，用一个 vector 二维数组 $no\_eq\_pos_{i,j}$ 表示。这一步需要时间复杂度 $O(10 \cdot n)$ 。接着预处理出下划线贡献的前缀和；对于区间查询，会发现贡献要扣除 $r$ 之后的下划线个数的 $10$ 的幂，所以还需要预处理 $10$ 的幂的逆元。

计算答案与 hard 一样，先枚举1000内8的倍数，然后跳到那些需要特殊处理的位置计算。为了方便，代码中会跳到 $l$ ，未填的字母，以及最后3位，最多遍历14次，每次需要在之前预处理的 vector 中二分找最近需要遍历的位置。所以时间复杂度为 $O(125 \cdot 14 \cdot (10+\log n))$ 。