Virtual : KOI TST 2023 (+ 題解?)

前言

Written by pooh at 2025/02/15
這場我是先打 Day 2 再打 Day 1，Day 2 是去年 11/16 打的，Day 1 是 2/14 (Leolin 生日) 打的，結論上來說這場體驗好多了，題目也比較有趣，Day 2 是我目前打過的 OI 除了 IOI 15 以外覺得最好的。

我可能會打題解，因為這場真的很有趣，完全被 koosaga 的題目們圈粉(?)，LOJ 上 Day 1 少一題，所以我會自己翻譯在下面，然後也因此這篇格式會不太一樣。

交解的地方在這個 韓國酷 judge。

Day 1

一些廢話

隔了四個月以後來 vir KOI，自己感覺是比四個月前有所進步啦，但不知道。

題目

題目

LOJ 上有 pABC。
pA
pB
pC
pD:
有 個人要玩一個遊戲，分成三個階段 : morning, afternoon, evening。
一開始他們會坐在圓桌旁，每個人手上有一個 的數字，且沒有兩個人是重複的。
morning : 每個人可以看到他跟他右邊的人的數字，然後寫下一個 的整數，然後忘記他看到的所有東西。
afternoon : 每個人可以看到他跟他左右的人 morning 寫的數字，然後寫下一個 的整數，然後忘記他看到的所有東西。
evening : 每個人可以看到他跟他左右的人 afternoon 寫的數字，然後寫下一個 的整數，然後忘記他看到的所有東西。
目標是 evening 後沒有相鄰的兩個人寫的數字一樣，令 evening 結束的時候寫下的最大的數字 + 1 是 ，Subtask 2 依照 連續給分。

Subtask 1 : (5 分)
Subtask 2 : (95 分)

實作細節是你可以做 4 個函式 :

void Init() {}
int morning(int my_num, int right_num) {}
int afternoon(int left_num, int my_num, int right_num) {}
int evening(int left_num, int my_num, int right_num) {}

同時他要求當用相同的參數呼叫函式的時候回傳的結果要是相同的。

賽中過程

賽中暴雷

0:00

因為 pD 不見了，所以先去讀了 pD，發現他有點太酷，根本不會做 = =。

實際分數: 0 / 0 / 0 / 0
精神分數: 0 / 0 / 0 / 5

0:30 ~ 2:00

看完 pD 然後放棄了以後就跑去看 pA，看完以後就發現他一定是交一條直排或橫排，所以直接搞個 dp 弄個前綴 max 應該就可以解決，然後就開始時做了。

pA 的實作真的不是一般的煩，邊界 case 不少，我中間還實做到一半腦死，只能說他有點臭。

寫完以後就一發 AC，但實作還是花了我一個半小時，只能說實作真的太慢。

實際分數: 100 / 0 / 0 / 0
精神分數: 100 / 0 / 0 / 5

2:00 ~ 2:40

然後看 pB，看完以後我的第一反應是他是 planar graph 的 max cut，也就是一個為什麼會有人想出在 OI 的東西，仔細再看一下就發現他是個 bounded treewidth 的圖，但我也不知道他 treewidth 多少，因為跟 treewidth 不熟。

總之結論就是他是可做的，然後他是棵樹 + 一個按照前序排好的環這件事看起來就是一臉要你樹 dp 的樣子 (因為在這個子樹上你在意的只有三個點的顏色)，所以我就推了一下樹 dp 式，然後就寫好了。

實際分數: 100 / 100 / 0 / 0
精神分數: 100 / 100 / 0 / 5

2:40 ~ 3:00

看 pC，看了一看發現有 20 分是 Dijkstra，8 分是李超，有一堆 0 的那個感覺是怪貪心 + Dijkstra，所以感覺是某種東西去當 Dijksta 的 Heap ? 沒意外的話應該是李超在某種樹上資節上，還沒想清楚。

先去吃飯再說

實際分數: 100 / 100 / 0 / 0
精神分數: 100 / 100 / 28 / 5

4:15

吃飯回來以後發現已經進入喇分時間了，所以當下先拿了 pC 的 20 跟 pD 的 5 分。

然後就一直在想 pD，因為感覺只要想出一點東西他的分數就會變多很多，而且也寫不完 pC，但到最後都還是沒想出來QAQ。

實際分數: 100 / 100 / 20 / 5
精神分數: 100 / 100 / 28 / 5

檢討

小心得

開版以後很意外，韓國只有兩個人有兩題 AC (也只有他們 200 分以上)，然後他們都是做 pA 跟 pC，pB 全部的最高分只有 11。

我個人體感是覺得 pB 的難度真的沒有比 pC 高，看解以後我還是覺得 pC 比較難，可能是因為韓國人手一棵重心樹所以他們覺得 pC 比較簡單?

pD 看解以後就覺得我沒拿到 57 真的該檢討，另外兩個有 2 AC 的都有 81 分欸，我真的太菜 QAQ。

最終分數 : 225, rk3

題解

有題解欸，想不到吧，喔好像想的到

pA

唯一的觀察點就是兩條路線交叉一定是一個 或 的一段 (因為一旦有一個轉角你就發現會有一個人不可能轉到他。)

有了這個觀察點以後我們就可以把路徑拆成 : 從左上 / 右上到重覆路徑的出發點，左下 / 右下到重覆路徑的結束點跟重複路徑。

假設重複路徑是 到 ，從 跟 到 的最大值我們叫他 ， 跟 到 的最大值我們叫他 ，答案就是 ，顯然可以拆成跟 有關的和跟 有關的分開維護，做一下前綴最大值就好。

實作上細節有些要注意的，一個是 跟 的計算的時候不能直接拿從兩個角落的 dp 值相加減這個點的值，因為這樣可能他們兩個的最佳路徑上還是有重複的(都是從旁邊進來)，所以需要把三個 case (一個從上面一個從下面，一個從上面一個從旁邊，一個從旁邊一個從下面) 和起來。

然後重複的是 可能需要特判一下，不然你可能會兩端進來的地方有重疊。

本質上是個想起來不難但實作有點麻煩的題目，。

我的實作

pB

首先就是這個問題到底在問啥，他叫你拔掉邊權和最小的邊讓這張圖沒有奇環，a.k.a. 最大權的二分子圖，也就是帶權最大割，然後因為他是 NPC 所以就是要利用這張圖的長相做一點 ad hoc。

編號是前序的是個很大的用處，因為這樣就可以很快地知道葉子上的那個環到底長什麼樣子，這時你就發現對於一個子樹上他只有三條連出去邊 : 編號最大的葉子的，編號最小的葉子的，根的，所以你其實只在乎這三個點被分配到哪個點集。

因此 dp 狀態很自然，就是 代表點 的子樹，點 在點集 ，編號最小的葉子在點集 ，編號最大的葉子在點集 ，然後就可以很簡單的樹 dp 了。

我的實作

pC

第一個觀察點是你走到某個點的這條路徑的 一定是遞減的，不然你沒有理由換車。因此我們把 由大到小 sort，注意到 的點其實根本不重要，所以可以先把它們丟掉。

接著就是重心剖分了，考慮維護重心樹，每層維護一顆李超，先詢問這個點的最小值，也就是詢問詢問 的答案 ( 是該層的重心)，然後插入一條 的線，代表從這個點開始轉乘到其他人。

然後就做好了，雖然感覺想起來不難，實作起來東西有點多。

我的實作

pD

超級酷題，有點被啟發到。

Quote from 官解 : 這題是平行的點著色演算法。

首先考慮建造一個函數 他滿足對於所有 ，沒有一個 跟他相等，官解提供的一個很簡潔的是 ，其中 ， 是二進位表示中 的第 位。

為什麼這個是對的呢? 因為如果 的 跟 的 不一樣那 跟 一定不一樣，不然 一定跟 不一樣，否則前面 就不會等於 的 high bit 了。

這個函數輸出的最大值是 ，因此可以將 ，這樣結束時

稍作改變以後可以得到 ，得到 。

這時發現瓶頸在於 的時候這個函數無法再將答案變小，同時其實 還是 。

這時看回他是平行的點著色演算法這件事，因此考慮每個 是一個點，與所以有 建邊，得到一張圖 ，我們預處理 的點3著色。

將這個點著色的結果叫做 ，，得到 。

Day 2

一些廢話

11/16 打的，這場真的很有趣。

題目

題目

pA
pB
pC
pD

賽中過程

賽中暴雷

0:00

讀完題目以後沒有任何一題馬上就知道怎麼做，但有每題都有一些想法，感覺可做，就在一個很尷尬的狀況。

pA 感覺似乎從維護這條邊有哪些區間不會經過比較好下手，但還沒有一個很清楚的實作。
pB 我發現轉成圖以後樹的 case 是好做的，但一個點雙就不知道怎麼下手。
pC 我感覺應該要先知道投訴的條件是什麼再下手，但還沒想清楚。
pD 的 cost 有轉移點單調，除了這個以外不知道怎麼下手。

實際分數: 0 / 0 / 0 / 0
精神分數: 0 / 23 / 0 / 25

0:40

數歸了一下以後發現了 pC 有 complain 的條件，也就是在某個人眼裡如果不存在 ，他第 天就會 complain (題解會有更詳細的解釋)，然後就發現因為 pC 的條件設定，所以問題就被轉成了 TIOJ 2289，然後就會算答案了，但還不會構解。

1:21

因為我圖論建模中毒所以用 DAG 搞出了他的構解，然後就做好了，開始動 pA。

實際分數: 0 / 0 / 100 / 0
精神分數: 0 / 23 / 100 / 25

1:54

發現 pA 要維護的其實就是在子樹內的區間跟子樹外的區間，然後因此我們可以開科朵利樹來維護這個東西，啟發式合並科朵利樹就可以解決。

實際分數: 0 / 0 / 100 / 0
精神分數: 100 / 23 / 100 / 25

3:01

式子推了 8 年然後東西改了 8 次以後 AC 了，然後後面就開始坐牢QAQ。

實際分數: 100 / 0 / 100 / 0
精神分數: 100 / 23 / 100 / 25

4:20

坐牢了一段時間以後就到了喇分的時間了，所以我就寫掉了 pD 的 25 跟 pB 的 12 然後就繼續坐牢，也不知道哪根筋不對不去寫 pB 的 11 分爆搜。

實際分數: 100 / 12 / 100 / 25
精神分數: 100 / 23 / 100 / 25

然後這場就這樣結束了。

檢討

小心得

首先是喇分沒有喇確實吧，以現在幾個月以後來看我開始覺得盡量讓每一題的精神跟實際不要差超過 10 分比較好。

然後再來是 pB 跟 pD，好像大部分的人都至少有一題分數比較高，但我 pB 就一直卡在樹的那個想法上，pD 也沒有注意到轉移點單調是可以用線段樹維護的，所以就有點悽慘，這兩題的觀察跟思考都是有趣的，但就是我自己實力不到。

Day 2 沒有題解，因為我沒有時間寫完 QAQ，但 Day2 pC 真的非常酷，改天再寫他的題解。

最終分數 : 237, rk6

兩天總分

大大暴雷

官解跟板
兩天總分 : 462, rk 3
本質上就是靠著 Day 1 pB，如果我實作力好一點然後沒有浪費時間的話可能可以多個 100 分左右，但還是很多審題上的失誤跟卡在同一個想法太久，實作速度也不夠快，碼力跟審題要再練一下。