---
# System prepended metadata

title: IOICamp 2021 心得
tags: [心得, ' IOICamp']

---

---
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