2021IOIC-Day4

不知不覺就到了最後一天上課了(明天會是五個小時的大團體賽)，時間過真快。

今天上的東西都是屬於我不太熟悉的，所以感覺可以學到不少東西(前提是聽得懂)

課程

早上

早上上了flow，其實之前就有用過dinic來二分圖最大匹配了，可是都沒有好好搞懂它的原理過。

今天搭配證明後就懂了><，同時也學到原來MCMF的複雜度其實很糟，跟最後的流量答案有關。

我還以為只是dinic的複雜度再乘上V或E而已。

原本我不會SPFA的，但是因為MCMF要用到，然後就不知不覺學會了www。

不過建模是真的很難，例題就有些沒很懂了。

最小割的應用也超級神奇，有些例題完全無法理解orz。

yp在開場就說他是他們隊伍(LYB)負責雜耍的。

下午

最後一堂課QQ，組合賽局。

組合賽局應該就是我最陌生的地方，以往只有寫codeforces的梗題才會用到game theory這詞。

一開始看到講師的投影片才195頁，相比其他講師都5 600頁少很多，尤其他又說這堂課應該是到目前最簡單的一堂。

在無偏賽局的前半段還好，把SG value搬出來後就有點小障礙了，後面的有偏賽局最後部分可說完全不知道她在說什麼QQ。

不過lawfung真的講得很好，有把定義都好好講清楚，所以我之後自己讀應該也能讀得懂(希望啦。

lawfung在開場就說他是他們隊伍(LYB)負責雜耍的。

晚上練習

今天是個人賽。

開場一分鐘就有人ac了，去看才發現他是問LYB誰負責砸耍XDD。

沒給其他東西，我還想了大概10秒到底要輸出誰，不過原來輸出三個人的名字任意一個就能AC，然而還是有人能WA XDD。

後來去開計分板上也很多人AC的題目，他是一個賽局論的題目，看到有人7分鐘就ac還有ac人數很多就猜他是梗題。

他的輸入有兩個數字n,m(<=10^9)，所以其實可以靠打表通靈。

但我想說我都上了一個下午的賽局論，應該可以自己想想看吧。

所以我就手列幾個case，然後傳上去，就wa。

發現新的case，再傳上去。又wa。

就這樣重複了四次，我果然不會猜梗。

所以先去寫別題，有一題就是裸裸ㄉMCMF，把講義的模板抄上去後就爽爽AC。

也把其他實作題都寫一寫。

之後發現那題梗題的ac人數真的超級多，所以我就放棄思考開始打表了。

然後表超級有規律，一眼就看出的那種。

結果我就因為這題的penalty排在超後面，好討厭梗題。

有一題線段樹優化建圖再Flow求二分圖最大匹配，還蠻有趣的，之後要把他理解。

第四天的名次其實算是最滿意的了><，除了penalty真的很多。

住宿

今天跟室友聊了一點天，之後又跑去昨晚那個房間，原本想說明天要正式賽別太晚睡拖累隊友，結果還是弄到兩點多了@@。

最後一個晚上了，其實這個室友還不錯，原本擔心遇到太雷的，我反而擔心在他眼中我是雷室友QQ。