2023-02-08 14:50 已编辑浙大宁波理工学院 C++ 发布于浙江

关注

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

题解写的比较匆忙，有误请指出。

2023.01.19 UPD：更新E题证明与三分反例，感谢这几位群友，以及提出疑问的群友：恶魔妹妹。

2023.01.25 UPD：更新一个牛客能跑4e10的证据。

这个提交在polygon不管用哪个版本的cpp都是TLE的，后台有n,q都大于1e5的数据。提交中的a数组把bool改成int会TLE，猜测是牛客神机把bool当成bitset，复杂度是nq/64，大概6e8，由于for里只有一个赋值语句，常数极小，所以跑的飞快。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60516804 alt

难度情况

出题时预估的难度：

easy: AB
easy-medium: DHJ
medium: CEFIL
hard: GK

内测&正赛：

easy: A
easy-medium: BDJ
medium: CFHL
hard: EGIK

内测后，通过率 (过题人数/有提交人数:3920) 预测情况： alt 可以看到与预想的还是有些差距（

题目花絮

BC是以前存的idea，然后兰子觉得B不够签，所以加了A。
D是临时想的，想出一道跟树和贪心有关的题，用来补足这套题没有贪心的缺陷，但想不出比较有趣的题。
E是以前存的idea，本来是求 $1$ 到 $m$ 中的那个 $f$ 最小是多少，后来觉得太简单了，加强了一下变成了这道题。最开始我也以为是个三分板子题，然后自己写了一个整数三分发现整数三分不能做这道题。我之前也不太熟悉三分，属于是自己出了个题把自己教育到了。
FG本来准备丢上Codeforces Round #789并分成easy,hard两个版本。首先被审题人说觉得F这个版本太简单了没什么意义，于是easy版本被毙了；hard版本进入了test阶段，然后被一个波兰final选手说这个题是一眼题，但写起来是"巨大的痛苦"，然后我说"代码能力也是算法竞赛的一部分"，但最后还是被毙了，于是就放到了寒假营里。
H也本来准备丢CF当div2的B题（当时的版本是输入 $k$ ，而不是现在 $k=1 \ldots n$ ），后来在赛前几场有一个题长的跟这题有点像，就换了（只是有点像，并不是原题），然后放到了寒假营里。放进来的时候觉得太简单了，于是就加强了一下（
I也本来准备丢CF当div2的C题，但审题人觉得没什么意思，就毙了。
J是以前做题遇到的一个子问题，结论挺简单的，就拿来当easy了。
K是根据一个工作内容演变出的idea（虽然最后没有应用到项目中）。本来想丢CF当div1的C题，后来出题组里的OI爷发现它的做法很像数三元环，就毙了。
L本来打算出成dp，后来发现容斥也能做，而且比dp做法简单，难度--

A. Tokitsukaze and a+b=n (easy)

签到题。枚举 $a$ = $L_{1}$ 到 $R_{1}$ ， $b = n - a$ ，再判断 $b$ 是否在区间 $[L_{2}, R_{2}]$ 中，如果是，答案 $+ 1$ 。

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

B. Tokitsukaze and a+b=n (medium)

根据 $a$ 的取值范围 $[L_{1}, R_{1}]$ ，我们求出能满足 $a + b = n$ 的 $b$ 的范围是 $[n - L_{1}, n - R_{1}]$ ，但是合法的 $b$ 的范围是 $[L_{2}, R_{2}]$ 。所以答案是区间 $[n - L_{1}, n - R_{1}]$ 与 $[L_{2}, R_{2}]$ 取交后的区间长度。

区间取交的区间长度可以这么计算：两个区间 $[a, b]$ ， $[c, d]$ 取交的区间长度为： $m a x (0, m i n (d, b) - m a x (a, c) + 1)$

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

C. Tokitsukaze and a+b=n (hard)

同样的，可以根据 $a$ 的范围 $[L_{i}, R_{i}]$ 能算出 $b$ 的范围 $[n - R_{i}, n - L_{i}]$ ，再与合法的 $b$ 的范围取交即可。由于这题变成了 $n$ 个区间，那么合法的 $b$ 的范围总共有 $n - 1$ 个（因为有 $1$ 个已经用来当成 $a$ 了）。但遍历每一个 $b$ 的合法范围时间复杂度是 $O (n^{2})$ 的，需要进行优化。

设 $d_{i}$ 表示 $b = i$ 时的区间个数。由于区间范围是 $1 0^{5}$ 级别，我们可以将 $n$ 个区间利用差分前缀和计算出 $d$ 数组。再做一次前缀和计算出 $b i t$ 数组。那么 $a$ 的范围是 $[L_{i}, R_{i}]$ 时，可能的 $b$ 的数量可以用通过 $b i t$ 计算出： $bit_{n-R_i}-bit_{n-L_i-1}$ 。但是要注意这样会把 $[L_{i}, R_{i}]$ 与 $[n - R_{i}, n - L_{i}]$ 相交的长度算进去，所以要减去。

计算时要记得取模。由于存在减法运算，要注意最后答案不要变成负数。

时间复杂度 $O (n + m)$

PS：本题还可以使用树状数组/线段树等数据结构进行区间求和。

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

D. Tokitsukaze and Energy Tree

可以发现当第 $i$ 个能量球放置在节点 $x$ 时，它的贡献为：节点 $1$ 到节点 $x$ 的高度 $h_{x}$ $\cdot$ 能量球的能量 $v_{i}$

于是我们可以贪心。求出高度 $h$ 后，分别对高度 $h$ 和能量 $v$ 排序，之后大的乘大的，再全部加起来即可。

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

E. Tokitsukaze and Function

通过暴力打表或者对 $f (x)$ 求导后，发现在 $x=\sqrt{n}$ 处 $f (x)$ 最小。但不确定是在 $\lfloor \sqrt{n} \ \rfloor$ 处还是在 $\lceil \sqrt{n} \ \rceil$ 处。

我们可以分别求出 $f (l)$ , $f (r)$ , $f(\lfloor \sqrt{n} \ \rfloor)$ , $f(\lceil \sqrt{n} \ \rceil)$ 进行排序，求出最小的 $f (x)$ 。

令 $f (t^{'})$ 为最小的 $f (x)$ ，现在要求最小的 $t$ 。显然在 $[1, t^{'}]$ 内的 $f$ 是单调递减的，所以我们可以在 $[L, t^{'}]$ 范围内二分求出 $t$ 。时间复杂度 $O(T \cdot \log{n})$

另外需要注意的是，本题无法使用三分解决，因为三分要求在极小值左边和右边都是严格单调的，而由于本题的 $f$ 函数有取整运算，可能使得函数的一些部分不是严格单调的，使用三分有可能找不到极小值点。

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

补充为什么直接三分不行：

alt

补充两位群友的证明：

群友1：

alt

群友2：

alt

F. Tokitsukaze and Gold Coins (easy)

显然，走进怪物格子一定不是最优解，所以我们把有怪物的格子当成障碍物来看。所以题目转化为：求 $(1, 1)$ 到 $(n, 3)$ 的所有路径能覆盖的格子数量。

我们可以通过两次 DFS/BFS 来搜索答案：

从起点 $(1, 1)$ 开始，向下/右走，标记所有能到达的格子。
从终点 $(n, 3)$ 开始，向上/左走，标记所有能到达的格子。

在这之后，只要统计哪些格子被标记过两次即可。

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

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

G. Tokitsukaze and Gold Coins (hard)

我们可以通过第一列和第三列来确定第二列的可行区域 $[L, R]$ 。

首先找到第一列向下的第一个障碍物，坐标为 $(r, 1)$ 。接着，我们通过 $r$ 来寻找可行区域的最大值 $R$ 。我们在第二列找到第一个大于等于 $r - 1$ 的障碍物，坐标为 $(x_{r}, 2)$ ，然后找到小于 $x_{r}$ 的第一个空白处，坐标为 $(R, 2)$ 。

同理，我们先找到第三列向上的第一个障碍物，坐标为 $(l, 3)$ 。接着我们通过 $l$ 来寻找可行区域的最小值 $L$ 。我们在第二列找到第一个大于等于 $l + 1$ 的空白处，坐标为 $(x l, 2)$ ，然后找到小于 $x_{l}$ 的第一个障碍物，坐标为 $(L - 1, 2)$ 。

可以用set分别维护障碍物和空白处，完成上述操作。

记 $r_{1} = m i n (r, R + 1) - 1$ , $l_{3} = m a x (l, L - 1) + 1$ 。

现在第一列的可行区域为 $[1, r_{1}]$ ;

第二列的可行区域为 $[L, R]$ ，

第三列的可行区域为 $[l_{3}, n]$ 。

如果 $L > R$ 或者 $l_{3} > R$ 或者 $r_{1} < L$ ，则无法从 $(1, 1)$ 走到 $(n, 3)$ ，所以答案是 $0$ 。否则答案为

$r_{1} + (n - l_{3} + 1) + (R - L + 1 - c o u n t (L, R))$

$c o u n t (L, R)$ 表示第二列 $L$ 行到 $R$ 行的障碍物个数，这个可以使用树状数组来维护第二列的障碍物得到。

总时间复杂度 $O(n \log{n})$ ，常数较大。

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

H. Tokitsukaze and K-Sequence

可以发现每种数字的贡献可以分开计算。我们按照每种数字出现的次数进行讨论。

假设数字 $x$ 出现的次数为 $c n t_{x}$ ：

如果 $cnt_x \leq k$ ，我们可以贪心地将每个 $x$ 都分到某个子序列中，使得每个子序列要么只包含 $1$ 个 $x$ ，要么不包含 $x$ 。所以此时数字 $x$ 的贡献为 $c n t_{x}$
如果 $c n t_{x} > k$ ，我们按照上面的方法分配完 $k$ 个 $x$ ，多出来的 $x$ 必须分配到某个子序列中，导致那个子序列中，数字 $x$ 没有贡献。所以此时数字 $x$ 的贡献为 $k - 1$

答案就是每种数字的贡献求和。

现在题目求 $k=1 \ldots n$ 的答案。我们对 $c n t$ 从小到大排序，枚举 $k=1 \ldots n$ ，答案为 $cnt_x \leq k$ 的 $c n t_{x}$ 求和，加上 $c n t_{x} > k$ 的 $c n t_{x}$ 的个数乘上 $(k - 1)$

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

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

I. Tokitsukaze and Musynx

先对 $x$ 排序。总共有 $5$ 个区间，枚举每个 $x$ 在哪个区间，二分出每个区间内包含几个 $x$ ，再乘上对应区间的 $v$ ，求和，即是当前情况的答案。最后对所有情况的答案取 max 即可。

具体的，我们可以枚举每个 $x$ 在哪个分界点上，来计算答案。实现的时候为了方便，求出当前枚举的分界点与第一个分界点的差值 $d e l t a$ ，将所有 $x$ 平移 $d e l t a$ 即可。

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

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

J. Tokitsukaze and Sum of MxAb

看到带有绝对值的式子，一般先展开绝对值。我们对 $a_{i}$ 和 $a_{j}$ 的正负进行讨论：

$a_{i} < 0$ , $a_{j} < 0$ 时， $\max(|a_i-a_j|,|a_i+a_j|)=|a_i+a_j|=|a_i|+|a_j|$
$a_{i} < 0$ , $a_{j} > 0$ 时， $\max(|a_i-a_j|,|a_i+a_j|)=|a_i-a_j|=|a_i|+|a_j|$
$a_{i} > 0$ , $a_{j} < 0$ 时， $\max(|a_i-a_j|,|a_i+a_j|)=|a_i-a_j|=|a_i|+|a_j|$
$a_{i} > 0$ , $a_{j} > 0$ 时， $\max(|a_i-a_j|,|a_i+a_j|)=|a_i+a_j|=|a_i|+|a_j|$

所以 $\max(|a_i-a_j|,|a_i+a_j|)=|a_i|+|a_j|$

那么原式 $\sum_{i=1}^{n} \sum_{j=1}^{n} MxAb(i,j)$

$=\sum_{i=1}^{n} \sum_{j=1}^{n} (|a_i|+|a_j|)$

$=\sum_{i=1}^{n} (n \cdot |a_i| + \sum_{j=1}^{n} |a_j|)$

$=\sum_{i=1}^{n} n \cdot |a_i| + n \cdot \sum_{j=1}^{n} |a_j|$

$= n \cdot \sum_{i=1}^{n} |a_i| + n \cdot \sum_{i=1}^{n} |a_i|$

$=2 \cdot n \cdot \sum_{i=1}^{n} |a_i|$

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

K. Tokitsukaze and Synthesis and Traits

题意转化为：给一张可能不连通的无向图， $q$ 次查询，每次给出 $k$ 个点，查询 $\frac{k \cdot (k-1)}{2}$ 条边中，有多少条边在原图中出现过。

Solution 1：给边定向

考虑给原图的边定向。设 $d_{x}$ 表示节点 $x$ 的度，则对于原图中的一条边 $(u, v)$ , 若 $d_{u} < d_{v}$ , 则连接 $u \rightarrow v$ ，否则连接 $u \leftarrow v$ 。给原图的边定向后，每个点的出边 $\leq \sqrt{m}$ 。对于每次查询，用桶记录每个点，然后直接遍历每个查询的点的所有出边即可，常数较小。总时间复杂度为 $O(\sqrt{m} \cdot \sum{k})$ 。

证明：对于一个查询的点 $x$ ，设 $c n t_{x}$ 表示 $x$ 的出边数量。若 $cnt_x < \sqrt{m}$ ，则显然遍历所有出边的时间复杂度小于 $O(\sqrt{m})$ ；若 $cnt_x \geq \sqrt{m}$ ，由于 $x \rightarrow y$ $(d_{x} < d_{y})$ ，则总边数最多为 $cnt_x \cdot d_y =m$ ，所以 $c n t_{x}$ 不超过 $\sqrt{m}$ 。

PS:如果看不太懂，画个图就明白了。

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

Solution 2：根号分治

对每组查询的点数按照 $w=\sqrt{\sum{k}}$ 进行分类：

若 $k \leq w$ ，则暴力枚举 $\frac{k \cdot (k-1)}{2}$ 条边，用 hash 判定是否在原图中出现。
暴力的时间复杂度为 $O (w^{2})$ ，这一情况出现的次数为 $\frac{\sum{k}}{w}$ ，因此总时间复杂度不超过 $O(w \cdot \sum{k})$
若 $k > w$ ，则暴力枚举所有查询点的出边。
暴力的时间复杂度最坏为 $O (m)$ ，这一情况出现的最大次数为 $\frac{\sum{k}}{w}$ ，因此总时间复杂度不超过 $O(w \cdot m)$ 。

由于 $\sum{k}$ 与 $m$ 的数量级一致，所以两种做法的时间复杂度区别不大，但是根号分治需要多一步 hash ，常数较大。

如果你是手写hash，那么是可以过的：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60500261

如果你是用gp_hash_table，那么也是可以过的：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60500349

但如果你是用unordered_map，那么残念，会TLE（也可能是我写臭了）：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60500358

L. Tokitsukaze and Three Integers

Solution 1：容斥

$d p_{x}$ 表示 $a_i \cdot a_j \equiv x \text{ (mod } p)$ $(i \ne j)$ 的个数，可以在 $O (n^{2})$ 的时间复杂度内计算出来。

接下来枚举 $k$ ，计算 $a n s_{x}$ 满足 $(a_i \cdot a_j) + a_k \equiv x \text{ (mod } p)$ $(i \ne j)$ ，时间复杂度为 $O (n p)$ 。

但这样会把 $i = k$ 或者 $j = k$ 的情况计算进答案，我们需要把这部分减掉。枚举 $i = k$ 的情况，减去 $a n s_{x}$ 满足 $(a_i \cdot a_j) + a_i \equiv x \text{ (mod } p)$ $(i \ne j)$ ， $j = k$ 的情况同理。时间复杂度为 $O (n^{2})$ 。

总时间复杂度为 $O (n^{2} + n p)$ 。

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

Solution 2：dp

我们让 $i, j, k$ 有序，分两种情况：

$k$ 在左边或者右边，即 $[i, j, k]$ 或者 $[k, i, j]$
$k$ 在中间，即 $[i, k, j]$

由于 $a_i \cdot a_j = a_j \cdot a_i$ ，所以不需要管 $i$ 和 $j$ 的顺序，最后答案乘 $2$ 即可。

对于情况1，只需要正着做一遍dp，倒着做一遍dp即可：
$dp_{x,y,0}$ 表示前 $x$ 个数，已经选了 $a_{i}$ ，且 $a_i \equiv y \text{ (mod } p)$ 的方案数；
$dp_{x,y,1}$ 表示前 $x$ 个数，已经选了 $a_{i}$ 和 $a_{j}$ ，且 $a_i \cdot a_j \equiv y \text{ (mod } p)$ 的方案数；
初始化 $dp_{x,a_x \bmod p,0}=1$ ，表示选 $a_{x}$ 作为 $a_{i}$
转移：
$dp_{x,y,0}$ += $dp_{x-1,y,0}$ ，表示不选 $a_{x}$ $dp_{x,y,1}$ += $dp_{x-1,y,1}$ ，表示不选 $a_{x}$ $dp_{x,(y \cdot a_x) \bmod p,1}$ += $dp_{x-1,y,0}$ ，表示选 $a_{x}$ 作为 $a_{j}$ $ans_{(y + a_x) \bmod p}$ += $dp_{x-1,y,1}$ ，表示选 $a_{x}$ 作为 $a_{k}$
发现 $d p$ 的第一维 $x$ 只跟 $x - 1$ 有关，可以用滚动数组优化掉这一维。
对于情况2，我们依然枚举 $k$ ， $d p 2_{y}$ 表示合法的 $(a_i \cdot a_j) \bmod p = y$ 的数量。
先将 $a_1 \cdot a_2$ , $a_1 \cdot a_3$ , $\ldots$ , $a_1 \cdot a_n$ 更新进 $d p 2$ 。
枚举合法的 $k$ ，从 $2$ 到 $n - 1$ 。假设当前 $k = x$ ：
把 $a_{x}$ 作为 $a_{j}$ 的不合法贡献从 $d p 2$ 中删去选 $a_{x}$ 作为 $a_{k}$ 计入答案： $ans_{(y + a_x) \bmod p}$ += $d p 2_{y}$ 把 $a_{x}$ 作为 $a_{i}$ 的合法贡献加入 $d p 2$