2021-08-03 12:33 已编辑北京师范大学 C++

关注

2021牛客暑期多校训练营5 J. Jewels(KM模板)

Jewels

https://ac.nowcoder.com/acm/contest/11256/J

Description

打捞 $n$ 个货物，货物会动，每一个时刻只能打捞一个，货物会动，打捞的代价是三维空间上的距离平方。

Solution

$n$ 个货物只需要 $[0, n - 1]$ 时刻就能全部打捞，对于每个货物在每一个时刻都有相应的代价，可以构建二分图，左边是时刻，右边是货物，做带权二分图的最优匹配（KM算法）即可。

听说网上假的 KM 板子假的满天飞，于是偷了 roundgod giagia 的板子封装一下，以后我也有KM板子啦！
时间复杂度 $O(n^3)$

Code

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

一些比赛的题解文章被收录于专栏

一些比赛的题解

全部评论

推荐最新楼层

12-25 15:48

上海得物信息集团有限公司_java开发工程师(准入职员工)

得物内推，得物内推码

得物测开一面面经，摘自优秀牛油面试时间：24/10/19面试时长：30 min1. 自我介绍； 2. 为什么找测试岗位； 3. 讲一下测试的一般流程； 4. 设计测试用例的常用方法； 5. 如果需要测试一个接口，去测试一个并发场景，应该如何去做； 6. 如何去设置多线程； 7. 10万级别的接口访问量，如何去模拟； 对零经验很友好！1.💰待遇 薪资是一天150，包晚饭，有双休，基本不加班，有茶水间小零食无限吃🍪，健身房、员工折扣店，晚上10点后打车免费，过节活动礼包🎁2.👗工作 服装运营岗，主要技能需要会用Excel、vlookup 工作内容有点像对接商家的客服👩🏻‍💻并且帮助你...

点赞评论收藏

12-24 17:38

睿联技术_结构工程师(准入职员工)

正浩创新内推，正浩创新内推码

26届女硬件工程师丨正浩创新面经及流程9.1一面1.自我介绍2.有无相关电源设计项目或经历，并浅谈3.DCDC拓扑手撕（但是我当时没带纸笔所以口头描述），BUCK和BOOST，同步异步的区别和优缺点，同步电路的控制方式（施加什么PWM波形，如何控制MOS通断）4.项目中最有挑战性的部分，怎么解决的，然后会深挖这一部分再提问（这个问题出现的根本原因，下次如何避免）5.面试官说我专业其实不是很对口，不是电气工程专业，所以问的比较浅，大家仅供参考9.2收到笔试链接，非笔试，为性格测试9.5收到二面短信9.8 二面，没有技术问题，主要问了在校做过什么项目，调试遇到什么问题，除此之外有没有做过电源相关项...

点赞评论收藏

不愿透露姓名的神秘牛友

10-29 21:14

字节意向审批。。

如图，已经审批好几天了，机会大吗

疯犬丨哈士奇：喜欢你的人会主动表白，对你有想法的人会很主动，所以要你的公司不会吊着你

所以懂了吧

点赞评论收藏

12-12 01:48

中国地质大学（武汉） Java

简历求拷打！

27届，投了半个月简历了，只有一些小厂的面试，中大厂根本拿不到面试机会，求各位佬给点建议！另外现在是搞一段寒假小厂实习呢，还是直接备战暑期？好焦虑😣

程序员花海：实习和校招简历正确格式应该是教育背景+实习+项目经历+个人评价其中项目经历注意要体现业务实习经历里面的业务更是要自圆其说简历模板尽可能保持干净整洁不要太花哨的

点赞评论收藏

12-22 13:53

美团_测试开发

考研结束如何准备实习/春招

前言：随着考研刚刚结束，如果感觉考研成绩不符合自己的心理预期的话可以趁着这两三个月准备来年的春招，最好不要等成绩出来或者调剂结束，那个时候春招已经开始或者结束，想要找工作就得和社会上的所有人一起去竞争社招岗位了。调整心态与自身定位调整心态：如果感觉考研的这几个月过的非常压抑的话可以先给自己放几天假，休息一下，一定要调整好自己的心态和状态才能全身心的投入到找工作这条路。自身定位：一直考研的同学可能不知道找工作这个市场到底如何，工作难不难找，究竟能找到什么样子的工作，待遇如何等等。先简单说个结论，找个工作的难度并不高，但是想要找个好的工作确实很有难度。首先要明确自己的学校以及水平如何，自己能找什么...

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 离家近房租贵VS离家远但房租低，怎么选 #

# 各大公司公布25年Q3财报，你怎么看？ #