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

王国

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

题目分析

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

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

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

点分治

此处省略1000字

虚树

此处省略1000字

出题人的解法

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

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

全部评论

推荐最新楼层

03-26 12:05

长沙理工大学高等教育

国企‘三进三不进’”，不是所有的央国企都值得进

很多友友不知道怎么校招选国企，朝着这三个目标前进三类值得进入的央国企• 第一类：垄断型国企或政策性银行举例：中国烟草、国家电网、三桶油、三大政策性银行，铁路等。优势：应届生进入后，待遇和未来发展前景较好，不会失业类似公务员。• 第二类：受国家保障的央国企（如军工类企业，中储量，邮政）特点：工作稳定、福利待遇一般，且“不可能失业”。• 第三类：省属市属总部国企机关适合人群：家庭条件较好、追求稳定工作的求职者。优势：工作内容管理为主、待遇尚可，无业绩压力、离家近，“工作生活两不误”。#春招至今，你的战绩如何？##工作经验# 

职场吐槽大会

点赞评论收藏

03-25 16:19

武汉大学 Java

京东jdy 平台产品与研发中心一面

八股java反射的原理哪些框架用到了反射java中除了synchronized还了解哪些锁线程池的参数，实际使用的时候参数怎么设置的concurrenthashmap原理什么是覆盖索引mysql慢查询排查及原因实习拷打（巴拉巴拉）另一个面试官：最近遇到的最大困难实习期间的收获设计一个查找方圆3公里的骑手并通知接单抢单

查看10道真题和解析

点赞评论收藏

03-05 13:31

郑州轻工业大学 Java

27届整改简历：

大佬帮我看看吧：我大二下学期有一段暑假实习，中小厂应该算，但是也没有参与核心业务，但是在有人带的情况下，写了个小项目（未完善），打算把它作为实习项目，但是简历上实习这个不太会写……我也知道star法则，但是如何包装……现在我的简历像是罗列技术栈……然后我的项目经历也是很标准的黑马点评，我要不要再做一个新的项目加到这个项目经理里面？？还有什么可以优化的都可以指出，我虚心接受并整改，多谢大佬们了！

书海为家：实习是成为大厂正式员工很好的敲门砖，看您的简历中有一段实习经历，挺好的。我来给一点点小建议，因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验，面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路，所以最好在简历中描述下自己实习时做过项目的完整过程，比如需求怎么来的，你对需求的解读，你想到的解决办法，遇到困难如何找人求助，最终项目做成了什么程度，你从中收获了哪些技能，你有什么感悟。

点赞评论收藏