【爆】軟挑大神的賽后感言竟然是這樣的！

2020年華為軟件精英挑戰(zhàn)賽已圓滿收官

想知道大神獲獎(jiǎng)后是什么心情嗎？

想了解大神的腦回路嗎？

想知道巔峰代碼是如何寫的嗎?

本文帶你一一揭曉！

01大神的解題思路

“暴力出奇跡”分享

初賽和復(fù)賽：

主要的思路就是雙端搜索，先找其中一端并且存下來處理一下，相對(duì)于別的選手來說我們沒有做很底層的優(yōu)化，主要是迭代展開（把dfs變成for循環(huán)），以及預(yù)處理IO。

決賽：

總的來說算法應(yīng)該都是相似的，優(yōu)化的部分可以從兩方面來說。

首先是減少cache miss: 對(duì)于邊表，一些圖的度數(shù)比較小的時(shí)候可以用二維數(shù)組來存邊表，相對(duì)于前向星可以減少一次尋址。由于相對(duì)于原圖，確定起點(diǎn)之后最短路圖的邊的數(shù)量實(shí)際上少很多，所以可以臨時(shí)把最短路圖存下來。記錄前驅(qū)更方便維護(hù)，而且對(duì)于絕大部分點(diǎn)來說，前驅(qū)都只有一個(gè)，所以可以用一個(gè)數(shù)組記錄第一個(gè)前驅(qū)，如果多于一個(gè)前驅(qū)，可以用其它各種數(shù)據(jù)結(jié)構(gòu)，速度都是相似的，這樣可以很大程度減少cache miss。

另外一些還有一些思路上的優(yōu)化，比如說dijkstra的堆優(yōu)化，可以發(fā)現(xiàn)實(shí)際上的最短路都不是特別大，而且每次新加入堆中的元素一定大于已經(jīng)出堆的元素，所以可以用一個(gè)類似于筒排序的堆來維護(hù)。可以很大的提升效率。對(duì)于一些比較特殊的點(diǎn)，比如說出度恰好是1的點(diǎn)，這樣的點(diǎn)為起點(diǎn)形成的最短路徑一定會(huì)經(jīng)過他的唯一后繼，所以我們可以把他與其后繼合并，這樣可以減少很大一部分計(jì)算。如果以點(diǎn)u為起點(diǎn)已經(jīng)計(jì)算出了達(dá)到每個(gè)點(diǎn)的最短路長(zhǎng)度以及最短路圖，那么u的前驅(qū)v可以繼承u的結(jié)果，也就是說直接令所有最短路長(zhǎng)度加上w(v, u)，這樣的話，圖越稀疏，就會(huì)有越多的點(diǎn)的最短路不需要更新，可以減少一部分求最短路的時(shí)間，這需要先預(yù)處理scc以及簡(jiǎn)單的任務(wù)調(diào)度。

02 其他Q&A

比賽過程中最大的收獲是什么？

暴力出奇跡：

比賽過程中，在網(wǎng)上和其它的選手交流，他們或者自己遇到的問題，都引發(fā)了很多思考。在這些天反復(fù)思考如何去最大化利用服務(wù)器運(yùn)行的特點(diǎn)的過程中，重新認(rèn)識(shí)了很多自己以前自以為學(xué)會(huì)的知識(shí)，對(duì)于計(jì)算機(jī)組成，編譯原理的理解更前進(jìn)了一大步。實(shí)際上大家遇到難以解決的問題大多都是相似的，在交流的過程中也認(rèn)識(shí)了很多新朋友。

參加本次比賽做過什么準(zhǔn)備？

#507：

隊(duì)友三人都參與過ACM競(jìng)賽，在浙江省賽、CCPC和ICPC的賽場(chǎng)上斬獲過金牌。三人同一寢室，有良好的算法交流氛圍。參加比賽前，我們閱讀過往年題目，并且學(xué)習(xí)了一下優(yōu)秀的往屆比賽開源代碼。

掃黑除惡小分隊(duì)：

在2019年我們同樣參與了2019年華為軟件挑戰(zhàn)賽。因?yàn)檫@次賽題評(píng)分標(biāo)準(zhǔn)是以運(yùn)行速度為主導(dǎo)的，所以在參賽前我們學(xué)習(xí)了一下c++的內(nèi)容，通過在華為論壇文檔上查看了一些針對(duì)鯤鵬服務(wù)器的優(yōu)化實(shí)例。

守望&靜望&觀望：

其實(shí)也沒有做太多準(zhǔn)備，只是看了一下2019年的題目，然后想了一下它的解題思路，因?yàn)镮O部分是一定會(huì)有的，所以寫了一下IO部分的代碼。

小白一個(gè)，隊(duì)友組完隊(duì)，我們就直接參加熱身賽，這期間學(xué)習(xí)到了很多優(yōu)化思路和加速技術(shù)，也了解了比賽流程，之前沒有準(zhǔn)備過。

對(duì)大賽主辦方有什么想說的話么？

暴力出奇跡：

實(shí)際上對(duì)于一個(gè)相同的問題，大家都很樂于提出各種各種的想法，其中有很有價(jià)值的，也有不靠譜的，但都為我?guī)淼暮芏嗨伎肌ｋm然受到疫情的影響，復(fù)賽決賽最后都是線上的形式，不是往年的線下活動(dòng)，但我覺得相對(duì)于賽后進(jìn)行的一些活動(dòng)，類似的破冰活動(dòng)同樣也可以在賽前一周兩周來舉辦，這樣也有助于不同賽區(qū)天南海北的同學(xué)相互認(rèn)識(shí)。雖然是相互競(jìng)爭(zhēng)的比賽，但更多的也是一個(gè)挑戰(zhàn)自我的過程，我覺得有這樣一種氛圍的話，在相互交流中能引發(fā)自身更多的思考，這樣所有人有更多的提升。

有什么比賽經(jīng)驗(yàn)可以分享給大家的？

守望&靜望&觀望：

隊(duì)員一：考慮最壞的可能，做好充分的準(zhǔn)備。參加過今年軟挑復(fù)賽的同學(xué)應(yīng)該都知道，很多大佬都倒在復(fù)賽現(xiàn)場(chǎng)改需求那關(guān)，我在前一天連夜寫了改不同環(huán)數(shù)、改金額限制的版本，使我們隊(duì)順利出線（如果要我們現(xiàn)場(chǎng)改，也可能改不出來）。

隊(duì)員二：

（1）熱身賽還是有必要參加的，可以提前進(jìn)入狀態(tài)

（2）練習(xí)賽時(shí)候，要做好正賽賽題變化的準(zhǔn)備，否則現(xiàn)場(chǎng)極容易翻車

（3）多看看各賽區(qū)群交流一下，大佬們經(jīng)常開課很容易開闊思路

（4）戰(zhàn)線很長(zhǎng)，保重身體

隊(duì)員三：

（1）分工明確。誰負(fù)責(zé)算法，誰負(fù)責(zé)代碼的哪一部分，都要清楚。

（2）隊(duì)友之間多溝通。碰到問題的時(shí)候，隊(duì)員一起溝通想出解決辦法。

（3）不要輕言放棄。即使A榜成績(jī)?cè)俨睿膊灰艞墸瑘?jiān)持到最后一刻。

（4）學(xué)會(huì)團(tuán)結(jié)合作。多和比賽群里的大佬交流溝通，找優(yōu)化的技巧，多向他人學(xué)習(xí)。

掃黑除惡小分隊(duì)：

首先我們覺得最主要的經(jīng)驗(yàn)還是多嘗試，尤其是對(duì)于今年的賽題。即使很多嘗試都是負(fù)優(yōu)化，但是發(fā)現(xiàn)一些trick就可以有很大的提升。其次我們覺得加強(qiáng)交流是很重要的，交流探討不同的方案，并可以快速迭代方案。

03 大神代碼分享

暴力出奇跡：

https://github.com/suniyu/HuaweiChallenge2020

守望&靜望&觀望：

https://github.com/Gocrzy/CodeCraft2020

掃黑除惡小分隊(duì)：

https://github.com/yifannir/codecraft2020

#507：

https://github.com/SIeepZzz/Codecraft2020

04 大神風(fēng)采

- 暴力出奇跡

- 掃黑除惡小分隊(duì)

- 守望&靜望&觀望

- #507

2020年軟挑依然齊聚各路高手

在這里只采訪了冰山一角

更多分享歡迎在評(píng)論區(qū)留言~

今年軟挑就陪你到這里。

明年，我們?cè)僖娧剑海?/p>

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

本文轉(zhuǎn)自：“華為軟件精英挑戰(zhàn)賽”公眾號(hào)

計(jì)算

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。