[TOI] 2022 1 模

賽前

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

賽中

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

• A diophantus [5.0s, 1 GB]
  給你 $n$ 個數字，問有多少組有序的 $(A,B,C)$ 滿足 $Ax + By = 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,\cdots,x_n,y_n,\cdots,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_is_j$ 或 $s_js_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

$\newline$

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

接下來去看了 B 發現可以定義 $dp_{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

$\newline$

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

02:25 C 11

$\newline$

這裡最大的問題是，這時候如果我跳題寫 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

$\newline$

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

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

Result

Rk. 15, 距 2! 線 -40

出場

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

檢討

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

各位選訓加油 ><