02-06 18:43 浙大宁波理工学院 C++ 发布于北京

关注

【题解】2025牛客寒假算法基础集训营4

A. Tokitsukaze and Absolute Expectation

根据期望的线性性质，可以转化成求 $|a_i-a_{i-1}|$ 的期望之和。那么问题就转化成了 $|a_i-a_{i-1}|$ 的期望。

分母显然，由于 $a_{i-1}$ 和 $a_i$ 在区间 $[l_{i-1},r_{i-1}]$ 和 $[l_i,r_i]$ 等概率随机，所以分母为 $(r_{i-1}-l_{i-1}+1) \cdot (r_i-l_i+1)$ 。

分子是 $a_{i-1}$ 和 $a_i$ 绝对值之差的所有情况之和。假设目前计算的是 $[l_1,r_1]$ , $[l_2,r_2]$ 。设 $[x,y]$ 为这两个区间的交，即 $x=max(l_1,l_2)$ , $y=min(r_1,r_2)$ 。然后通过下面 3 个部分进行计算：

$[l_1,x-1]$ 与 $[l_2,r_2]$
$[x,y]$ 与 $[y+1,r_2]$
$[x,y]$ 与 $[x,y]$

情况 1 和情况 2 很好算，因为它们区间都没有交。实现可以参考代码中的 cal2 函数。

情况 3 因为它是对称的，可以推出一个式子。式子可以参考代码中的 cal3 函数。

求完分子就做完了。

由于每次需要求一下分母的逆元，所以时间复杂度为 $O(n \log m)$ , $m=10^9+7$ 。

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

B. Tokitsukaze and Balance String (easy)

按题意模拟，直接暴力。时间复杂度 $O(2^n \cdot n^2)$ 。

需要注意的是，把 ? 填了之后，回溯的时候要填回 ?，不然下一次递归到这一层，这里就不是 ?，就错了。

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

C. Tokitsukaze and Balance String (hard)

对于长度为 $n$ 的01字符串 $s$ ，发现当 $s_1$ 与 $s_n$ 相等时 "01" 与 "10" 子串数量相等。所以 $2 \leq i \leq n-1$ 中的 ? 可以随便填，不会影响 "01" 与 "10" 子串数量。

令 $2 \leq i \leq n-1$ 中的 ? 个数为 $cnt$ 。

先不考虑 $s_1$ 与 $s_n$ 为 ? 的情况。

如果 $s_1=s_n$ ， $2 \leq i \leq n-1$ 中的 $s_i$ 可以随意翻转，即 $val(s)=n-2$ 。所以贡献为 $2^{cnt} \cdot (n-2)$ ；

如果 $s_1 \ne s_n$ ，则必须翻转 $s_1$ 或者 $s_n$ ，即 $val(s)=2$ 。所以贡献为 $2^{cnt} \cdot 2$ 。

至于 $s_1$ 与 $s_n$ 为 ? 的情况，可以再分类讨论一下。具体参考代码。

由于 $cnt$ 最多等于 $n-2$ ，所以我们可以预处理一下 $2$ 的幂，不需要用快速幂，时间复杂度为 $O(n)$ 。

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

D. Tokitsukaze and Concatenate Palindrome

贪心。考虑按某种顺序将回文两侧尽可能匹配上。

先让 $a$ 和 $b$ 匹配。如果 $n=m$ ，直接做完了。

否则肯定是一长一短，长的那个字符串会跨过回文中心，所以再自己匹配自己一下，把回文中心的部分匹配完。注意不要多匹配。

剩下的就是不能匹配的，直接数一下有多少个然后除二即可。如果有奇数个无法匹配的。那么 $n+m$ 肯定为奇数；否则肯定是偶数个无法匹配的，因为每次成功匹配都会使字符同时减少两个。所以直接除二就行。

单组时间复杂度 $O(n)$ ，如果把清空数组的时间复杂度算进去就是 $O(26T+n)$ 。

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

E. Tokitsukaze and Dragon's Breath

观察斜线的下标可以发现，每条斜线要么 $i+j$ 是固定的，要么 $i-j$ 是固定的。

于是可以用两个 map 记录所有 $i+j$ 与 $i-j$ 的和，然后枚举 'X' 的中点计算答案。

也可以不用 map，用数组，但需要加上一个偏移量来保证 $i-j$ 不是负数。

用数组实现的时间复杂度为 $O(nm)$ 。

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

F. Tokitsukaze and Kth Problem (easy)

Solution 1：二分答案

这类求第 k 大，或者前 k 大类的题，一般可以先考虑二分答案。

由于 easy 版本与序列顺序无关，所以可以先 sort，然后二分答案后用双指针数一下有多少对大于等于答案。

求出第 k 大后，大于答案的对可以暴力求出来，剩下的再用答案填。

时间复杂度 $O(n \log V + k)$ , $V$ 为值域。

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

Solution 2：堆

我们可以构造一种方案，使得堆内必定存在当前的最大值。这样只要从堆中弹出 $k$ 次就是前 k 大。

对于这道题，可以枚举 $a_i$ ，对于每个 $a_i$ ，找到与它匹配能使 $f(i,j)$ 最大的 $a_j$ 放入堆中。

每次从堆中弹出一个东西，我们就把下一个与 $a_i$ 匹配的 $a_j$ 放入堆中(如果有的话)。

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

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

G. Tokitsukaze and Kth Problem (hard)

本题沿用 easy 版本 Solution 2 的做法。

现在的问题就是无法对原数组进行排序后二分找匹配的 $a_j$ 。

由于 $0 \leq a_i \pmod p + a_j \pmod p < 2p$ ，我们可以将 $f(i,j)$ 的值分为两类。一类是 $0 \leq a_i \pmod p + a_j \pmod p < p$ ，另一类是 $p \leq a_i \pmod p + a_j \pmod p < 2p$ 。

对于第一类，我们需要实现的功能是：查询区间内小于 $p-a_i$ 的最大的数；对于第二类，只需要找到 $a_j$ 的最大值即可。

第二类很好解决，主要是第一类，问题转化成如何查询区间内小于 $p-a_i$ 的最大的数，没有修改。

std 的做法是建立一个线段树，每个节点用一个 vector 存放区间内的所有数。对于查询，找到这个区间对应的 $\log$ 个节点，然后在节点对应的 vector 内二分查找小于 $p-a_i$ 的最大的数，然后把这些节点的结果求个最大值。

在建立线段树的时候可以使用归并排序实现，时间复杂度为 $O(n \log n)$ 。但时间复杂度的瓶颈不在建树，查询时需要找到区间对应的 $\log$ 个节点，然后需要在每个节点的 vector 内二分，所以总时间复杂度是 $O((n+k)\log^2 n)$ 。

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

Bonus

上面分成的两类，发现选择第一类是优于选择第二类的。然后第一类内部是单调的，第二类内部也是单调的，并且第一类与第二类没有交。所以可以先求出符合第一类的数的个数，然后用 kth 求出值；第一类用完后，再开始使用第二类，同样的也是用 kth 求出值。这样可以用主席树来做，时间复杂度 $O((n+k) \log n)$ 。

H. Tokitsukaze and Necklace

显然是一个 dp 题。

$dp_{i,j,k,x,y}$ 表示当前使用了 $i$ 个 a $j$ 个 b $k$ 个 c，上两个字符为 $x$ ，上一个字符为 $y$ 的最大喜爱值。

转移的话很简单，就枚举当前填哪个字母，然后根据前两个字母和当前的字母计算贡献。注意填的每种字母数量不能超过给定的数量。

然后它是个环，所以需要断环成链，即枚举第一个字符和第二个字符填什么。

输出方案只需要在转移时记录一下上一个字符是什么，具体参考代码。

时间复杂度 $O(3^5 \cdot cnt_a \cdot cnt_b \cdot cnt_c)$ 。你可以写一个暴力枚举一下 $cnt_a \cdot cnt_b \cdot cnt_c$ 最大是多少，发现最大的情况是 $cnt_a=cnt_b=cnt_c=50$ 。所以时间复杂度为 $O(3^5 \cdot 50^3)$ 。空间复杂度是 $O(3^2 \cdot cnt_a \cdot cnt_b \cdot cnt_c)$ 。

思路简单，写起来繁琐，还容易写挂，而且还容易爆空间。

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

I. Tokitsukaze and Pajama Party

签到题。考察选手是否掌握循环语句，以及时间复杂度计算。

每次碰到 "uwawauwa" 子串时，假设最开头的 'u' 的下标是 $i$ ，只需要统计 $1$ 到 $i-2$ 中有多少个 'u'，累加就是答案。

如果每次都遍历 $1$ 到 $i-2$ ，时间复杂度为 $O(n^2)$ ，无法接受。我们可以用一个变量来维护即可 'u' 的个数。时间复杂度 $O(n)$ 。

需要注意的是，"uwawa" 最多有 $\frac{n}{5}$ 个，大致估算一下最终答案不会超过 int，所以不需要开 long long 也能通过。

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

J. Tokitsukaze and Recall

题目要求访问到的点数最多，并且访问顺序的字典序最小。

先解决点数最多的问题。求出每个连通块有多少个点，并按点的数量从大到小排序。这样肯定优先选择点数前 $k$ 多的连通块；如果 $k$ 大于等于连通块个数，可以全选。

再考虑字典序最小。首先在选连通块时，如果两个连通块的点数相同但只能选一个的时候，需要做一个选择。设连通块内编号最小的节点的编号为 $mn$ ，在排序时，优先选择 $mn$ 小的那个连通块。

统计连通块内节点个数与最小编号可以建图后 dfs 或者并查集实现。

为了使字典序最小，我们用一个优先队列来维护所有可访问的节点，每次弹出最小编号。

因为要求访问顺序字典序最小，所以仲裁者肯定会被部署在一个连通块的编号最小的节点上，也就是部署在连通块的 $mn$ 节点。所以最初，把所有选择的连通块的 $mn$ 节点都放入优先队列。

然后要注意，如果 $k$ 大于连通块个数，或者换句话说， $k$ 还有剩余，可以把剩余的 $k$ 服务于最小字典序。具体的，如果当前 $k>0$ ，并且存在编号比队列弹出来的编号更小的节点，那么直接在那个节点上部署是更优的。

由于使用了优先队列，每个节点最多会入队出队一次，所以时间复杂度 $O(n \log n)$ 。

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

K. Tokitsukaze and Shawarma

签到题，输出 $\max(\{x \times a,y \times b,z \times c\})$ 。

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

L. Tokitsukaze and XOR-Triangle

如果求的是 $\sum_{i=l}^r \sum_{j=l}^r a_i \oplus b_j$ ，那就是个大家都会的经典原题。但现在求的是 $\sum_{i=l}^r \sum_{j=i}^r a_i \oplus b_j$ 。直接做不好做，考虑把它拆解一下。

$\sum_{i=l}^r \sum_{j=i}^r a_i \oplus b_j$

$=\sum_{i=l}^r \sum_{j=i}^n a_i \oplus b_j - \sum_{i=l}^r \sum_{j=r+1}^n a_i \oplus b_j$

先看后一半 $\sum_{i=l}^r \sum_{j=r+1}^n a_i \oplus b_j$ ，这两个区间没有相交，所以可以转化成类似 $\sum_{i=l}^r \sum_{j=l}^r a_i \oplus b_j$ 的求法。即拆位后统计 $a_l,a_{l+1},\ldots,a_r$ 中这一位上有多少个 $0$ 和 $1$ ；再统计 $b_{r+1},b_{r+2},\ldots,b_n$ 中这一位上有多少个 $0$ 和 $1$ ，然后乘一乘。

再看前一半 $\sum_{i=l}^r \sum_{j=i}^n a_i \oplus b_j$ 。这一部分可以预处理出对于每个 $i$ ， $f_i=\sum_{j=i}^n a_i \oplus b_j$ 。然后记 $g_i = \sum_{j=1}^i f_j$ ，那么 $\sum_{i=l}^r \sum_{j=i}^n a_i \oplus b_j=g_r - g_{l-1}$ 。