TOI 2023 四模（+ 選訓心得）

2023-04-25

以下可能會時不時有前幾次模考的爆雷，雖然我不認為有人會略過前幾次直接往四模前進，但我還是發個告示在這，以免有人看一篇虧了四場模考的練習。

至於附件以及詳細細節，我會在能夠得到資訊的時候補充。

題目

A 滑雪跟拍 (Ski)

[Batch 6s/2 GB]

給定長為 $n + 2$ 個點的折線，其中第 $i$ 個點為 $(x_i, y_i)$ 且 $x_i$ 嚴格遞增，對另外不在這個折線上的 $m$ 個點 $(u_i, v_i)$，對所有兩個不同的點 $(u_i, v_i)$、$(u_j, v_j)$ 連接的線段，計算這條折線在線段的兩側切換了幾次，若折線（部份）在線段上則根據最少切換的次數決定這段折線落在哪一側。

實際上的切換次數的定義可以參考下面的說明（這段話並沒有在題本上）

對一條線段 $S$ 來講，我們只看平面上 $x$ 座標在 $[x_0, x_{n + 1}]$ 的點集 $A$，並且令 $S'$ 是 $S \cap A$，如果 $S' = \varnothing$ 那換邊次數被定義為 $0$。
否則，定義折線的上面叫做上面，折線的下面叫做下面，折線本身可以被算做上面或者下面，而切換次數就被定義為將線段 $S'$ 上的點分成上面或下面，使得從一個端點走到另一個端點的過程，換面次數最小的這個次數。

$0 \leq n \leq 5000$
$2 \leq m \leq 5000$
$0 \leq x_i, y_i, u_i, v_i \leq 10^6$
$(u_i, v_i)$ 兩兩相異

分數	額外輸入限制
$21$	$n, m \leq 100$
$19$	$v_i$ 皆相同
$60$	無額外限制

B 整除序列 (Divide)

[Batch 1s/2 GB]

給定長度為 $n$ 的一位數字陣列 $\langle b_i\rangle$，求出位數數量總和最少的正整數序列 $\langle a_i \rangle$ 滿足

$a_i | a_{i + 1}$ 或 $a_{i + 1} | a_i$
$a_i$ 有一位數是 $b_i$

多組解輸出任意一組皆合法。

$2 \leq n \leq 10^5$
$0 \leq b_i \leq 9$

分數	額外輸入限制
$6$	$n \leq 10$
$13$	$n \leq 100$
$22$	$n \leq 1000$
$59$	無額外限制

C 集合比對 (Set)

[Batch 10s/2 GB]

給定 $n$ 個正整數集合 $A_i$ 及 $m$ 個正整數集合 $Q_j$，對所有 $Q_j$ 求出有多少 $A_i$ 與它的對稱差大小不超過 $k$。

兩個集合 $A, B$ 的對稱差定義為 $A\triangle B = (A\cup B) \backslash (A\cap B)$，也就是只出現在 $A$ 或 $B$ 其一的元素所組成的集合。

$1 \leq n, m \leq 5000$
$0 \leq k \leq 9$
所有元素皆屬於 $[1, 10^6]$
$\sum|A_i| + \sum|Q_j| \leq 3 \times 10^6$

分數	額外輸入限制
$4$	$n, m \leq 500$ 且所有元素皆屬於 $[1, 1000]$
$12$	所有元素皆屬於 $[1, 1000]$
$25$	$k \leq 1$
$23$	$A_i$ 兩兩互斥
$36$	無額外限制

D 掃地機器人 (Robot)

[Batch 2s/2 GB]

給定 $m \times n$ 的網格，有一些位置是障礙（#），有一些位置是空格（.），求出滿足下列條件的路徑總數 $\mod 10^9 + 7$。

起點在 $(1, 1)$
終點在 $(1, 1)$
路徑上只有空格（.）
路徑上至少有兩個相異格子
不計終點時，所有格子只能被通過一次
不存在 $2\times 2$ 的子網格沒有被路徑通過也沒有障礙

$2 \leq m \leq 100$
$2 \leq n \leq 9$

分數	額外輸入限制
$18$	$n, m \leq 5$
$31$	$n, m \leq 7$
$51$	無額外限制

比賽

模考又延，所以其實寫回去 9 點開始好像也不會怎樣，反正都會延到 10 點（X
這次又是 11 點開始，然後教室似乎是在 E101 還是 E102，根據 PixelCat 的說法是初選的教室，
題本的封面是用標楷體印的，我記得我一二年級的時候都是這樣但今年的一二三模都是新細明體，看著有一本不一樣就特別不舒服，

開場先讀完四題，A 確定是詭譎幾何，B 可能是怪 Greedy、怪 DP 或怪數學，
題目敘述都莫名其妙的短，感覺這場會不好玩（至少還我 $d$ 輪投票的爛梗吧）
C 很像蔡孟宗之前講過的題目，但我的思考模式一直卡在怎麼知道 $k$ 個差別，尤其值域又有點大，但 $k$ 很小，
但我一看到的時候不知道什麼是對稱差，題目也只有給三角形這個符號，所以就直接發問題了，
記得蠻快就得到公告了，
D 是輪廓線 DP（我等等可能會不小心把它叫做拼圖 DP），

A 大概不是我會去碰的，C 思路一直卡住，然後 D 是我目前知道解的題目，所以我就先開始寫 D 了，

我先寫了狀態的 encode 與 decode，確定沒問題之後開始枚舉拼圖的 case，
寫的途中其實沒有遇到太大的問題，大概一小時就寫完，測完範測 2

3 3
...
...
...

之後 WA 了，輸出是 14 但我輸出 10，把 DP 表印出來之後找很久發現有兩個路徑漏掉了，
這時候順便看到原本的範圍是 $3 \leq n \leq 9$ 然後範測 $n = 2$ 是什麼鬼，發了問題之後就改了，

所以我就一路追溯轉移過程之後發現我初始值設錯，改完之後全部輸出都變 0 了，怎麼會這樣，
大概到一個小時半的時候我才發現我初始值在亂轉移，修掉之後這筆的答案變成 12，也就是還有一個東西漏掉了，
重新比對之後我漏的是這個 case：

xxx
xxx
xx.

（依序是右右下左下左上上走跟逆著走回來）
認真看很久之後，我發現我 ┘ 這塊的 case 有蓋完迴路跟合併兩條路徑的，判完之後這筆就過了，範測 4 也過了，但範測 3 沒過，想說搞不好 $n$ 很大才會出事，所以就先去傳一下

? D 0

吃 WA 了，傷心欸，

我有點忘記了，但這時候我應該是想著先去拿 C 的 25 分 $k \leq 1$，只要 hash 再比對就好了，
寫下去就拿到分數了，

? C 25

回頭 debug D，我想說我迴路會不會判錯了，直接跑了一個詭譎的測資：

6 6
......
..##..
.#..#.
.#..#.
..##..
......

過程中打錯這筆花好久的時間，結果我就發現我輸出 8 而應該要是 0，所以一定是判 $2\times 2$ 壞了或是迴路壞了，結果真的是迴路壞了，修完範測 3 就過了，傳上去得到

? D 49

本機跑範測 3 大小 $9 \times 9$ 其實就有點久了，所以可能還算在意料之內，不過感覺複雜度是對的而且子題感覺就是給亂剪枝的人過 subtask 2 然後不會剪的給 subtask 1，所以其實內心還是覺得有點虧，
不過正確性都有了，如果真的被卡常只要壓壓就好了，應該沒事，

這時候我決定去猜猜看 B，我開始覺得解的陣列不可能很大，感覺會是某個位數以下之類的，所以就亂調了一個 1000 亂寫了 DP 傳上去，

? B 19

所以我就開始亂調界結果一往下就

? B 6

大概 1000 三位數有什麼性質吧，不過我覺得我數論超級爛，怎麼想都沒有任何保證的性質，
不過自己亂跑一下也沒出什麼事，大概就是猜這樣會對了，因為 subtask 2 的 $n$ 也不小，
這時候預處理因數就好，這樣大概就會很快，傳上去就

? B 41

subtask 4 直接 TLE，所以我在想是不是有什麼可以壓的，
這時候我想到的是直接調成一個很大的質數感覺超級廢的，因為根本不可能有這個轉移會用到這件事（你一定有更小的質數可以取代他用），
然後那種因數很少的人幾乎也不會用到，不過確切要怎麼篩選我還是沒有頭緒，
因為夠小的質數其實還是可能被用到的，所以我想到的就是

「那我跑個幾次滿測資，然後把用到的數字蒐集起來做感覺就會過了」

我二話不說直接複製然後開寫這件事，我一開始是一筆一筆跑，但我發現這樣好像還是會漏掉一些東西，因為每筆都差一點點之類的，
所以我就直接讓他跑 20 次這件事了，確定兩次沒問題之後我就把他開滿然後放著讓他跑，

順帶一提，那邊的廁所超級遠（最近的兩個是學餐的廁所跟學餐靠近大樓那邊的廁所），所以我想說我就可以去散散步然後等出來然後亂唬爛，
結果散步完的時候還有 15 筆要跑，爛透了，
（我現在想起來應該是忘記把 -fsanitize=address,undefined 拔掉，各位記得這個雖然很好用但是會變慢）

所以我就先去看看 C 的子題，前面兩個感覺可以亂暴力，然後第四個可以直接比對就好，
那時候我想到的就是直接把每個集合個別 sort，然後用 merge sort 的方式比對兩個集合，
大小差超過 $k$ 就跳掉，然後比對錯超過 $k$ 也跳掉，
這時候我大概在腦中都想完了，而且感覺不會比對太多東西，
只差在等 B 的剩下的測資。

等完之後輸出很棒，像是 13 好像都不會出現，很多大數字也都消失了，大概剩 200 ~ 300 個數字吧，
直接測完發現我忘記回溯的時候跳掉沒有被設為可行轉移的，改一下範測都過了，傳上去

? B 100

接著直接切 C 寫，很快就寫完但範測錯了，
結果是我打錯字，我爛透了，
傳上去超級快就跑出來了，

? C 100

❓❓❓

莫名其妙地過了，我現在覺得他應該是某種根號，然後最多是 $\mathcal O((n + m)S)$，$S$ 是總大小。
我覺得我完全在靠賽，當下腦袋真的卡住沒有想到可以 hash 二分搜（明明我在想字串題的時候很常都是光速想到這件是然後發現會多帶 $\log$ 還會撞到好虧），
也可能是上太多蔡孟宗的課，因為 hash 二分搜丟過去的東西好像會太多，所以很常被題目範圍 reject 掉，
三模的時候我也是很常在 Codeforces 上被卡 $\mathcal O(n \sqrt n)$ 記憶體，所以我覺得我有時候還是要想想用空間換時間這件事，不要只會想著用時間換空間，

回頭壓壓 D 未果，這時候大概剩下一小時左右，看到 A 的滿分是噁噁的極角排序掃描線（可能要 treap），然後我對我 treap 的實作完全沒把握，計算幾何更是不敢去亂試，但子題只要線段相交跟水平的掃描線，然後類似的題目 Codeforces 598F Cut Length 我又有處理過這種東西的經驗，想一想就開寫了，

subtask 1 其實寫蠻快的，因為只要做 point on line 跟 segment intersection 就好，把腦袋中有的計算幾何模板打出來寫，接下來就只要按照順序判要是交一半的話，紀錄上次是從上面進來還是下面進來，然後出去的時候再看要有沒有換邊就好，

範測很快就過了，傳上去

? A 0

太詭譎了，仔細一看題目只有保證無人機（那 $m$ 個點）不在賽道上，但起點可能在飛行路徑上，爛透了，
改完再傳

? A 21

接下來大概還有 30 分鐘，我的策略是先把 A 19 拿到再壓 D，不過我對我的幾何信心不高所以我猜我很可能最後就沒時間做 D 了，
subtask 2 是無人機的 $x$ 座標都一樣，所以先 sort 就能對剛剛這件事跑掃描線，
中途在猶豫 sort 事件該怎麼寫，後來想說 $x$ 座標都是整數那誤差可以接受，直接用分點公式算交點就好，
大概寫完之後測了幾個想到的 case 都對，傳上去

? A 21

所以說我一定漏掉什麼了，想一想把掃描線的東西改來改去

? A 21

這時候還有 10 到 20 分鐘的樣子，我直接拿出剛剛寫好的暴力對拍，拍拍拍就拍出一個 WA 的測資，
結果是我測資的 $x$ 座標重複了，大燒雞，

座標調大之後就真的拍出錯的測資了，結果是我分點公式寫反，大燒雞。
傳上去得到

? A 21

繼續看看的時候發現我怎麼思路好像跟剛剛不一樣，一看之下就發現我掃描線漏 case 了，快速修完就直接傳上去

? A 40

這時候大概剩 3 分鐘了，我想我 D 也真的壓不下去了（光範測 3 就要跑 2 秒多），所以我就走到外面去把我的健達繽紛樂吃掉，然後慢慢等比賽結束。

Result

A	B	C	D
40	100	100	49

模考心得

我出場的時候想說大概會有一個做 A 然後一到兩個做 D 吧，結果根本都沒有，
其實我賽中就應該要想到 D 的 subtask 2 應該至少要插頭 DP 才能過，故事是這個爆搜我根本就有在留社考出過，當初準備問題的時候 $n$ 是有 $3, 5, 7$，但後來因為 $7$ 的 case 就算有剪枝也跑超慢所以我就把他從題目裡面拿掉了，
而且我還莫名其妙地拿到全場聯集，不得不說我 C 真的在靠賽，
很幸運的我在四模還是做出了兩題 Batch，不知道 APIO 會不會就斷 combo 了，

選訓心得

這四個禮拜的選訓，我感覺很開心，
至少我能夠沒有後顧之憂地把專題丟掉（結果我現在就得還債了）
然後在這裡盡情的學習競程，跟人 virtual，看芒果做 AGC，看 PixelCat vir IOI，看 Darren 雀魂役滿，還有很多是只有在這個選訓營，才有可能看的到、做得到或者體驗得到的，
對選訓以來不小心被我的腦袋短路的時候嗆的人，我在這裡道歉，雖然我不是個會嗆人的人但有時候腦袋壞掉的時候會講一些不知道在幹嘛的話，

至於排名的話，四次模考的總成績是

1A	1B	1C	1D	2A	2B	2C	2D	3A	3B	3C	3D	4A	4B	4C	4D
22.26	100	61.69	100	100	100	12	0	43	100	100	5.88	40	100	100	49

根據邪惡表格的說法我是 Rank 1 且不會被 APIO 逆掉國手，
四模一出場聽到芒果 182、PixelCat 也 182 的時候我真的有點難以置信我能夠贏超過一題的分數（不是在嗆人），
仔細想想我在整個競賽的生涯中，我真的沒有發自內心說過「我很強」這類的話，
大多數都是檢討「我實作穩定度爛透了」或者是勉勵自己「我要變強」這種，
對我自己而言，我總是有更多的空間可以變強、有更多的領域需要加強，
回想高一 Rank 23、高二 Rank 14，感覺在這四次模考打到這個成績，或許就是有點那麼

那麼不真實。

1A 沒有想過可以暴力跑所有路徑，明明我曾經在校內的留社考考過 $5 \times 5$ 的 Hamiltionian Path 暴力 DFS，
1D 靠著運氣通過了，賽後更是被許多人生出卡滿的測資，
2C 雖然我不認為在我想到的範圍之內，但轉成圖是我根本沒有下手的部分，
2D 沒有發現物件只有兩個有簡單的解法，
3A 在 Codeforces 常常用根號過題目的我竟然沒有想到可以暴力記錄每一塊的出現次數，
3D 更是完全沒有觀察到任何好用的性質，
4C 大靠賽拿到這個滿分，

我不知道我在其他人眼裡是強還是弱，但我自己覺得（在不參考邪惡表格的前提下）我打成這樣，我從來都不可能是強的一方，
但事實似乎在說服我，我或許是有那麼一點實力的。

無論如何，就算最終大家發現我是最沒有實力的那個人，就算最終我還是學不會對我自己有自信，
我覺得我還是能自信地說出「我在選訓很快樂」，
這樣就夠了，至少我達成了最初的目標，至於國手什麼的之後再說吧。

突然覺得有好多想說的，但一打字起來就不知道要怎麼表達了，
總之我覺得我的整個高中競賽歷程，實在是太神奇了。

[更新] 題本

4A.pdf 4B.pdf
4C.pdf
4D.pdf