IOICamp 2022

高一的時候太笨根本不知道有 IOIC， 總算今年報到了 ><

Day -?

雖然今年營隊改成線上的很可惜， 但我收到講義的時候超興奮的， 那時候翻了一遍講義，順便把習題都整理出來，大概有 350 多題， 戳了幾題看了也完全沒有想法，大概我有生之年是寫不完的吧。

寫基礎資結的習題寫得很挫折想說要不要放棄聽進階， 但聽說即使聽了那堂課習題也不會寫是正常的所以後來就去進階了。

Day 1

早上不是經驗分享，是何達睿講了一些有關競賽跟這個營隊的事情， 中間有講到各種活動對應的 CF rating， 看到二階被放在紅牌，然後自己也特別笨連深橘都上不了應該今年會連初選都過不了吧， 還有總召波路特石在講營隊規則的時候講到了今年有特別的 Flag 機制，感覺很酷， 接下來就是 Gartic 的益智破冰，超難猜還好隊友吳威錡超強，通靈大師orz

順帶一提，找到 Flag 是沒有附贈舒服的， 但中午突然多出空題，我一開始傳了 CE 拿到了普通 submission CE 的首殺， 後來我想說傳傳看正常的 Code 看看結果拿到了 Flag， 但我沒有很想喝飲料，所以後來就請工作人員幫我給下一個人順便舒服他了， 後來那個 submission 被刪掉了，然後我也就沒再找到過 Flag 了 qwq

下午是資料結構，我對李超線段樹 Ex. 跟線段樹優化建圖比較有感受， 但聽到吉如一線段樹 (Segment Tree Beats) 就直接燒雞聽不懂， 那時候剛開始聽完全不知道為什麼暴力是好的，直覺我的線段樹暴力下去就會失控， 甚至不會維護同時有取 $\min$ 跟加值的懶標，是上課去戳 PixelCat 問才會的， 講到兩個陣列、歷史最值還有區間取 $\min$ 跟 GCD 直接聽不懂，被打爆。

晚上團體趣味賽完全不知道是駭客題、除蟲題跟構造題，一進去有點嚇到， 點開的題目完全不會做，被抓到自己不會 C++， 過程中只做出三題，其中一題是 Easy，一題是測資爆搜 那題傳了超多次因為我原本想用 Memory 分但好像被優化掉了，笨到忘記可以用時間分zzz 另一題是浮點數的 bug，那時候我覺得爆不了精度大概就是往 inf 跟 nan 想， 不過 checker 爛了所以我是全場唯一唬爛過的 ><

Result:

Day 2

早上是數學課，聽到組合技數的後面幾乎是在想「這到底怎麼通靈出來的」， 還好後面幾天出組合計數的題目不多 (? 數論前面都還能跟上，但是到歐拉函數、循環節跟原根的時候幾乎都聽不懂， 後面多項式操作只聽得懂 FFT，慘。

下午是進階圖論，沒想到支配樹沒有想像中的那麼恐怖，Lemma 還算能理解， 有向最小生成樹也還能理解， 但擬陣真的太抽象了，到現在還是聽不太懂，燒雞。

晚上個人賽一開始先讀題，然後就看到 C，發現這不是就一臉排序不等式嗎， 寫下去傳了才發現可能會有正負的 case，我有點忘記原本的不等式有沒有正負了， 然後他就過了，首殺好耶， 之後覺得 D 一臉二分搜樣，寫了二分搜 + greedy 過了， 這時候 E 看到原本要開刻 SCC 的，後來發現他是 DAG 所以就直接拓撲排序就過了， 中間傳來 D rejudge 變 WA，後來發現他 greedy 應該是爛的， 隨便構就發現這樣做會有很多無法決定的 case，決定跳去做 A 數學題， 想著想著發現 $K$ 最多就只有 $30$，就想了一個排容傳上去 WA， 想很久之後去寫了暴力對拍發現自己有多 1 少 1，發現是判太大的 if 壞了，換成 pow 去估計就過了， 後來把 GH 暴搜分寫完，看板很多人會 G 就在那邊想要怎麼砸線段樹， 想了很久終於有合成函數的想法，複雜度 $O(NC \log N)$ 但傳上去被卡常，我線段樹常數怪， 後來沒過，燒雞。

Result:

Day 3

早上是賽局，講師超會嘴砲， 上完真的有對 SG Value 是怎麼來的有更進一步的理解了， 可是還是不會通靈，我爛。

下午是進階 DP，真的很酷， 上課大概就是 ZCK 講題目然後抓人duel讓有想法的人上去討論， 題目很酷，拆題目的方式也很酷， 但題目真的太難了，至少上完比較知道要怎麼定 DP 了（吧。

晚上團體賽我以為又會跟 Day 1 一樣，結果是正常比賽。 進去我先看 GHI，發現 I 是裸的雙指針就寫下去 AC 了， 吳威錡超強，把 E 做掉去看 H 但很不幸的 TLE 了， 這時候我們已經有一大段時間沒進展了，當時我看 A 應該就跟烏龜疊疊樂一樣是斜率優化， 想清楚之後開刻 deque，過程中一直被細節卡到。

這時候工作人員就進來問我們需不需要提示， 我說我在做 A，同時王亭懿在看 B 她說她等等再看看需不需要提示， 然後我 A 就一發過了。

工作人員：你們應該不用提示了

然後他就走了 XD
吳威錡問我說要不要看 D，我看了一下發現是 DSU 水題就跟他講解之後就過了， 同時王亭懿看出 B 的奇數 case，但不會偶數，我跟他說偶數就 /2 XOR 起來看 SG Value 就好， B 也過了，起飛， 後來我去看 H Claim 了一個感覺會唬爛過的解，我跟吳威錡驗驗看，他覺得它會爛掉， 但因為我們手邊沒有更好的解了，所以我就跟他說我傳上去唬爛看看， H 過了，好耶，唬爛成功 🎉

最後我們全力在做賽局 F 但好像假解了所以找到的循環節是錯的， SG Value 是對的但不知道為什麼我們會爛。

Result:

Day 4

對不起字串講師，早上我睡過頭了，笨死zzz 還好字串前面沒講很難的東西，所以直接聽後綴平衡樹還可以撐得住。

下午是計算幾何，一個很酷但又很煩躁的東西， 聽了很多酷題，但完全沒練實作所以很多燒雞燒掉了， 掃描線收穫很大，還有如何減少枚舉這個技巧也很酷。

晚上是個人賽，開場先讀題， H 根本就簽到題，傳上去就 AC 了， 回去看 B 觀察了一下覺得可能性很少，本機爆搜完就傳上去了，WA 發現是自己沒有刪乾淨不合的東西，刪一刪就 AC 了， 接下來去刻 C 的線段樹，因為看到二次方把它展開就很顯然了，所以直接開寫， 吃了兩次 WA 因為忘記在算一次項要乘以區間大小，燒雞， 回去碰賽局 E，打表看完規律傳上去得到了 WA， 想很久之後發現講義有 $t = 0$ 的 case，抓到我打表都在亂打，重新打完傳上去就過了， 做完之後去看了 F 先寫了 $O(NK)$ 的傳上去拿 25 分，看了記分板一堆 WA 我猜應該是沒有凹性所以就不打算砸 Aliens 了， 之後就是猶豫要寫 D 50、G 100，還是 G 40，這時候我應該先去做 D 50 因為他只要倍增就做完了， 但實際上我去寫了 G 100，是這場的敗筆之一，因為我沒有把握 G 可以刻完， 後來 G 刻完 WA 我才發現要映射到 $[0,\pi)$ 才是對的，被邊界搞了很就之後就掛了， 我就算要刻 G 也應該早一點發現才對 -w-，根本沒想好就開刻是這場的另一個敗筆。

Result:

Day 5

燒雞團體賽。 開場吳威錡 Claim A 組合超少就做出 A 了， 這時候我看後面幾題都沒想法，吳威錡問我說要不要寫 G 裸李超，我就去寫了然後過了， 之後吳威錡去做 B，吃了 WA 然後請我幫他 debug，
：$n$ 會不會可以是 $0$ 啊
：如果加上去過了我就爆氣
然後 B 就過了， 接著我繼續看題目，然後吳威錡去寫 K 17 分， 後來我跟他說 K 我應該會做就去刻 SA 跟 LCP 了， 講義的模板本機 RE 所以我就再想了一下 SA 跟 LCP 要怎麼做， 後來傳上去第一次忘記拔 debug，超蠢， 第二次我還是忘記拔 debug 的 assert，但它不應該 RE 的， 這時候傳來 K 爛掉了會 rejudge，
：我們就先當它過了好了
之後我把 E 的表打出來了，然後吳威錡超強都會看規律， 找到之後 Claim 我其實也不知道他是不是對的但傳上去就 AC 了， 後來不知道什麼時候吳威錡做出 F 20，超強， 後來我去做 D，然後隊友在走自己的路（N）， D 一開始我想位元 DP 然後後來就發現位數會很多個，就改做背包， 完全忘光這時候就可以同餘最短路了，笨死zzz 後來隊友沒走出自己的路，然後我唬爛過 D 了， 我的方法是枚舉 $1, 10^1, 10^2, \cdots, 10^K$ ，然後判完答案 = 1 的取嚴格前 $C$ 小暴力背包，
很神淇的就過了，超唬爛， 整場我都在耍笨，J 沒看出是凸包然後 M 也沒發現可以差分，該回去基礎班了吧。

Result:

心得

在 IOIC 完全被揍回原形，我不會寫程式， 然後還被山姆整天嘲諷，燒雞， 希望可以至少把 IOIC 習題做完 $\frac 1 3$，然後補完 $\frac 7 {10}$ IOIC Judge 上的題目， 不然到了初選我還是一樣弱 qwq

另外想要 IOIC 題目整理的可以來找我，條件是你有參加今年的 IOIC ><