西北工业大学"编程之星"C题

王国

https://ac.nowcoder.com/acm/contest/5403/C

题目分析

由于出题人造数据的时候忘记造一种特殊数据,所以导致 $n^2log(n)$ 可以水过.(也就是 $n^2$ 枚举边然后求距离) ,但是万幸的是ac的人中只有4个人是暴力 $n^2log(n)$ 的解法.

其中虚树和点分治占大多数

大约4,5个人使用了出题人的加法

点分治

此处省略1000字

虚树

此处省略1000字

出题人的解法

我们要在同一种颜色的点中,找到距离最远的两个点.

那么距离最远的两个点中,必然有一个点深度大的点. 所以我们找到这种颜色中深度最大的点,然后和其他求距离即可.(如果深度最大的点有多个,那么随便找一个就行)
正确性: 与两次dfs求树的直径本质上差不多

全部评论

推荐最新楼层

05-21 17:07

已编辑

门头沟学院 Java

拿到携程大住宿的秘诀，我决定发出来

作为去年通过校招进入携程大住宿BU的25届Java后端开发学长，今天把压箱底的面经和真实工作体验分享出来。全是干货，建议收藏。一、面试问题我当时技术面一共两轮，加一轮HR面。第一轮：基础面- 项目深挖。面试官会一直追问“为什么这么设计”“有没有更好的方案”。我简历上有个订单系统的项目，面试官专门问了表结构怎么设计、索引怎么建、接口QPS预估多少、怎么压测、如果QPS上去了响应时间被拉长怎么优化——这些都需要你有Java后端的基本盘，比如JVM调优、多线程并发处理能力。- 手撕代码。我抽到的是LRU缓存，写完让分析时间复杂度和空间复杂度，还问了有没有其他实现方式（比如LinkedHashMap）...

查看25道真题和解析

点赞评论收藏

05-19 17:02

门头沟学院销售工程师

误打误撞进卖起了大模型——文科HR转AI销售工程师真实记录堂堂公开！

说实话，我自己也没想到会走到这一步如果你翻我两年前的帖子，也会觉得我的简历很杂做过：HR、写过稿、运营过新媒体，策划过各种活动，面试官看我简历大概会想：这人到底想干啥？我自己也不太知道，反正就是什么都投，广撒网，先上岸再说。（我也真的准备过四个方向的简历）25年10月底我签了一家某行业的头部公司做大客户销售，拿到offer后公司推出了第一款大模型产品，也是全行业内第一个涉足大模型的公司。我当时的心情很微妙，有点懵，但也兴奋；因为我其实很早就在自己瞎摸索GPT，Claude，AI相关的东西了，只是没想到这玩意儿这么快就落到我工位上了。运气？是的。但我自己也没完全闲着，就这样，50%的努力加上50...

如何成为1个AI工程师？

点赞评论收藏

03-26 13:04

已编辑

电子科技大学算法工程师

27找实习这简历有问题吗？要怎么改啊？腾讯京东大厂不给面呜呜

腾讯 京东oppovivo快手美团百度字节蚂蚁上面的厂都投了，有的直接简历挂了（快手  阿里挂的最严重），测评做了，有的给了笔试，但为啥大多都一直卡流程？卡在“简历筛选/评估中”，这是怎么回事？项目不行？还能找到实习吗？

xiaowl：你这个简历“条目上”都比较有深度性，但是实际上面试官又没法很好的评估你是怎么达到很多看上去很厉害的结果的。要避免一些看上去很厉害的包装，比如高效的内存复用策略的表达，如果仅是简单的一些内存共享机制，而且面试上也没有深挖的空间，就不要这样表达。比如，工程化模式本质上可能就是定义了一些abstract class，那也就没特别多值得讲的内容。建议简历上应该侧重那些你花了大量时间和精力解决、研究的问题，不要过分追求“丰富”，而是关注在技术深入度、问题解决能力的表现上。

没有实习经历，还有机会进...

点赞评论收藏