2021-06-13 12:16 已编辑 C++

关注

【题解】牛客练习赛84

A - 牛客推荐系统开发之静态特征获取

Solution

C++用STL的std::map以及std::set就可以解决了。

Code

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

B - 牛客推荐系统开发之女装药水

Solution

显然在某个位置扔两次女装药水和不扔是同样的效果。

状态压缩枚举每一个位置扔或不扔即可。

Code

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

C - 牛客推荐系统开发之选飞行棋子

Solution

令这四个人分别为ABCD。

枚举A和B的情况，时间复杂度 $O(n^2)$ 。

枚举C和D的情况，时间复杂度 $O(n^2)$ 。

将枚举的情况容斥整合，时间复杂度 $O(n^2)$ 。

（还有复杂度更低的做法）

Code

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

D - 牛客推荐系统开发之动态特征获取

Solution

用一个单调链表以存优先级顺序存放动态特征的指针，用另一个单调链表以动态特征拿取时间顺序存放动态特征的指针。

用两个哈希表（或大数组）存放某个编号的动态特征在两个链表中的位置。

然后按照题目要求进行模拟即可。

除了排序部分时间复杂度为 $O(n\log(n))$ ，其余部分时间复杂度为 $O(n)$ 。

时间复杂度 $O(n\log(n))$ 空间复杂度 $O(n)$ 或 $O(n+10^{7})$ 。

Code

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

补充

出题人在某公司的推荐系统后端开发中实习过一段时间，由此设计出了D题，本题错误率很高。

有两位同学分享了他们的解法：

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

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

通过对拍数据发现，这两个同学都是因为置信度不够的特征有可能没有被删掉导致答案错误。

如果还有用类似算法的同学可以通过下面的这组数据来验证一下：

输出应该为：

YES
YES
YES
YES
YES
YES
NO
NO
YES
NO

当然，过了这组也不一定能通过本题，如果这组数据过了，Windows平台下可以用下面的代码进行对拍：

import os
import cyaron

os.system("g++ -o std std.cpp -O2")
os.system("g++ -o user user.cpp -O2")

for i in range(100):
    io = cyaron.IO(file_prefix='', data_id=1)
    n = 30
    io.input_writeln(n, 3, 5)
    for i in range(n):
        io.input_writeln(cyaron.randint(1, 5), i + 1)
    io.output_gen("std")
    io.close()
    os.system("user < 1.in > user.1.out")
    if os.system("fc 1.out user.1.out > out") != 0:
        print('found')
        break

~~环境配不了的自己写对拍~~

E - 牛客推荐系统开发之标签重复度

Solution

考虑点分治：

对于经过某点 $u$ 的路径，显然都能拆分为两条以点 $u$ 为起点的路径。

对任一路径 $p$ ，可以表示为 $p = (x, y)$ ，其中 $x$ 为路径上最小的权值， $y$ 为最大的权值，显然路径对答案的贡献为 $x\cdot{y}$ 。

那么，对于两条以点 $u$ 为起点的路径 $p_{a}$ 和 $p_{b}$ ，拼接得到的路径 $p_{ab}$ 即为 $p_{ab} = (\min(x_{a}, x_{b}), \max(y_{a}, y_{b}))$ 。

如何在已知 $p_{a}$ 和 $p_{b}$ 的条件下求 $p_{ab}$ 的贡献？容易发现，对任意两条路径的拼接，都能归结为以下三类中的一类：

$x_{a} < x_{b}$ , $y_{a} < y_{b}$
$x_{a} < x_{b}$ , $y_{a} \geq y_{b}$
$x_{a} = x_{b}$

对上述三种情况分别做一次二维偏序即可。

二维偏序的时间复杂度为 $\rm{O}(n\cdot{\log(n)})$ ，故点分治的总时间复杂度为 $\rm{O}(n\cdot{\log^{2}(n)})$ 。

Code

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

F - 牛客推荐系统开发之下班

Solution

$\begin{align}&\sum\limits_{i_{1}=1}^{n}\sum\limits_{i_{2}=1}^{n}\sum\limits_{i_{3}=1}^{n}\cdots\sum\limits_{i_{k}=1}^{n}\gcd(f(i_{1}),f(i_{2}),f(i_{3}),\cdots ,f(i_k)) \\=&\sum\limits_{i_{1}=1}^{n}\sum\limits_{i_{2}=1}^{n}\sum\limits_{i_{3}=1}^{n}\cdots\sum\limits_{i_{k}=1}^{n}f(\gcd(i_{1},i_{2},i_{3},\cdots,i_k)) \\=&\sum\limits_{d=1}^{n}f(d)\sum\limits_{i_{1}=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{i_{2}=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{i_{3}=1}^{\lfloor\frac{n}{d}\rfloor}\cdots\sum\limits_{i_{k}=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i_{1},i_{2},i_{3},\cdots,i_{k})=1]\\=&\sum\limits_{d=1}^{n}f(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)(\lfloor\frac{n}{d\cdot i}\rfloor)^{k}\end{align}$

莫比乌斯函数前缀和用杜教筛很容易求。

斐波那契数列前缀和求法：

显然， $\sqrt{5}$ 可以用二次剩余求得 $616991993$ 或 $383008016$ 。

可以知道 $f(n)=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$ 。

令 $p=\frac{1+\sqrt{5}}{2}$ ， $q=\frac{1-\sqrt{5}}{2}$ 。

则有

$\begin{align}&\sum\limits_{i=1}^{n}f(n)\\=&\frac{\sqrt{5}}{5}(\sum\limits_{i=1}^{n}p^{i}-\sum\limits_{i=1}^{n}q^{i})\\=&\frac{\sqrt{5}}{5}(\frac{p^n-1}{p-1}-\frac{q^n-1}{q-1})\end{align}$