【题解】牛客练习赛62

A 牛妹的游戏

不妨假设绿方已经控制了所有蓝方没有控制的链,此时存在一个结论:当 时答案必定为 yes。这就是拉姆塞结论,下面给出简单证明:

假设 个据点分别为 ,那么在 连向其它据点的控制链中,必然至少有 条链被同一方控制,不妨假设它们为 。如此一来只要 中有任意一条链也被这一方控制,则可以形成控制区域;如果这三条链都没有被这一方控制,也就意味着它们都被对方控制了,则它们同样可以形成控制区域。

于是这道题只有在 时会出现答案为 no 的情况,这部分直接暴力判断即可。


B 病毒扩散

问题可以转化为以下模型:

多次询问从点 出发,每个时刻可以选择将 坐标或 坐标增加 或不走动,时刻 走到点 的方案数量。

如果要在时刻 走到点 ,那么必定有 个时刻选择走动,共有 种方案。

同时,走动的 步中有 步需要将 坐标增加 ,其余的需要将 坐标增加 ,共有 种方案。

于是答案即为 ,预处理组合数可以做到 查询,总时间复杂度为


C 牛牛染颜色

这是一道树形dp。

我们记 表示选择/不选择 这个节点后以 为根的子树的合法方案数。

我们分开来转移:

  • 若选择 这个节点,则子树内可以随便选点,那么转移方程就是:
  • 若不选择 这个节点,则只能选择其中一颗子树的节点或者一颗都不选,否则在 的子树内就会存在两个点 使得 ,这样就不满足题意了。

注意: 包含空集的方案,所以在枚举子树统计的时候每颗子树贡献的答案要减 ,但最后也要把空集的情况算上,还要加个

转移方程就是:

这样就能在 的时间复杂度内解决本题。


D 牛牛的呱数

首先这道题题目很容易联想到 dp,但是由于拼接顺序是不确定的,dp 是有后效性的。

但是我们可以把 dp 的状态变成节点,转移边做带权边,跑最短路。

我们可以这样设计节点:

一个二元组 表示 ,( 是数字串 的串长) 且数字串 的值 后的值为

对于每个串可以这样连边:(设长度为 ,模 后的值为 )

对于每个 连向 ,边权为

还要建一个超级起点和超级终点,超级起点连向各个只有一个串的状态,每个 的状态连向超级终点。

直接连边用 Dijkstra 算法跑最短路即可。

由于边数是 级别的,所以时间复杂度:


E 水灾

根据题目中所说:"将图中所有所有边权小于等于 x 的边删除",不难想到可以把原图的 Kruskal 重构树建出来,

那么原题就转化为:在重构树上删去若干个点,使得被询问的点互不连通。

由于 Kruskal 重构树的性质:每个节点的权值肯定小于等于它的子树中任意一个点的权值,可知删去重构树上的点深度越小越好。

最优情况可以是删去所有任意被询问两点的

由于我们只需要知道这些被删去的点中点权的最大值,所以我们只用知道把被询问点按照 dfs 序排序。

那么每组询问的答案就是排序后所有被询问相邻两点的所有 的点权的最大值。

非相邻两个被询问点的 一定是某相邻两点的 的父亲,它的点权一定不是最大的,所以就不需要查询。

时间复杂度:


F 牛牛的繁星

根号科技练手好题,难度并不是很大。

离线做法

考虑使用莫队,维护每个数的出现次数,然后使用平衡树维护出现次数,每次挪动端点至多改变 个出现次数,因此复杂度是 的,总时间复杂度为

一些优化

仍然考虑莫队,这次我们想办法去掉平衡树的 。考虑别的什么方法维护出现次数,可以做到 单点修改,并可以在不超过 的复杂度内查询第 大,显然有一个值域分块做法。

我们考虑对出现次数分块,然后维护每个出现次数的个数,以及块内所有出现次数的个数,修改时只会改动 的信息,查询时从大到小枚举整块,然后在块内枚举出现次数即可,总时间复杂度为

强制在线

有很多做法,我介绍其中一种做法。先序列分块,考虑维护前缀块中每个数的出现次数。

再考虑将数分为两类:出现次数大于 的,我们称为 A 类数;出现次数小于等于 的,我们称为 B 类数。可以发现,A 类数至多只有 个。

考虑维护两两块间出现次数为 的 B 类数分别有多少。查询的时候先查整块中出现次数为 的 B 类数的个数,然后枚举 A 类数,将出现次数小于等于 的也算到前面,剩下的留下来。接着扫描散块,如果是 B 类数则算入前面的贡献,否则像之前处理 A 类数一样分开。

最后我们得到了若干 A 类数,它们的出现次数一定大于 ,用我们刚刚优化莫队的那个查询第 大的技巧处理这部分即可,剩下的数出现次数必然在 间,暴力枚举即可,总时间复杂度为

全部评论
为什么E题直接建生成树,然后每次查询dfs序相邻两点路径上的最小边权,是错的呀。求大佬解释
1 回复 分享
发布于 2020-04-24 22:14
orz
点赞 回复 分享
发布于 2020-04-25 20:28
F题维护好前缀块中出现次数为 1 ~ 根号n 的 B 类数各有多少以后怎么差分呀。。 比方说如果要求第 x 个块中出现 y 次的数有多少个,该怎么做呀
点赞 回复 分享
发布于 2020-04-25 12:34
B题题解有误,应该是x+y个时刻选择走动
点赞 回复 分享
发布于 2020-04-25 00:39
讲道理 F写了个按答案bigsmall 没调块大小冲了个n\sqrt n\log n就冲过去了.. 是不是因为没有随机数据的原因233333  随机数据应该就过不去了qaq
点赞 回复 分享
发布于 2020-04-24 23:03
没有数理基础的我,做 A 的时候留下了悔恨的泪水。😥
点赞 回复 分享
发布于 2020-04-24 22:40
E题出题人出来谢罪了,有点卡常QAQ.
点赞 回复 分享
发布于 2020-04-24 22:24
F 题 在线莫队好像复杂度也只有 1e8 左右,应该也能过(大概
点赞 回复 分享
发布于 2020-04-24 22:18

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
CARLJOSEPH...:宝宝你戾气太大了
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
9
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务