竞赛讨论区 > 牛客练习赛 83 官方题解
头像
limpid_
编辑于 2021-05-25 16:23
+ 关注

牛客练习赛 83 官方题解

场上由于数据数据较水 $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$ 的性质考虑拆开维护



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

如果 $\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

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐