建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
请选择 进入手机版 | 继续访问电脑版-->
设置昵称

在此一键设置昵称,即可参与社区互动!

确定
我再想想
标签
您还可以添加5个标签
  • 没有搜索到和“关键字”相关的标签
  • 云产品
  • 解决方案
  • 技术领域
  • 通用技术
  • 平台功能
取消

小云对小云

角色:成员

话题:0

发消息
发表于2020年06月10日 14:54:54 27562
直达本楼层的链接
楼主
显示全部楼层
[精彩回顾] 软挑大神的赛后感言竟然是这样的!

2020年华为软件精英挑战赛已圆满收官


想知道大神获奖后是什么心情吗?

想了解大神的脑回路吗?

想知道巅峰代码是如何写的吗? 

本文带你一一揭晓!

image.png

01大神的解题思路



‘暴力出奇迹’队分享

初赛和复赛:

主要的思路就是双端搜索,先找其中一端并且存下来处理一下,相对于别的选手来说我们没有做很底层的优化,主要是迭代展开(把dfs变成for循环),以及预处理IO。

决赛:

总的来说算法应该都是相似的,优化的部分可以从两方面来说。

首先是减少cache miss: 对于边表,一些图的度数比较小的时候可以用二维数组来存边表,相对于前向星可以减少一次寻址。由于相对于原图,确定起点之后最短路图的边的数量实际上少很多,所以可以临时把最短路图存下来。记录前驱更方便维护,而且对于绝大部分点来说,前驱都只有一个,所以可以用一个数组记录第一个前驱,如果多于一个前驱,可以用其它各种数据结构,速度都是相似的,这样可以很大程度减少cache miss。

另外一些还有一些思路上的优化,比如说dijkstra的堆优化,可以发现实际上的最短路都不是特别大,而且每次新加入堆中的元素一定大于已经出堆的元素,所以可以用一个类似于筒排序的堆来维护。可以很大的提升效率。对于一些比较特殊的点,比如说出度恰好是1的点,这样的点为起点形成的最短路径一定会经过他的唯一后继,所以我们可以把他与其后继合并,这样可以减少很大一部分计算。如果以点u为起点已经计算出了达到每个点的最短路长度以及最短路图,那么u的前驱v可以继承u的结果,也就是说直接令所有最短路长度加上w(v, u),这样的话,图越稀疏,就会有越多的点的最短路不需要更新,可以减少一部分求最短路的时间,这需要先预处理scc以及简单的任务调度。



02 其他Q&A



比赛过程中最大的收获是什么?


暴力出奇迹:


比赛过程中,在网上和其它的选手交流,他们或者自己遇到的问题,都引发了很多思考。在这些天反复思考如何去最大化利用服务器运行的特点的过程中,重新认识了很多自己以前自以为学会的知识,对于计算机组成,编译原理的理解更前进了一大步。实际上大家遇到难以解决的问题大多都是相似的,在交流的过程中也认识了很多新朋友。


参加本次比赛做过什么准备?

#507:

队友三人都参与过ACM竞赛,在浙江省赛、CCPC和ICPC的赛场上斩获过金牌。三人同一寝室,有良好的算法交流氛围。参加比赛前,我们阅读过往年题目,并且学习了一下优秀的往届比赛开源代码。

扫黑除恶小分队:

在2019年我们同样参与了2019年华为软件挑战赛。因为这次赛题评分标准是以运行速度为主导的,所以在参赛前我们学习了一下c++的内容,通过在华为论坛文档上查看了一些针对鲲鹏服务器的优化实例。

守望&静望&观望:

其实也没有做太多准备,只是看了一下2019年的题目,然后想了一下它的解题思路,因为IO部分是一定会有的,所以写了一下IO部分的代码。

小白一个,队友组完队,我们就直接参加热身赛,这期间学习到了很多优化思路和加速技术,也了解了比赛流程,之前没有准备过。


对大赛主办方有什么想说的话么?


暴力出奇迹:

实际上对于一个相同的问题,大家都很乐于提出各种各种的想法,其中有很有价值的,也有不靠谱的,但都为我带来的很多思考。虽然受到疫情的影响,复赛决赛最后都是线上的形式,不是往年的线下活动,但我觉得相对于赛后进行的一些活动,类似的破冰活动同样也可以在赛前一周两周来举办,这样也有助于不同赛区天南海北的同学相互认识。虽然是相互竞争的比赛,但更多的也是一个挑战自我的过程,我觉得有这样一种氛围的话,在相互交流中能引发自身更多的思考,这样所有人有更多的提升。


有什么比赛经验可以分享给大家的?


守望&静望&观望:

队员一:考虑最坏的可能,做好充分的准备。参加过今年软挑复赛的同学应该都知道,很多大佬都倒在复赛现场改需求那关,我在前一天连夜写了改不同环数、改金额限制的版本,使我们队顺利出线(如果要我们现场改,也可能改不出来)。

队员二:

(1)热身赛还是有必要参加的,可以提前进入状态

(2)练习赛时候,要做好正赛赛题变化的准备,否则现场极容易翻车

(3)多看看各赛区**流一下,大佬们经常开课很容易开阔思路

(4)战线很长,保重身体

队员三:

(1)分工明确。谁负责算法,谁负责代码的哪一部分,都要清楚。

(2)队友之间多沟通。碰到问题的时候,队员一起沟通想出解决办法。

(3)不要轻言放弃。即使A榜成绩再差,也不要放弃,坚持到最后一刻。

(4)学会团结合作。多和比赛群里的大佬交流沟通,找优化的技巧,多向他人学习。

扫黑除恶小分队:

首先我们觉得最主要的经验还是多尝试,尤其是对于今年的赛题。即使很多尝试都是负优化,但是发现一些trick就可以有很大的提升。其次我们觉得加强交流是很重要的,交流探讨不同的方案,并可以快速迭代方案。



03 大神代码分享


暴力出奇迹:

https://github.com/suniyu/HuaweiChallenge2020

守望&静望&观望:

https://github.com/Gocrzy/CodeCraft2020

扫黑除恶小分队:

https://github.com/yifannir/codecraft2020

#507:

https://github.com/SIeepZzz/Codecraft2020



04 大神风采

image.png

- 暴力出奇迹

image.png

- 扫黑除恶小分队

image.png

- 守望&静望&观望

image.png

- #507


2020年软挑依然齐聚各路高手

在这里只采访了冰山一角

更多分享欢迎在评论区留言~


今年软挑就陪你到这里。

明年,我们再见呀:)


本文首发软挑官方微信号:https://mp.weixin.qq.com/s/Gai740g6H9CjBcuT-z9LYA

举报
分享

分享文章到朋友圈

分享文章到微博

Campus Hero

角色:成员

话题:3

发消息
发表于2020年06月17日 15:10:19
直达本楼层的链接
沙发
显示全部楼层

点赞 评论 引用 举报

丰台小霸王

角色:成员

话题:0

发消息
发表于2020年08月13日 16:30:51
直达本楼层的链接
板凳
显示全部楼层
点赞 评论 引用 举报

游客

富文本
Markdown
您需要登录后才可以回帖 登录 | 立即注册