[TOI] 2022 1 模

2022-03-28

TOI , OI

賽前

賽前真的很緊張，感覺有超多人都會爆打我（結果好像也的確如此），只能好好把心態穩下來 qwq

賽中

進場時間燒雞，所以整場往後延 10 分鐘。
開場先讀 A

A diophantus [5.0s, 1 GB]
給你 $n$ 個數字，問有多少組有序的 $(A, B, C)$ 滿足 $A x + B y = C$ 有整數解。
$1 \leq n \leq 10^{5}, 1 \leq a_{i} \leq 10^{7}$
[4] $n \leq 50, a_{i} \leq 100$
[15] $n \leq 700, a_{i} \leq 10^{6}$
[33] $n \leq 5000, a_{i} \leq 10^{6}$
[48] 無額外限制

看了之後大概是數學排容之類的東西，然後看下一題，

B dungeon [2.0s, 1 GB]
給你一張 $n$ 點 $m$ 邊帶權的 DAG，其中一個拓撲排序是 $x_{1}, x_{2}, \dots, x_{n}, y_{n}, \dots, y_{1}$ ，
問從 $1$ 開始，從 $x_{1}$ 開始經過所有下標 $\in [2, n]$ 剛好各一次並到達 $y_{1}$ 的最短距離。
$3 \leq n \leq 5 \times 10^{4}, 1 \leq m \leq 5 \times 10^{5}$
[7] $n \leq 10, m \leq 190$
[17] $n \leq 500$
[5] $n \leq 5000$ ，保證有一組最佳解經過剛好 $2$ 個 $x$
[27] $n \leq 5000$
[44] 無額外限制

剛看到還以為不可做，但後來想一想就發現他似乎可以用兩邊夾起來 DP，

C palindrome [1.5s, 1 GB]
給你 $n$ 個字串 $s_{i}$ ，總長度是 $m$ ，計算有多少數對 $(i, j)$ 使得 $s_{i} s_{j}$ 或 $s_{j} s_{i}$ 是回文。
$1 \leq n \leq 10^{5}, 1 \leq m \leq 2 \times 10^{6}$
[11] $n \leq 1000, m \leq 5000$
[26] $n \leq 50000, | s_{i} | \leq 300$
[63] 無額外限制

看到的第一想法就大概是 hash 之類的東西，可能可以大小分或者做其他的事之類的，

D fortress [9.0s, 1 GB]
給你 $n$ 個點，任三點不共線，問有多少凸多邊形。
$1 \leq n \leq 700$
[11] $n \leq 20$
[52] $n \leq 100$
[37] 無額外限制

剛看到這題的時候感覺不太可做，想要枚舉一些東西或觀察一些等價的條件都沒找到，所以就先放著。

開始決定寫 A $O (C \log C)$ 壓壓看可以過到哪裡，

00:43 A 52

只有過到值域是 $10^{6}$ 的 subtask，這時候其實狀況不是很好，到了 40 分鐘才刻出來，中間花很久的地方是我有點忘記怎麼排容所以弄式子弄很久，但這題是一題裸題所以我不應該在這裡花到太多時間，感覺頭腦剛清醒有點笨，連 for 迴圈都可以寫超久。

接下來去看了 B 發現可以定義 $d p_{i, j}$ 表示 $x$ 在 $i$ 、 $y$ 在 $j$ 而且下標到 $max (i, j)$ 的都解決了，這時候會發現轉移只有 $x_{i}$ 走到 $x_{max (i, j) + 1}$ 或 $y_{j}$ 走到 $x_{max (i, j) + 1}$ 的可能，所以可以在 $O (n^{2})$ 裡解決這個問題。過程中出了一個 bug 是最後算答案的時候跟怪東西取 min，整天出 bug 的笨方塊看來這場是要燒掉了。

01:12 B 56

C 一開始想要分大小 $\sqrt{m}$ 的 case 做，但後來我發現這樣要 $O (n \sqrt{m} \log m)$ 做完我覺得有點太危險，想了一段時間發現我根本不用判這樣，可以直接把所有東西 hash 之後丟進去一起做，但是等我做完之後，我先用 map 做了一次得到

02:25 C 11

這裡最大的問題是，這時候如果我跳題寫 D 很可能心態會穩很多，或是可以嘗試兩題交替想或回去壓 A，現在回去看 submission 紀錄覺得這時候想很久真的是整場的敗筆之一，

回到那筆 submission，後面的 subtask 都是 TLE 所以我就打算先把它壓成 vector + sort，這時候腦袋感覺真的很糟，推式子都可以推很久，實作也很燒雞，應該要想清楚一點再實作，

後來又花了很多時間壓下去，壓下去之後變成 WA，所以我就想加兩個 hash／__int128 的 hash，這時候真的完全不該花時間在上面做這題，應該要跳題的，二模的時候要記的提醒自己不要這樣做，一直弄一直弄弄到 03:22 都沒 AC，反而倒虧了一堆時間。而且這部分完全反映出我對 hash 不熟，用這樣的 hash 我選定的質數大概要 $O (m^{2})$ 量級才行，所以說我根本不應該嘗試這個解（何況他還帶 $\log$ ）

偷偷回去壓 A 沒壓成功，後來才決定跳題寫 D，一開始一直不知道要對什麼東西做事，但後來發現可以直接選定最下面右邊那個點，然後就可以極角排序之後用外積好好 DP 了，目前複雜度是 $O (n^{4})$ ，寫了一下就一發拿到分數，

03:49 D 63

這時候的策略回去做 C 才是對的，因為 A 我感覺我壓不太下去了，然後 B 也沒有更進一步的想法，

大概在剩 30 分鐘的時候， C 想到一個 hash + trie 的方法，可以 $O (n \log n + m)$ ，這樣應該可以快一點，甚至可以加更多 hash，接下來就刻到沒 debug 完，燒雞。

Result

						Sum
A	4	15	33	48		52
B	7	17	5	27	44	56
C	11	26	63			11
D	11	52	37			63
Score						182

Rk. 15, 距 2! 線 -40

出場

出場看到一堆人都會 AC，甚至有三個人破台，我大概就下去了吧，後來聽到 A 大家都是壓常壓下去的，只有我莫比烏斯反演太慢被卡， C 有人樸素 hash 就過，甚至有人可以不 TLE，或是帶根號 $\log$ 都能過（還很快），這場的 A、C 到底是什麼得= = 不過我自己策略也不太好，甚至對常數的觀念也很差，我也怪不得 TOI 題目耍怪，只能說是自己太笨。

檢討

我覺得我初選打得還算可以的主要原因是我當下心態有好好穩住，而且開場就能開始全力思考，這場心態的部分我沒有爆的很差，但中間花在 C 上面燒雞燒太久了，所以我覺得我要開始好好練習貫徹自己的策略，以及保持能夠好好思考的腦袋，希望二模可以好好把這個部分補起來，然後正常發揮隨緣看能不能進 2!。

各位選訓加油 ><