2019-10-28 14:27 已编辑邦邦大学 Java

关注

【题解】牛客小白月赛18

A.Forsaken喜欢数论

很显然， $f(x)$ 可以在线筛过程中维护出来，所以我们只需要做一遍线筛维护出所有 $f(x)$ ，然后求和就行了，复杂度 $O(n)$ .

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

B.Forsaken喜欢字符串

对于每个询问，本质上是求其他所有串的长度为 $len$ 的子串是串 $S_x$ 的子串的个数，然后总数乘上 $len$ 就是答案,注意到 $k$ 特别小，因此我们只需要存下每个串的所有哈希值，并且记录这个哈希值出现的次数，然后每次查询哈希值出现的次数就行了。复杂度是 $O(nk^2 +qk)$ 。

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

C.Forsaken给学生分组

签到题，我们将数组排序，然后取最大的 $k$ 个之和以及最小的 $k$ 个之和，相减就是答案。复杂度 $O(nlogn)$ 。

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

D.Forsaken喜欢正方形

简单计算几何，对于第一种情况，只需要会判断4个点能否构成正方形即可。

对于第二种情况，只需要枚举四个点，然后依次判断移动后能否构成正方形。

前两种都不行就是第三种。

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

E.Forsaken的数列

简单数据结构题。考虑这个题有动态插入点这个操作，因此我们很容易想到 $Splay$ 维护序列操作，因为我不擅长 ,所以提供一个无旋 $treap$ 的做法。

对于操作1，我们只需要分裂出 $Size$ 为 $pos-1$ 的子树，然后插入点合并就行了。

对于操作2，在无旋 $treap$ 的 $l$ 到 $r$ 区间的子树打上 $lazy$ 就行了。

对于操作3，取无旋 $treap$ 的 $l$ 到 $r$ 区间的和就行了。

复杂度 $O(qlogn)$

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

F.Forsaken的位运算魔法

类欧几里得算法套路题。我们对 $k$ 按位考虑，当 $k$ 的二进制第 $p$ 位为 $0$ 时，那么当且仅当 $ij$ 的第 $p$ 位为1时才有贡献。那么对于第 $p$ 位我们只需要计算有多少个 $ij$ 满足第 $p$ 位为1，这等价于计算 $\frac{ij}{2^p} - 2\frac{ij}{2^{p+1}}$ 的值。对于 $\frac{ij}{2^p}$ ,我们枚举每一个 $i$ ，然后问题就转换成对于所有 $j$ 求 $\frac{ij}{2^p}$ ,这是个经典的类欧几里得算法形式。

现在考虑第 $p$ 位为1的情况，那么问题转换成计算 $ij$ 第 $p$ 位为0时的贡献，那么我们转换成总数减去第 $p$ 位为1的个数就是答案。复杂度是 $O(cn(logn)^2)$ , $c$ 是一个非常大的常数。

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

G.Forsaken的三维数点

简单二分 + 树状数组统计。对于每个 $(x,y,z)$ 我们都可以算出距离原点的位置，然后我们把贡献算在这个距离向上取整的位置上。查询的时候只需要二分距离，然后树状数组统计这个距离内的能量和。复杂度是 $O(nlog^2n)$ 。

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

H.Forsaken喜欢独一无二的树

最小生成树统计冲突边。考虑问题形式我们可以转换成删掉所有可以代替最小生成树种某条的边的所有边权和。一个比较笨的做法是树上倍增，我们找出一颗最小生成树，然后枚举每条不在树上的边，判断两端路径上的最大边是否大于这条边，复杂度是 $O(mlogn + mlogm)$ 。

比较好的做法就是我们在构造最小生成树的时候直接计算每条可以加进最小生成树的边权和，然后最后减掉最小生成树的边权和就是答案。复杂度是 $O(mlogm)$ 。

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

I.Forsaken遇到了毒瘤

我们从 $m \% d + n \% d \geq d$ 这个限制入手。

众所周知, $n \% d = n - d\frac{n}{d}$ ，那么限制转换成 $m - d\frac{m}{d} + n - d\frac{n}{d} \geq d$ .

两边同除 $d$ 可得 .由于这个式子有天然的限制 $m - d\frac{m}{d} + n - d\frac{n}{d} \geq d$ .

同理可得 $\frac{m + n}{d} - \frac{m}{d} - \frac{n}{d} < 2$ 。由此可见 $\frac{m + n}{d} - \frac{m}{d} - \frac{n}{d}$ 的取值只有 $0,1$ 。

那么对于和式 $\sum_{d \in S(n, m)} \sigma(d)$ .我们写成 $res = \sum_{d} \sigma(d)[\frac{m + n}{d} - \frac{m}{d} - \frac{n}{d}]$ 。设 $g(n) = \sum_{d = 1} ^{n} \sigma(d) \frac{n}{d}$ ，可以发现 $g(n)$ 是个经典的数论函数求和，我们预处理出 $O(n^{\frac{2}{3}})$ 的 $\sigma(d)$ 函数的前缀和，然后整除分块就可以求这个积性函数和。那么有了 $g(n)$ ，我们可以把答案写成 $res = g(n + m) - g(n) - g(m)$ 。复杂度是 $O(n^{\frac{2}{3}})$ 。

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

J.Forsaken喜欢玩自走棋

我们设 $f(x) = \sum_{i \& x = x} a_i$ 。那么这个题就是求最大的 $f(x)$ 和对应的 $x$ 。显然有一个显然的枚举子集的做法，复杂度是 $O(3^m)$ ，考虑到这个题的 $m$ 最大可以到 $20$ ，所以这么做显然会 $T$ 。我们考虑 $SOSDp$ ，这个问题就是典型的 $SOSDp$ 问题，直接反着写 $SOSDp$ 的转移就行了。复杂度是 $O(m2^m)$ ， $m$ 是二进制最高位。

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