当前在线人数6688
首页 - 分类讨论区 - 电脑网络 - 数据科学版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
[版面:数据科学][首篇作者:sqrtn] , 2019年02月26日00:41:04 ,1211次阅读,1次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
sqrtn
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: sqrtn (不问不行啊), 信区: DataSciences
标  题: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个m (转载)
发信站: BBS 未名空间站 (Tue Feb 26 00:41:04 2019, 美东)

【 以下文字转载自 Military 讨论区 】
发信人: sqrtn (不问不行啊), 信区: Military
标  题: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个medium
发信站: BBS 未名空间站 (Tue Feb 26 00:24:03 2019, 美东)

睡前看到这道题,两三分钟就做出思路了,写完整证明也用不了10分钟。
我一说思路,买提将军多数都能做出来吧:
1)这是一个送分的大水题;
2)这是一个计算机算法题;
3)中国队教练该刷刷Leetcode了
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1700:f180:]


此主题相关图片如下:

[删除]

 
sqrtn
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: sqrtn (不问不行啊), 信区: DataSciences
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Feb 26 00:45:25 2019, 美东)

证明思路:
1. edge数小于v的图是tree,只有tree是没有cycle的,多出来的那epsilon*v条边就是
在树上加的圈;
2. 平衡的满树的高度是logv,只要v足够大,epsilon*v就大于logv,根据抽屉原则,加
到树上的这些圈就必有等高的,也就是等长的(不等长的圈最多logv平方个);
3. 当树不平衡不满时,反对结论的一方只会更吃亏,证毕。

借次机会给我老的刷题班打个广告!数据科学家也得刷题呀,我老也是数据科学家呢。
搜“刷题就得快糙猛”,投简历预审吧 ^_^




--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1700:f180:]

[分页:1 ]
[快速返回] [ 进入数据科学讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996