2020-04-17 22:58 已编辑中国科学院大学算法工程师

关注

【题解】牛客挑战赛39

萌新出题人第一次出题，没把握好难度，被A穿了，十分抱歉

B题题面出了一些小锅，我已经帮大家喷过出题人了= =,~~如果大家有啥想喷的，欢迎私信我，我一定转达（雾~~

B会把之前wa的代码按原错题rejudge

A.聚会

显然一个传送门放在 $x=0$ ，另一个传送门放在位置 $x$ 非 0 的位置是最优的，否则我们将一个传送门挪到 $x=0$ 一定可以使得使用传送门的朋友们更快到达聚会地点。

剩下能放传送门只有一个，只能放在 $x < 0$ 或者 $x > 0$ 位置才有收益。

当所有朋友的家都在 $x > 0$ （或 $x < 0$ ）时，我们可以发现，假设传送门放在位置 $x_0$ ，对于所有 $x\ge x_0$ 的朋友，走传送门比不走传送门速度更快，而 $x<x_0$ 的朋友则需要讨论走到传送门更快还是直接奔向原点更快（因为传送门和原点在两个方向）。将朋友位置按 $x$ 坐标排序并重新编号后，不难发现一定存在一个编号 $i$ 使得编号 $1,2,\cdots,i$ 的朋友直接走向原点，而编号 $i+1,\cdots,n$ 的朋友们走向传送门。那么我们可以枚举这个前缀 $i$ ，让 $1,2,\cdots,i$ 的朋友直接走向原点，让剩下人走向传送门，问题转换为如何摆传送门，让 $i+1,\cdots,n$ 的朋友同时出发到达传送门的时间最短，注意题目要求只能摆在整点位置，容易发现摆在它们的中间位置是最优的。

当存在朋友的家 $x<0$ 也存在朋友的家 $x>0$ 时，需要分别讨论一下传送门放在哪一侧，计算其中一侧的朋友，另外一侧的朋友直接走向原点，最后取耗时更小的方案。

这个题也存在其它做法，方法大同小异。

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

B.密码系统

不难发现从某个起点 $i$ 开始进行 $k$ 段划分后，划分后的子串头部在原串位置的下标 $i\mod k$ 都相同，例如baca，若划分为ba和ca，则b和c对应下标为 $0$ 和 $2$ ，在取模 $k=2$ 意义下都是 $0$ ，而若划分为ac和ab，其中a对应下标分别是 $1$ 和 $3$ ，在取模 $k=2$ 意义下都是 $1$ 。因此原串下标按 $k$ 分组后，每一组的所有下标就是划分后子串的起始位置。

一种做法是对原串复制一遍后建立后缀数组，由后缀数组定义，rank 数组按 $k$ 分组后每组内的最大值就对应着每种划分的字典序最大的子串（备选密码），最后在所有备选密码中选取对应 rank 的最小值就是所有备选密码中字典序最小的密码。

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

C.牛牛的等差数列

比较经典的线段树问题

由于一个等差数列加上另一个等差数列，得到的还是一个等差数列，考虑对于线段树每个区间维护一个等差数列的首项和公差以及区间和，在push_down的时候可以 $O(1)$ 的计算出左右区间的公差首项以及增加的区间和，对于取模操作，只要维护区间的和对 $3*5*7*11*13*17*19*23$ 取模，最后得到答案的时候再取一次模即可。

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

D.牛牛的数学题

本题分为三个部分来分别处理

第一部分为 $i|j$ 且 $i\&j=0$ ，这部分可以通过子集卷积来解决

第二部分为 $+k$ ，这部分可以通过NTT来解决

第三部分为 $xor\ h$ ，这部分可以通过FWT来解决

分步来处理之后更新答案即可

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

E.牛牛与序列

不妨考虑容斥。不难知道， $n$ 个位置，每个位置填 $1...k$ ，总的填法是 $k^n$ 。对于所有不合法序列，先除去所有数字都相同的序列（一共 $k$ 个），其他的都是长度为 $n$ 的不下降或不上升序列。去掉的 $k$ 种既是不下降的又是不上升的。

显然不上升与不下降是对称的。只要求长度为 $n$ ，每个位置填 $1...k$ 的不下降序列的方案数即可。

记 $f[i][j]$ 为 $i$ 个位置，最后一个位置填数字 $j$ 的方案数。显然有 $f[i][j]=\sum_{t=1}^j f[i-1][t]$ 。那么最后的 $Q$ 就是 $\sum_{i=1}^k f[n][i]$ 。打个 $f$ 的表容易发现就是个斜着的杨辉三角，然后随便写个什么求组合数的就过了，出题人太鶸了

$f[1][i]=1$ ，定义 $g[t]=\{f[i][j]|i=t\}$ ，那么 $g[2]$ 可以对 $g[1]$ 做前缀和得到，显然可以用组合数直接表示。

以下用数学归纳法证明 $f[i][j]=C_{i+j-2}^{i-1}$ ：

当 $i=1$ 时，显然只有填一个数字 $j$ 的唯一方案， $f[1][j]=1=C_{j-1}^0$ ，成立。
若 $i=p$ 时 $f[p][j]=C_{p+j-2}^{p-1}$ 成立，当 $i=p+1$ 时， $f[p+1][j]=\sum _{t=1}^j C_{p+t-2}^{p-1}$ 。展开得 $C_{p-1}^{p-1}+C_p^{p-1}+...+C_{p+j-2}^{p-1}=C_{p-1}^0+C_p^1+...+C_{p+j-2}^{j-1}$ ，因为 $C_{p-1}^0=1=C_p^0$ ，所以可改写成 $C_p^0+C_p^1+C_{p+1}^2+...+C_{p+j-2}^{j-1}$ 。反复使用帕斯卡公式（ $C_{n-1}^{k-1}+C_{n-1}^k=C_n^k$ ）变换，得到 $C_p^0+C_p^1+C_{p+1}^2+...+C_{p+j-2}^{j-1}=C_{p+1}^1+C_{p+1}^2+...+C_{p+j-2}^{j-1}=...=C_{p+j-1}^{j-1}=C_{p+j-1}^p$ 。

所以 $f[p+1][j]=C_{p+j-1}^p=C_{(p+1)+j-2}^{(p+1)-1}$ 。

最后，不下降序列总方案数为 $\sum_{i=1}^k f[n][i]=\sum_{i=1}^k C_{n+i-2}^{n-1}=C_{n+k-1}^n$ 。

所以答案为 $k^n+k-2*C_{n+k-1}^n$ 。

由于 $n$ 范围较大，所以需要对 $C_{n+k-1}^n$ 稍微约分一下，显然实际需要乘进去的项不超过 $O(k)$

时间复杂度 $O(Tlogn+k)$ 。

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

F.树与异或
由于查询是离线的，两种询问可以分开做。

对于查询链上权值种类数，直接树上莫队即可。

对于查询链上权值是z的倍数的点个数，首先把1个询问拆成不超过3个的点到根的询问。考虑暴力枚举每种z，再把所有z的倍数加入计算。不难知道1e5以内的数的因子数规模最多约 $O(log^2n)$ 个。同时，每把一个点加入统计，影响的是这个点子树内的点到根的所有询问，此时答案+1。用dfs序+树状数组维护即可。

时间复杂度 $O(nlog^3n+n\sqrt{n}+q)$ 。但并不是每一种z都能达到 $O(log^2z)$ 的上界。

还可以对询问的z分块，对于 $z\le \sqrt{nlogn}$ ，直接dfs处理 $f[i][j],(j\le\sqrt{nlogn})$ 表示点i到根的路径上点权是j的倍数的点个数，当作答案。对于 $z>\sqrt{nlogn}$ ，仍然枚举z的倍数。但此时z的倍数不会超过 $\frac{n}{\sqrt(nlogn)}=\frac{\sqrt(n)}{\sqrt(logn)}$ 个，加上树状数组复杂度为 $\frac{\sqrt(n)}{\sqrt(logn)}*logn=\sqrt{nlogn}$ 。