【题解】牛客小白月赛6

T1 鲲

典型的追及问题,其中值得注意的是,HtBest反向游回起点时有可能被在起点等待的鲲抓到。

T2 鹏

考虑保存⼀下前⼀座⼭之后最低点,这时如果遇到下坡,就判断⼀下下坡后的点是否≥之前保存的最低点,如果是,则需要多翻越⼀次。

T3 桃花

两遍dfs,第⼀遍从任⼀点开始,找到距这个点最远的点,他⼀定是直径的⼀端,然后从这个点开始再dfs,找到最远的距离,输出即可。

T4 字符串丝带

考虑用⼀个数组保存下每个字母的最后出现位置,然后用⼀个数组ff[i]f,f[i]表示第ii个位置的该字母之前出现的次数即可。

T5 对弈

模拟下棋,下⼀步棋判断⼀下这个新落的⼦是否会影响胜负即可。

T6 发电

用树状数组维护每个节点的发电效率,除法用逆元搞。

T7 指纹锁

思考会发现set的实现⽅式与这个有惊⼈的相似处,需要重载⼀下运算符,差距小于k的返回相等,删除操作用while⼀个⼀个指纹来删,知道查询不到指纹xx为⽌。

T8 挖沟

裸的最小⽣成树。

T9 公交线路

原题目前我能想到的算法是O(n22n)O(n^2*2^n)的,显然通过不了n=100n=100的数据。

修改后该题是⼀个单源最短路问题,可以考虑使用Dijkstra或者SPFA算法实现。

T10 洋灰三角

矩阵快速幂,转移矩阵:

k 1 1 0

0 1 0 1

0 0 1 0

0 0 0 1

初始矩阵:

1 //答案

p //转移时需要加的值

1 //维护答案

p //维护转移时需要加的值

其他疑问可加以下交流群(加入一个即可啦~)

牛客多校算法训练营1:453799454

牛客全国算法训练营2:330766563

牛客多校算法训练营3:934889305

全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:13
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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