limpid_

题解牛客练习赛 83 官方题解

题解

/ 注册

牛客练习赛 83 官方题解

649 浏览 0 回复 2021-05-22

limpid_

+关注

牛客练习赛83_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

https://ac.nowcoder.com/acm/contest/11173

场上由于数据数据较水 $C,E$ 都有人骗过去，出题人在此谢罪。

祝大家 $5.21,5.22,5.23$ 愉快！

A

可以将题意简化成快速判断是否可以 $t$ 秒从 $(0,0)$ 到 $(x,y)$ 。

显然 $x+y$ 与 $t$ 的奇偶性是相同的，并且 $t\leq x+y$ 才能是 "Yes" 。

这也是充分的，因为可以到 $(x,y)$ 后上下上下循环走。

时间复杂度 $\mathcal O(T)$ 。

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

Challenge: 如果问求方案数怎么做呢？

B

由于是 $B$ 题就让数位 $dp$ 过了（

将询问差分，即 $[l,r]=[0,r]-[0,l-1]$ 。

而对于 $[0,x]$ 中，二进制下有奇数个 $1$ 的个数可以 $\lfloor\dfrac{x}{2}\rfloor+[x\&1\space or\space cont(x)\&1]$ ，其中 $cont(x)$ 表示二进制下 $x$ 中 $1$ 的个数。

证明需要分类讨论：
1.如果 $x$ 为偶数，那么 $x+1$ 为奇数，容易看出 $cont(x)$ 与 $cont(x+1)$ 的奇偶性是不同的，那么在 $[0,x]$ 中可以划分为 $\lfloor\frac{x}{2}\rfloor$ 个区间与若 $x$ 为偶数那么答案为 $\frac{x}{2}+cont(x)$ 。

2.若 $x$ 为奇数那么答案即为 $\frac{x+1}{2}$ 。

结合一下即为上式，时间复杂度 $\mathcal O(T\log r)$ 。

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

C

自然的想法是将 $n$ 个数放到同一个长度为 $p$ 的区间内进行模拟即可。

则我们考虑维护放到同一个区间过程，记录每次所需转移量即可解决。

最后会剩下小于 $n$ 次操作，直接模拟即可。

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

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

D

由于直接递推为 $\mathcal O(n^2)$ 的，而由于 $a\bmod b$ 的性质考虑拆开维护

$\begin{aligned} f_i&=\sum_{j=1}^i f_{i\bmod j}\\&=\sum_{j=1}^i f_{i-\lfloor\frac{i}{j}\rfloor\cdot j} \end{aligned}$

显然上述是一个数论分块的式子，考虑利用根号的性质解决。

如果 $\lfloor \frac{i}{j}\rfloor\geq \sqrt{n}$ 的 $j$ 只会有 $\mathcal O(n\sqrt{n})$ 个。

那么我们只需要关系 $<\sqrt{N}$ 的情况，由于上述 $dp$ 转移是一个长度以 $\lfloor\frac{i}{j}\rfloor$ 的一段区间和，不难想到通过前缀和实现。

设 $S_{i,j}$ 表示 $f_i+f_{i-j}+f_{i-2j}+f_{i-3j}+...$ 的和即可实现 $\mathcal O(1)$ 转移。

由于两部分时间复杂度均为 $\mathcal O(n\sqrt{n})$ ，总时间复杂度为 $\mathcal O(n\sqrt{n})$ 。

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

E

考虑当 $k=1$ 的情况，我们将点对 $(x,y)$ 表示 $ax+by$ 的结果。

由于 $gcd(a,b)=1$ ，所以对于 $\forall t$ ，都可以表示成 $ax+by$ 的形式，但是 $x,y$ 不一定均大于 $0$ 。

而一条斜线上的点 $(x,y)=t$ ，则 $(x-b,y+a)=t$ 。

而当 $k=1$ 时即为最大的斜线使得在第一象限内没有点。即为 $(-1,a-1),(b-1,-1)$ ，答案为 $ab-a-b$ 。

而当 $k>1$ 时我们发现当当 $(-1,a-1)$ 无法表示时， $(-2,a-1),(-1,a-2)$ 均无法被表示。

即 $(x,y)=t$ 无法表示时， $t-a$ 与 $t-b$ 均无法表示，并且此条件是充要条件。

那么问题转换为给定 $t$ ，每次操作可以减去 $a$ 或 $b$ ，求第 $k$ 大的数。

可以通过优先队列维护，时间复杂度 $\mathcal O(k\log k)$ ，无法通过本题。

线性做法

假设 $a<b$ 。由于答案不能算重则当减去 $b$ 时就不能在减去 $a$ 。

维护两个队列，一个队列表示当前能减去 $a$ ，另外仅能减去 $b$ ，那么每次在两个队头取最大的比较即可。

正确性类比 $NOIP$ 蚯蚓。时间复杂度 $\mathcal O(k)$ 。

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

F

显然有许多 $\mathcal O(n\log n)$ 的做法，但均通过不了此题。

对于每种相同的 $v$ 单独考虑，并将其树转成以 $1$ 为根的有根树。

我们设当前考虑的颜色为 $c$ ，考虑补集转换，若对于路径 $u\rightarrow v$ 不存在 $c$ 的话那么 $u,v$ 一定在一个不包含 $c$ 的连通块中。

我们只要找到对于颜色 $c$ 的极大不包含连通块，将其减去每个点答案减去连通块个数。

那么我们只要找到所有 $c$ 颜色的极大连通块即可，有一个很显然的是连通块一定仅包含一个根，而根的父亲的 $v$ 一定是 $c$ 。

现在我们已经知道每个点为根的颜色，而个数即为在该子树下做洪水填充时没有碰到 $v=c$ 时的结点个数。

而这个显然可以记 $tag$ 表示，需要注意一下许多颜色都有强连通块的根为 $1$ 的个数。

树上差分即可解决。

时间复杂度 $\mathcal O(n)$ ，代码有轻微卡常。

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

举报

收藏

赞

评论加载中...