[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

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!。

各位選訓加油 ><