虞皓翔IOI2021參賽總結IOI2021參賽總結2021-07-13 13:14:36閱讀量:27275

 
 

很榮幸能代表中國參加由新加坡主辦的線上第 33 屆國際信息學奧林匹克競賽。由于新加坡的疫情仍較為嚴重,因此本次比賽仍然采用線上的形式。今年中國隊比賽的場地設在北京中關村皇冠假日酒店的一個會議室,平時就住在酒店的樓上。不得不說 CCF 還是非常用心的,在各方面都做了充分的準備,以讓我們專心投入到比賽中。

為了照顧來自世界各地的選手,本次比賽的時間為 18:00 ~ 23:00,對中國選手略有一些影響。因此在一個月前的集訓時我們已經開始調整時差,以使我們在考試的時間獲得最好的狀態。此外,今年除了中國隊的四位選手外,還有一名來自荷蘭的選手來中國的賽場上參加比賽。我們和領隊老師們對其表示歡迎,并進行了深入的交流。

第一天,我首先讀了所有的題目,發現第一題 candies 是比較傳統的數據結構,第二題 keys 是關于圖論的綜合題,第三題 parks 則是一道圖論的構造。

瀏覽完畢后,對 candies一題,我并沒有很好的思路,于是轉而先做 parks。經過觀察,我發現題目需要你找一張網格圖子圖的生成樹,使得其對偶圖是基環森林。在一個小時左右,我想出了基于對角線構造的方法,寫完后交上去發現只有 70 分。然后我利用 assert 的方法,找出程序運行失敗的位置,在對應位置構造例子并修改,經過若干次修改后最終在 2 個小時左右通過了 parks 一題。

然后回到 candies,我馬上得到了前 4 個子任務的做法,不過直觀感覺我覺得這道題的定位應該會比 parks 更簡單,于是我繼續思考正解。然而我思考了好一會也沒想出用線段樹等 poly log 復雜度的做法,于是我轉而考慮根號做法。我將第 4 個子任務的做法改編成了一個 O(n√(nlog(n) )) 的做法,然而因為常數過大只通過了第 1 個子任務。經過細致地分析,我發現可以通過單調性和均攤分析可以得到 O(n√n) 復雜度的做法,于是便通過了這道題。此時距離比賽結束還有 1 個小時。(事實上這道題的正解是在線段樹上二分后綴 max - min,確實是一個比較妙的構造)

此時開始做 keys,首先我迅速過掉了前 3 個包,獲得了 37 分。接著嘗試考慮標算,但我未能繼續獲得些許進展。賽后我發現這道題只需要像類似 Bor?vka 算法一樣暴力啟發式合并 O(log n) 輪就可以得解了。

比賽結束后,發現鄧明揚和代晨昕分別獲得了 300 270 的分數,位居榜首;而我和 錢易只有 237 分,不過最終仍然還有并列第 7 名的成績。第二天比賽前,領隊韓文弢老師再次強調了題目按照字典序編排順序,與難度無關,需要選擇合適的策略。

第二天包含兩道傳統題和一道造計算機題。經過 10 分鐘的閱讀,我發現第一題是一道簡單的貪心題,于是馬上通過了此題。

面對數據結構題 dungeons 和造計算題題 registers,我打算先做 registers。題目要求用二進制大整數的位運算和加法來實現取最小值和排序的操作。由于數的個數比較多而數位不多,因此我使用逐位確定的方法完成了取最小值。而對于 n = 2 的部分,可以利用熟知的等式 min(a, b) = (a + b - |a - b|) / 2 來在常數時間內完成。

而對于后面的排序部分,我首先想到的是 O(n log2n) 次比較的排序,發現只能通過 n = 10 的部分。于是嘗試對其進行優化,可惜最終沒能通過 n = 100 的部分。賽后得知正解是通過大整數位數多的性質來進行并行,這樣就只依賴與排序網絡的深度而不是比較器個數。于是一些如奇偶排序等的 O(n2) 排序在這方面有體現出了優勢。這一點恰恰是我在賽場上沒有想到的。

最后回到 dungeons 一題,根據部分分的提示和以往的經驗,我知道這是一道和值域倍增有關的題。即將值域以 2 的冪次劃分后,在每個段中的部分可以使用數據結構一次性解決。從而我將值域以 2 的次冪劃分,每一個部分使用數據結構解決。由于劃分的值域段數太多,由于空間原因我只好放棄倍增而轉用樹鏈剖分??上в捎趦蓚€ log 分配不均,我的做法在最后的 n = 4 × 10? 被卡常數了。于是我將底數改成了 4,然而由于奇怪的原因并沒有能夠獲得最后的 11 分。

結束后,我發現全場有兩個 AK,而且都是中國隊的。出乎意料的是,這次 IOI 中國隊取得了前所未有的包攬前四的成績,遺憾的是我沒有取得個人最理想的結果。

對于這次 IOI,總體來說和目前國內 OI 在賽制以及風格上還是有較大區別的。在平時的訓練中,不僅要培養對 IOI 賽制的適應,更應該加強對這類題型、風格的把握,如這次的賽前訓練中 JOISC CCO 的題就是比較好的例子。希望中國信息學競賽的氛圍與環境能不斷向前,今后取得更輝煌的成績。

最后,感謝中國計算機學會為我們提供參加 IOI 的寶貴機會,感謝領隊韓文弢博士、趙鑫教授的指導,感謝符水波老師對我的照顧與關心,感謝一路上幫助過我的老師和同學們!


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