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

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

想了解大神的脑回路吗？

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

本文带你一一揭晓！

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 大神风采

- 暴力出奇迹

- 扫黑除恶小分队

- 守望&静望&观望

- #507

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

在这里只采访了冰山一角

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

今年软挑就陪你到这里。

明年，我们再见呀：）

-------------------

本文转自：“华为软件精英挑战赛”公众号