錢易IOI2021參賽總結IOI2021參賽總結2021-07-13 13:14:36閱讀量:22325

 
 

非常榮幸能夠代表中國參加 2021 年第 33 屆國際信息學奧林匹克競賽(IOI2021)。受新冠疫情的持續影響,由新加坡主辦的第三十三屆國際信息學奧林匹克競賽(IOI 2021)于 6 19 - 28 日在世界各地以線上比賽形式同步舉行,共有來自 88 個國家(地區)的 355 名選手參賽。IOI2021 中國隊參賽活動在北京舉行。

我們四位同學在前往北京參賽前,已經在鎮海中學訓練了十來場比賽,我在訓練中也調整好了狀態。

參加練習賽時,我略微適應了一下 CMS 系統,發現其測評并不會顯示每個點的運行時間和程序使用的內存,每個測試包中測到第一個未通過的點就結束當前測試包的評測。這與我預想的不太一樣,但也不構成問題。

練習賽后便是開幕式,開幕式前我了解到參賽的不僅有我們四位同學,還有一位荷蘭隊的選手因為疫情的影響,也和我們一起參賽。

第一天比賽前,我還是略微有點緊張,而且還要提前半個小時到場,到場后坐在位置上也十分無聊。比賽開始后,我先閱讀了一遍題目,感覺 T2, T3 可能較難,T1 是數據結構,或許相對來說會簡單一點。于是我便著手于 T1,但在兩個多小時后,我仍未解決這題。因為我之前一直認為這題比較重要必須通過(事實上最后這題通過人數也是最多的),白白浪費了很多時間。此后我絕對先嘗試解決 T2、T3。我簡單的思考了T2之后,決定使用迭代縮點的方法嘗試一下。我自己想了一下沒能想到可以卡掉這種做法的數據。實現后我發現這一做法通過了絕大多數的點,而且未能通過的點是因為數組開小了,修改后重新提交便成功地通過了此題。

但此時我的分數仍然較低,因此我先迅速寫了 T1 的一個部分分。然后我思考了一下 T3,認為這題非常困難,需要花較長時間去構造。此時我想到了一個基于 2-sat 的亂搞做法。于是我就把 T2 的縮點拉了過來迅速實現了一下,略微調參得到了T3 70 分的成績,在調參提交評測過程中,我抽時間寫了 T1 另外一些部分分,最后在 距離比賽結束還有 8 分鐘時提交上去并得到了分數。

比賽結束后我依然心有余悸,開局的不利讓我心態幾乎崩裂,幸好關鍵的 T2 亂搞做法讓我有了一線生機。在看到排行榜上我依然排在并列第 7 的位置后,我松了一口氣。在晚上睡覺前我又重新思考了一下 T1,突然發現我考場上 30 分鐘左右的時候就得到的一個做法能夠很好解決這個問題。但當時我認為這和原問題等價,可事實上這非常簡單就能完成,因此我感到了非常地懊悔。

第二天比賽前有兩天的休息時間,我也利用這段時間調整好了心態。在得到題目后,我讀了一遍題,T1 是一道簽到題,T2 應該是一道不是很難的題目,T3 好像是利用壓位優化的一道造計算機題。

首先,我迅速地解決了 T1之后來研究 T2。略微觀察后,我便發現了題目的關鍵點:打敗一個怪獸加的是怪獸的能力值,于是按 2^k 分組一下然后倍增就可以得到一個 log^2 的做法。但是觀察最后一個包,n=400000,q=50000,我發現把 2^k 改成 16^k 就可以了。于是我迅速寫了一下代碼,但是沒能通過。我肉眼查了一下錯沒能查出來。于是我寫了一個對拍,在這一過程中浪費了一定的時間,但最后還是順利的在 1 個小時 40 分鐘的時候通過了這題。

最后剩下一道造計算機的 T3,他讓我完成兩種任務,一種是取 n 個數的最小值,另一種是給 n 給數排序。我先利用取反和加法兩種運算迅速設計了一個快速比較的方式,并且可以改造到并行之中。于是我每次將一個序列折半,把第一個評測包解決了。

對于第二個評測包,我首先想到了之前了解到的雙調排序,但我對其不是很了解,因此我轉而嘗試其他做法。在思考一段時間后,我得出了一個改造冒泡排序使之能并行的方法,實現了之后優化了一下常數便通過了此題。

第二天出來后,我和四名同學去吃夜宵。當得知我們四個包攬前四的時候,我感到十分不可思議,也十分開心。

最后,感謝 CCF 給我參加這次 IOI 的機會,感謝韓文弢領隊,感謝符老師、應老師對我的悉心照料與指導,感謝和我一起交流成長的同學!


18禁人看免费无遮挡网站_亚洲欧美偷拍综合图区_推油少妇久久99久久99久久_最近中文字幕在线中文视频