计蒜之道2018初赛做题记录

最近又开始了计蒜之道,目前进行到了前两场,两场都打了:第一场是自己打,第二场帮考试中的队友打的。第一场题目不算太坑一个小时做完前三个不想写hard就可以晋级了。。。第二场题目有些坑点实在难以注意到结果半个小时写完前两个easy就晋级了。。。写了一整场的medium。。。想到博客已经n年没有更新了,最近考试周也过去了,就把题目补补(如果会的话),写到这里算了,毕竟月底蓝桥杯还是要咸鱼冲锋一下的。。剩下的几场因为没有号了,可能就随便打打了。。。

第一场

A. 百度无人车

二分答案没啥好说的。。

B. 百度科学家(简单)

这道题我比赛的时候写了两个版本简单和中等,困难当时也看出来要写可持久化线段树优化建图,但是老年人写不动就算了。
简单版本直接枚举的起点然后bfs的。。。不贴代码了。

C. 百度科学家(中等)

发现加的总边数不会超过1e5就很好办了。先Tarjan缩点成dag后重新建图,然后因为权值非负贪心选择出度为0的点中价值最小的即可。

D. 百度科学家(困难)

待补。

第二场

A. 淘宝的推荐系统

直接dp[i]表示到当前元素为止价值为i的合法序列长度,然后就是O(nd)的dp了。。。

B. 阿里巴巴的手机代理商(简单)

没有update不贴代码了。。

C. 阿里巴巴的手机代理商(中等)

这个题细节贼鸡儿多。。。就说一个地方吧,因为我是错在这里了,就是你update需要先删除然后断掉子树,然后插入在连接。具体看代码吧,至于为什么,考虑你把一个老的单词换成一个新的单词且老的是新的前缀的情况,所以这个顺序不能乱。

D. 阿里巴巴的手机代理商(困难)

待补。。写不动了啊。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注