2021-10-05 10:05 已编辑中国石油大学（华东） Python

关注

2021牛客OI赛前集训营-普及组（第一场）题解

第一题优美的数

出题过程

Venn: 第一题怎么出
BLUESKY007:不如搞个矩阵加速的数位dp吧。
Venn:？（数据范围砍成log级别）

考察知识点

枚举，预处理

做法

由于给了样例 $k=2021$

我们可以对优美的数进行预处理，得到前 $2021$ 个优美的数。然后读入 $k$ 并输出答案即可。
总时间复杂度 $\mathcal{O}(k)$ 。
std:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48896072

第二题异或序列

出题过程

Venn:第二题搞个二分吧。
BLUESKY007:我更喜欢位运算，也是log的。
Venn:那就二分+位运算。

考察知识点

位运算，二分, 哈希

做法

对于前50%的点，我们考虑使用一个 $O(n^2)$ 的二重循环，枚举所有的数对，判断是否为答案。

对于接下来25%的数据，我们考虑 $a\ xor \ b = c$ 等价于 $a\ xor\ c = b$ .那么对于每一个 $a_i$ 都有一个固定的数 $ans = a_i\ xor\ X$ .我们用 $cnt[i]$ 记录数字 $i$ 的出现次数，即可统计答案。时间复杂度 $O(n+v)$ .
Tips : 此做法可以借助std::map 扩展到100%的情况,但是要取决于常数问题(由于常数问题，导致某不愿透露姓名的出题人挂了3个点)。

对于全部的数据，考虑排序数组后，每一个 $a_i$ 对应的 $ans$ 都是一个连续的区间。我们二分出左右端点，即可在 $O(n\log_2n)$ 的时间内统计答案。

std: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48896051

第三题分！身！术！

出题过程

Venn:整点高难度的，来个NOI题
BLUESKY007：差不多得了😓 给你题目名一样就行了

知识点

单调队列, two-pointer

做法

对于30%的数据，我们考虑枚举所有的区间，然后分别统计两人做题时间，判断是否可行，时间复杂度 $\mathcal{O}(n^3)$
对于60%数据，我们在枚举区间的同时，使用ST表 $\mathcal{O}(1)$ 统计两人的做题时间，判断合法性。时间复杂度 $\mathcal{O}(n^2)$
对于 $80\%$ 的数据，我们可以用"Two-Pointer"做法，用set数据结构，维护当前区间答案，并且可以在 $\mathcal{O}(\log n)$ 的时间进行转移，总复杂度达到了 $\mathcal{O}(n\log n)$
对于100%的数据，使用two-pointer在移动区间右端点时，使用单调队列，对 $a_i,b_i$ 分别维护最大值,最小值。当差值超过 $K$ 时，记录答案，并移动区间左端点位置。时间复杂度 $\mathcal{O}(n)$

std https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48896050

第四题种树

出题过程

Venn:我们好像没有出dp题啊
BLUESKY007：确实，也没有出图论
Venn:缝合起来

知识点

树形dp, 换根dp

做法

对于45%的数据，枚举受力点进行 $O(n^2)$ 的计算即可。

对于100%的数据：
首先，假设受力点为 $1$ 并计算此时的做功 $W_1$ ，时间复杂度 $\mathcal{O}(n)$

然后，我们考虑将受力点从 $u$ 转移到 $v$ （ $u$ 和 $v$ 之间有连边），可以得到对于 $v$ 的子树中的所有点 $i$ ， $dis_i$ 将减小 $1$ ，对于 $v$ 的子树以外的所有点 $j$ ， $dis_j$ 将增加 $1$ 。由此可知， $ans_v=ans_u-\sum_{i在v的子树内}w_i+\sum_{j不在v的子树内}w_j=ans_u+\sum_{i=1}^{n}w_i-2\sum_{i在v的子树内}w_i$ 。在预处理所有点的子树重量和的情况下，可以在时间复杂度 $\mathcal{O}(1)$ 内由 $ans_u$ 得到 $ans_v$ 。

总时间复杂度 $\mathcal{O}(n)$ 。

赛场总结

~~本场题目难度适中，考察知识点全面，给出题人点赞~~
中间看到有一位选手AK，但是又交了一发错误的C导致被卡到320，不过最后一分钟又交了正确的代码，成为AK人。
C题为了放过1e7数据量的读入，时间开到了2s,导致部分80分的做法加上快读通过了。
std https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48896053