最近给我的小学信息学奥赛学员讲解Codeforces上的算法编程竞赛题目 。这是一个知名的俄罗斯算法竞赛网站,俄罗斯人算法很厉害,华为就有很多俄罗斯科学家 。所以我们很有必要学习俄罗斯人算法编程 。
我讲解的题目是DSU2,一个并查集算法,大意是通过Union u,v 操作合并两个集合,然后通过get v操作找出v元素所在集合中的最大与最小元素及其集合元素总个数 。
算法题目其实不算难,我要说的是,这个网站非常棒,题目质量非常高!为什么这样说?我们就以DSU2这道题为例进行说明 。
首先,它的逻辑严密性要求非常高,它提供的输入样例的测试覆盖率较低,如果选手编写的程序在本地运行通过就以为万事大吉那就大错特错了!你提交后很可能出现类似AC:38%这样的信息,意思是你的算法逻辑不严谨,还有62%测试用例没有覆盖到 。这也是我们国内大部分码农的通病,只保证主体功能实现,很多细节根本就没有考虑到,所以测试部门工作非常大 。我大学毕业刚做开发的时候也犯过类似的错 。
因此,你自己不仅得是个开发高手,还得是个测试高手,要保证测试用例覆盖率达到100%,否则提交后绝对通过不了 。
其次,它的性能要求很高,它需要的是最优算法 。这很锻炼开发人员的编程能力 。互联网公司大部分人的代码性能很差 。
而且,就这道题而言,尽管你在算法层面已经使用非常好的优化措施,如在查找节点祖先的find(int x)函数中使用了路径压缩优化算法 。本地运行正常信心满满,结果提交上去很容易出现超时 。这个时候你就得注意编程细节了,比如scanf输入函数不能和cin混合使用,数组越界,代码去重等等,综合能力要求很高 。
最后,英语能力非常重要,否则连题目都看不懂,更不能及时了解前沿新技术 。我也看到过国内有些信息学辅导机构翻译过来的题目往往漏洞百出,难免有误人子弟之嫌 。
因此,经常参加这种大赛的信奥获奖选手绝对都是算法高手,其能力大于大厂程序员也就不足为奇了 。
【为什么说信奥选手可以碾压大厂程序员】
文章插图
文章插图
文章插图
- 为什么健身要补充肌酸 为什么说用了肌酸就不是自然健身了
- 洛阳算命高人(图文)
- 属猪的几月犯月
- 九寨沟的水与风清扬的独孤九剑
- 揭秘KPL职业选手为什么出两只鞋
- 败也萧何"名句中讲的是谁 成也萧何败也萧何说的是谁
- 为什么说元宵节是中国情人节 元宵节又称什么节
- 却没有选择华为 为什么买不到华为
- 苹果手机虽然很好 苹果手机为什么好
- 酿葡萄酒为什么需要橡木桶 酿葡萄酒为什么要用橡木桶