IOICamp 2021 心得

--- tags: 心得, IOICamp --- # IOICamp 2021 心得 [TOC] ## Day 1 === 營前 === 早上兩點多睡覺，然後五點半起來趕火車，好累 zzz === 上午 - 殿壬的喵喵時間 === 然後今年終於聽到喵喵時間了 >////<，不過今年沒有喵三下吸收電力 ww 發現隊友其中一個是學校的學弟 @王宇森，另一個是 joy 前隊友跟前前隊友（缺席）的 @吳典叡第一天基本都在寫測試賽的題目 0A. 區間修改 / 區間加值 / 求區間和 / 求區間 max 0B. 矩形覆蓋面積本來想用分塊寫 0A，結果寫爛了 de 不出 bug，中午才用線段樹好好寫掉，0B 不會分析複雜度，以為在線段樹上暴力求 1 的個數會 TLE。我就爛不會資節 QQ === 中午 - 午餐 === 今年因為疫情影響，吃飯要梅花座，而且不能講話，甚至連去年播的動畫都沒有了 QQ 一邊吃飯一邊幫 @林哲宇 debug 線段樹，結果還是找不出 bug 吃飯好無聊ㄛ === 下午 - 圖論 === 圖論今年的進度好像有點慢，本來想聽關於擬陣的部分，不過連 BCC SCC 都沒講到，還是在 Day 2 的進階資節上繼續補的，燒雞 === 晚上 - 總召好帥趣味賽 === 晚上是趣味賽，題目似乎越來越少了，而且今年的除蟲題只有兩題，好難過ㄛ 1AB. （除蟲）floyd 的咚咚 1CD. （除蟲）sort 的咚咚 1E. （駭客）[TLE] sort + dfs 01 背包 1F. （駭客）[WA] LCS 數量 1GH. （駭客）[WA] 最近點對 + 旋轉 1I. （駭客）[TLE] 最近點對 1J. （通靈）水題 1K. （通靈）正常的題目 (?) 1L. （通靈）偷 header 1M. （通靈）avx512 壓常 1NOP. （通靈）給一些越來越「好」的字串，求一個夠「好」的字串開場我先看 ABCD，隊友負責 EFGHI，過幾分鐘之後發現記分板一堆人過 J，於是就看了一秒想到做法跟隊友說，然後沒開 long long 吃了一次 WA 接著發現 A 的 floyd 順序爛掉，所以把它修好就過了然後又試出只要跑兩次 dp 就能 AC，於是就把一堆東西塞進註解裡面搞出來一個 `dp();`，搶到 B 首殺 >////< 跟著記分板把 G 水掉之後，就進入一個小時的燒雞期了記分板上 EFK 貌似都可做，我跟隊友就輪流看這幾題，我 random 了幾次 E 不過它的解都只跑 1ms，我在想 F 的爆 long long 方法，隊友在找 code 有沒有錯，K 看不懂題目，到封板前都沒過任何一題不過在封版前幾秒，記分板上出現了這個 ![](https://i.imgur.com/cKYkJnh.png)，於是我也跑去通靈 NOP，在 P 隨便唬爛一個東西之後交上去拿到 WA 就沒有再試了封版後終於想到 F 爆 long long 的方法，隊友丟了 `A`\*50 跟 `A`\*100 之後拿 WA（UPD：輸出第二行之後沒換行），再寫一次 `AABBCCDD...UUVVWWXX` 跟 `AAAABBBB...WWWWXXXX` 之後拿到 AC 最後終於看懂 K 的題目，雖然感覺不出它有任何通靈的成分，總之就正常的 dp 掉了最終以 6 題結束，Rank 14 === 回飯店 === 離開的路上重新看計分板發現我的 P AC 了，還拿到首殺！？接著看到 P rejudge 的訊息，變成 7 題，Rank 8，超開心ㄉ >////< 晚上回飯店房間，室友是 @周得壹不過在發現旁邊房間住的是 @李明奕跟 @黃仲群之後就跑過去玩 (X) debug (O) 了一整個晚上，@邱翊均也在，李明奕在寫噁心的 JOIOC '18 Cats And Dogs，我在耍廢 (?)，一直到兩點多才回房間 ## Day 2 === 起床 === 7:00 morning call，結果我大概只睡了四個小時，洗澡也是早上起來才洗的 w 跟著大家一起走到台大，今天是數學跟資節，要被電爆ㄌ === 上午 - 數學 === 今年的數學內容比去年多了很多，FFT、生成函數、線性代數都是我想聽的咚咚在 slido 上發了想聽快速線性遞迴的 request，結果沒人理我 QQ 多虧 SCMS 有聽 @Andrew Yang 的群論，今年聽 Burnside 終於有大概理解他在做什麼了，然而一聽完燒邊我就睡著ㄌ，一醒來已經快要下課ㄌ QQ 不過我想聽的部分貌似今年也沒有講到 owo === 下午 - 進階資料結構 === 把初階跟進階分開講果然是正確的選擇呢，不過初階就講到 Treap 跟持久化真的讓我遲疑了一下該去哪邊 wwww 雖然叫做「進階資料結構」會覺得有講到很多資節，但是其實全部都是線段樹 (O)，之前看吉如一一直看不懂，現在聽過這堂課之後有點理解ㄌ一邊寫 Legacy 一邊聽 @Brian Tsai 講題目，看到 @吳邦寧又被拿出來鞭，期待明年再多鞭幾下 (X) 講完之後開始繼續教圖論的 BCC 跟 SCC，@塗大為（圖論講師）跑來說：「先講點雙連通」波路特石：「你要不要來講」塗大為：「不要」 wwwwwww 波路特石：「欸，隔壁（初階）怎麼講那麼慢」某人：「5:50 下課」波路特石：「真的喔，我以為是 5:20」吃完晚餐之後跟 @張程凱至高無上、@王政祺、@王品翔、@Wiwi Ho 打拿破崙（窩不知道有沒有漏標 QQ，有的話麻煩請跟我講一下owo），第一把王政祺就直接全吃 <(\_ \_)> === 晚上 - 總召好帥之數學好難個人賽 === 2A. 求所有樹上距離為 2 的點對數量的期望值 2B. 奇怪的題目 2C. 水題，拿到全國音樂能力競賽一等一的 KCZ orz，聽說有做出這題的人說不定會因此不再被 ptnilyoj 預（ㄕㄨ）測（ㄈㄨˊ）(?) 2D. 進階資節習題，區間加值 / 區間取 min / 求區間和 / 求區間 max 2E. 把有向圖拆成環跟練，問鍊的數量的最小值 2F. 裸圓方樹，但是實作量頗大的噁題 2G. 區間 mex，比 2016 年的還要簡單一點 owo 一開始先把題目都看過一遍，看到 C 有一個 $f(x) = \frac{?}{x^2 + 1}$ 瞬間把它丟掉，看到 F 以為是所有詢問都輸出 Yes 的梗題，結果把輸入刻完才發現他是圓方樹，於是也直接丟掉 (O) 這時發現計分板上面已經有一排過 C 的，於是靜下心來看才發現是水題 QQ 接下來其他題目都沒有感覺可以很快作完的題目，於是就先找 A 的數學式，用 Prüfer code 拆掉包裝之後 AC，發現至高無上已經三題了 orz 想說既然隔天要補題，那就先把比較模板的 D 寫一寫，結果就這樣 debug 到結束ㄌ甚至有一題是我拿來出題的原題我都沒做出來，我弱最後以 2 題結束，Rank 14，意外的是雖然第一名只有四題，卻沒有題目滅台，BDF 都有恰一個人解出來 wwww === 回飯店 === @林煜傑說他是爆搜 + 觀察得到 2A 的通式 <(\_ \_)> 今天買宵夜的時候我跟室友都忘記帶房卡，我們回去的時候都跟櫃台要了房卡，所以就變成有六張房卡ㄌ晚上再度跑去隔壁房，人貌似又變多ㄌ wwwwwwww 大家一起找出李明奕 Beats 的 bug 之後就一起燒雞在我的 bug 上面，一直到三點都還找不出 bug，就在即將要睡覺之時，我發現我又沒帶房卡，然而因為室友在睡覺，我就睡在李明奕房間ㄌ ## Day 3 === 起床 === 喵喵喵，結果昨天沒有洗澡，只有換衣服而已 === 上午 - 字串 === Boook：我負責在 LYB 隊上雜耍 AC 自動機還是聽不太懂，不過講義上的字串集是 $\texttt{"ioi", "iloli", "olioi", "ioioi"}$ 到簡報上就變成 $\texttt{"ioi", "ijoji", "ojioi", "ioioi"}$，我的 loli 呢 QQ === 下午 - 動態規劃 === 今年的 DP 優化比較著重在四邊形優化上面，不過凸跟凹我還是不會分 QQ 轉移點會不會單調我也看不出來 QQ 今天晚餐吃披薩，但是因為疫情只有個人餐 QQ 晚上又打牌，亂喊直接被打爆 QQ === 晚上 - 總召好帥之披薩好好吃團體賽 === 3A. 習題改編 Pattern，求有幾個連續子區間在樹上形成簡單路徑 3B. 計算 Partition Number + Möbius 反演 3C. 給一些只能當嘴上或右下角的點，求最大矩形 3D. 沒看 3E. 找出一組順序滿足 hash function 使最終陣列的樣子跟給定的相同 3F. 在可以把一個 1 改成 0 的情況下，求全 0 的矩形最大面積 3G. 上課習題，KMP 轉 Z-value 3H. 水題 3I. 直接寫可能有點難，但是 Hint 直接破梗就變水題ㄌ因為吳典叡上課一直在看 Z-value，所以他就把 G 撿走，我撿走 H，不過我實作能力大降，過了 26 分鐘才 AC 接著因為記分板很多隊開 I，所以就跟隊友一起看題目，連想的時間都沒有，一看到 Hint 就會做了 owo，於是就把 I 也撿走然後我的 Partition Number 一直耍雷，甚至交了 O(N^2) 記憶體跟 O(N^3) 時間的 code 上去好幾次（$N \le 10^4$），還自以為不會爛掉過了一個半小時終於 AC，然而題目最後有一句「如果 N 可以達到 2e5，你有好的做法嗎？」，怕爆（Library Checker 有這個模板ㄛ）最終 4 題，Rank 9，DF 滅台 === 回飯店 === 本來想說 11:05 會到飯店，大概 11:10 會解散，11:40 查房，可以先去吃永豆，結果 YP：「今天比較早回來，所以 11:30 查房」QQ 今天 5067 的人又變多了呢，連 @Ji Kuai 都在，雙人房已經擠六個人了 www 晚上跟一堆人去買宵夜，回房之後周得壹說身體不太舒服，於是就跟助教說，助教就帶著他去屈臣氏買藥，結果 YP 跟我說他們討論過後我跟周得壹都需要被隔離，我從 5068 搬到 5073，而且只能待在旅館裡線上上課 QQQQQQQQ 感覺心理狀態開始崩潰 (?)，特別是在這三天都只睡不到四個小時跟缺乏營隊的集體參與感之下，不過我還是繼續寫題目到三點多才睡不過今天晚上終於可以抱著拉菲跟四糸乃睡覺ㄌ >////< ## Day 4 === 起床 === 今天沒有 morning call，設定的 7:20 鬧鐘也沒有響（或是沒叫醒我），所以我一路睡到 8:50 才起床嘗試加進去早上網路流課程的線上直播，不過我試了十幾分鐘都是「你的加入要求無人回應」，所以我就躺下來繼續睡ㄌ，睡到 10:40 起床之後再度嘗試，又收穫了幾次 TLE 之後戳 @唐博彥才成功加進去，今天真是睡眠最充足的一天呢 owo === 上午 - 網路流 === YP：我負責在 LYB 隊上雜耍從最小割例題 - 喵喵發大財聽到 Stoer-Wagner 就聽 Bert 說有午餐可以ㄘ，於是我就下樓ㄘ午餐ㄌ === 中午 === 跟 Bert 還有 @王師宇學姊一起吃八方，發現 Bert 真的很酷 wwwwww 酷哥 Bert，名不虛傳 >////< 回房間聽了 Day 2 題解，不過還是不會做 2B === 下午 - 組合賽局 === lawfung：我負責在 LYB 隊上雜耍這是我最想聽的部分，因為我對於 Game 的理解就只有，「我燒雞你就打爆我，我可以打爆你你就燒雞」跟 nim 要 xor 等於 0 而已很多 Game 的題目都需要證明正確性，而且大部分的題目都很難直接想出來，可能是接觸過的東西太少了ㄅ QQ，我都只會打表看規律而已稍微睡了一下，從 Coin-Game 睡到 Hackenbush，結果醒來後直接大燒雞，看不懂 $\{a_1, a_2, \dots | b_1, b_2, \dots\}$ 代表什麼意思 QQ === 晚上 - 總召好帥之 LYB 到底是誰在雜耍個人賽 === 所以說 LYB 到底誰在雜耍ㄋ wwww，我投給 boook 一票，不過聽說最多人投的是 lawfung QQ 4A. Nim 對戰只取最大堆 4B. 計算 $\sum_{i=1}^{N}{\sum_{j=1}^{i}{\lfloor{\log_{i}{j}}\rfloor}} \pmod{10^9 + 7}$（$N \le 10^{12}$） 4C. 字串處理 4D. 習題改編 Chomp 4E. 「最後的個人賽，小明超級厲害，花了兩個小時，費氏數列ＡＣ，最後的個人賽，大明有點品祥，流水題不ＡＣ」裸題 4F. 字串題 4G. 裸線段樹優化建圖 + 二分圖匹配 4H. Nim，操作有選任一堆 -1 或 /2，問能不能拿走最後一個 4I. LYB 到底是誰在雜耍先寫 I，結果開到團體帳號，還聽到 BB 在前面說記得要用個人帳號 wwwwwww 寫 D，WA，我就爛不會 Nim，於是就打表找規律 AC ㄌ寫 C，WA 寫 C，WA 寫 C，WA C 的題目重新修改，把「每段話最後一定是句號」的條件移除了，也把之前的三筆拿掉ㄌ寫 C，WA 寫 C，WA 抄 E 模板，TLE，不過發現是每一筆都 TLE 之後就覺得是其他地方出 bug ㄌ，最後找到的雷是 `ios_base::sync_with_stdio(0)` 會讓 `getchar()` 爛掉，AC 重新寫 C，AC 推出 B 的式子之後下去砸，本機跟暴力對拍都對，但是傳上去 WA，de 不出 bug 來，燒雞去猜一些 A 的性質，不過還是 WA 4 AC，Rank 25 === ~~回~~飯店 === 發現 LYB 邀請賽 R3 pI 跟今天 4A 一模一樣，難怪我覺得我看過，但是我還是不會做 QQQQQQQQ 拜託李明奕幫我買 7-11 的綠咖哩當宵夜，雖然辣辣的但意外的還不錯吃！（忘記還錢ㄌ owo，我要還 70 塊錢）晚上黃仲群展現出強大的 debug 能力，在完全沒看我的 code 的情況下成功指出我的錯誤 <(\_ \_)> 晚上用電視看了 0.5 集神裝少女小纏跟 1.5 集的輝夜姬，發現還不錯ㄟ，之後可以看看 >////< 一直想不出要怎麼證明浪漫 Duke 是智障（4A），感覺我才是那個智障 QQ ## Day 5 === 起床 === 今天意外的是跟其他人一起走到台大，只是聽說會帶到別間教室打比賽拍了團體照，由於帶著口罩，所以就讓拉菲站前面一點才看的到 owo 正式賽快要開始的後就被帶到五樓的一間教室ㄌ，只有我跟某個不認識的助教 QQ === 正式賽 - 總召好帥之總召真的好帥正式賽 === 我不太想打題目敘述 QQ 一開場看完 A~F 我：「ㄟ，記分板上很多隊過 G 欸，你們要不要寫寫看」吳典叡：「喔我已經 AC 了」<(\_ \_)> 這場打得實在不能再爛了 QQ 丟給隊友 J，不過他對 Hash 不熟，所以最後是我收掉然後我 E 直到全場有約 20 隊 AC 之後才看到，於是我就直接 claim 答案是問有幾個子集 xor 是 0，RE 一次、MLE 一次、TLE 一次，最後直到用折半才過，為什麼這麼明顯的作法我沒想到呢？因為我這幾小時燒雞在 F，從頭到尾我都沒有注意「子序列」是下標要遞增的，在一堆不存在的 bug 上面處理半天，卻沒有去好好的讀過哪怕一次題目，甚至到最後一小時我也沒將這明顯的 bug de 出來，成為全場唯一沒 AC 的隊伍接下來的 B 也是，題目問「使離最近的距離盡量遠」，但我卻把它當成「使連續空格的區間長度盡量長」，連題目都不會讀我到底還能幹嘛 :angry: :angry: :angry: 最後 3 AC，Rank 24，倒數 1 === 頒獎 === WiwiHorz，說要打的滿意就直接大一位恭喜 @林秉軒拿到捕蟲網恭喜張程凱拿到兩個筆電墊 (X) @Balbit balbit orz 恭喜 @Lai Justin 拿到四顆水球 ## 結語可能還會有個結語ㄅ，不過那不重要，也不會算在請拉麵的範圍裡ㄌ，想卡的人請自行退散喵 0w<  https://hackmd.io/@SorahISA/BJjRHl8gd