当前在线人数5513
首页 - 分类讨论区 - 学术学科 - 数学版 - 同主题阅读文章

此篇文章共收到打赏
0

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

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

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

发信人: 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 (不问不行啊), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Feb 26 00:52:05 2019, 美东)

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

借机给我老的刷题班打个广告!刷题转码的童鞋们,去待字闺中搜“刷题就得快糙猛”
,投简历预审吧 ^_^
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1700:f180:]

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

发信人: NotJY (金灿荣--美国的战略家最恨中国的带路党), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Mon Mar  4 19:04:00 2019, 美东)

中国这几次奥数差是不是也和教练领队的翻译不行有关?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 173.]

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

发信人: NotJY (金灿荣--美国的战略家最恨中国的带路党), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Mon Mar  4 19:04:55 2019, 美东)

中国教育部的领导都是些大脑装满屎、嘴巴鳃鳗鲷的肉便器。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 173.]

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

发信人: killbill8 (Kill Bill), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Mar  5 08:31:12 2019, 美东)

谁把这道题准确翻译一下?这道题的英语描述,每个单词都认识,可是这个句子的意思
却非常令人费解。中学的国际奥林匹克,解题可能需要高智力,但是读懂题目,却是完
全不需要高深的水平的。换句话说,把题目报出来,一个普通的中学生就应该能懂得的
。大家不要妄自菲薄。这道题,我觉得可能就是英语的理解中国队吃了亏。英语描述数
学,相对而言,比汉语拙劣。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 195.]

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

发信人: killbill8 (Kill Bill), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Mar  5 08:48:39 2019, 美东)

比如说,any graph on v vertices是什么意思?graph是指那种有坐标点的图吗(例如
一个开口向上的抛物线)?还是指一个几何图形(例如多边形)?on vertices里面的
on具体指哪一条意思?是指多边形的顶点就是指定的点吗(所以才说on)?还是指带坐
标的图像的某一维坐标(例如说y=×**2是关于x和y的抛物线,这里也可以说on x and
y)。题目到底应该怎么理解?后面的一截短语也让人费解。我前几天读了好几遍题目
,都不懂意思。
有人可能要问,那对母语是英语的人来说也费解吗?是的,只是情况可能会好一些,因
为他们会尽快找到一个可以说得通的理解。英语的名词,在特定学科里面通常总是指特
定的意思。graph,shape,profile这几个词,非英语出生的人会迷惑,哪怕是查权威
英语字典,你可能还是不明白核心的区别在哪里。而英语里的介词呢,更是随意滥用,
同一个介词on,有几十种解释。相当于是语言不发达,做不到精细区别,所以只好来来
回借着用。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 195.]

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

发信人: killbill8 (Kill Bill), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Mar  5 08:57:24 2019, 美东)

正是为了消除语义理解上的差异,我记得以前的国际数学奥林匹克竞赛,同一道题目,
会有多种语言描述,临场让参赛队伍选择试卷。不同语言版本的描述,事先经过核准无
误的。不知道现在的奥赛还是不是这样。但是这个罗马尼亚大师赛显然不是。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 195.]

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

发信人: killbill8 (Kill Bill), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Mar  5 09:09:38 2019, 美东)

any graph on ... vertices with ...  edges, 有顶点(vertices),也有边(edges
),那graph是指多边形吗,那为啥不用polygon这个词而用graph?而且,边的数目是
整数,可是(1+epsilon) * v 是实数哦。是要取最接近这个实数的整数吗?那应该用
【】这样的数学运算符号啊。后面还有,two ... cycles of equal lengths,这里面
length是指循环(cycle)的周期吗?那为啥不用period这个词,或者period length这
样无歧义的词组?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 195.]

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

发信人: bottlecapper (bottle), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只是个
发信站: BBS 未名空间站 (Tue Mar  5 09:40:57 2019, 美东)

graph, cycle, vertices, edges 都是图论里面的专有词汇,大家都那么用的。看过图
论就不会不知道,改成polygon period专业人士会看不懂的
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 91.]

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

发信人: killbill8 (Kill Bill), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只
发信站: BBS 未名空间站 (Tue Mar  5 10:57:57 2019, 美东)


【 在 bottlecapper (bottle) 的大作中提到: 】
: graph, cycle, vertices, edges 都是图论里面的专有词汇,大家都那么用的。看过图
: 论就不会不知道,改成polygon period专业人士会看不懂的


图论?

哦,那我差不多明白这些词了。graph是把若干顶点用边连起来的图形。length是指边
的条数,cycle是指回路,或者闭环。

虽然现在还是没有完全明白题目的意思,但是可以再琢磨一下。

嗯,那个(1+ε)*v应该括起来取整,这个还是要抱怨一下。

非常感谢你的回复。
--
※ 修改:·killbill8 於 Mar  5 11:31:49 2019 修改本文·[FROM: 195.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 195.]

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

发信人: easior (囫囵), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只
发信站:
BBS 未名空间站 (Wed Mar  6 06:23:56 2019, 美东)

没看过具体的题目,
不过对所谈的语言问题深有同感,
英语单词的词性太没人性了,
搞不好,能找到一个具有所有词性的英语单词!
【 在 killbill8 (Kill Bill) 的大作中提到: 】
: 比如说,any graph on v vertices是什么意思?graph是指那种有坐标点的图吗(例如
: 一个开口向上的抛物线)?还是指一个几何图形(例如多边形)?on vertices里面的
: on具体指哪一条意思?是指多边形的顶点就是指定的点吗(所以才说on)?还是指带坐
: 标的图像的某一维坐标(例如说y=×**2是关于x和y的抛物线,这里也可以说on x
and
: y)。题目到底应该怎么理解?后面的一截短语也让人费解。我前几天读了好几遍题目
: ,都不懂意思。
: 有人可能要问,那对母语是英语的人来说也费解吗?是的,只是情况可能会好一些,因
: 为他们会尽快找到一个可以说得通的理解。英语的名词,在特定学科里面通常总是指特
: 定的意思。graph,shape,profile这几个词,非英语出生的人会迷惑,哪怕是查权威
: 英语字典,你可能还是不明白核心的区别在哪里。而英语里的介词呢,更是随意滥用,
: ...................


--

※ 修改:·easior 于 Mar  6 09:50:24 2019 修改本文·[FROM: 129.]
※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 129.]

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

发信人: voidcinder (ashesoftime), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只
发信站: BBS 未名空间站 (Wed Mar  6 19:24:37 2019, 美东)

edge数小于v的图是tree?
说了是连通图了?

【 在 sqrtn (不问不行啊) 的大作中提到: 】
: 证明思路:
: 1. edge数小于v的图是tree,只有tree是没有cycle的,多出来的那epsilon*v条边就是
: 在树上加的圈;
: 2. 平衡的满树的高度是logv,只要v足够大,epsilon*v就大于logv,根据抽屉原则
,加
: 到树上的这些圈就必有等高的,也就是等长的(不等长的圈最多logv平方个);
: 3. 当树不平衡不满时,反对结论的一方只会更吃亏,证毕。
: 借机给我老的刷题班打个广告!刷题转码的童鞋们,去待字闺中搜“刷题就得快糙猛”
: ,投简历预审吧 ^_^



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2d1:20]

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

发信人: TheMatrix (TheMatrix), 信区: Mathematics
标  题: Re: 罗马尼亚大师赛中国队被团灭的第三题, 改改放到Leetcode只
发信站: BBS 未名空间站 (Thu Mar  7 18:26:23 2019, 美东)

没说。但是可以是森林。

【 在 voidcinder (ashesoftime) 的大作中提到: 】
: edge数小于v的图是tree?
: 说了是连通图了?
: ,加




--
☆ 发自 iPhone 买买提 1.24.09
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2607:fb90:9828:]

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

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

友情链接


 

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

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