AA 競程 2023 TOI 模擬賽 決賽

子題 1

• n 對情侶坐成一圈的方法總共有：\(2 \times 9! \times 2^9\)，直接枚舉所有方案的話，大概會超時。

• 但是每對情侶若確定坐哪兩個位置時，我們可以貪心的決定誰左誰右會比較好。
• 所以枚舉的情況剩下 \(9!\) 種。

子題 2 & 3

• 不妨假設情侶坐的位置是 \(2i-1\) 和 \(2i\)。
• 把每個人當圖論上的點，情侶間連一條邊，\(a_{2i-1}\) 和 \(a_{2i}\) 也連一條邊
• 可發現此圖是由很多環組成，且長度為 2 的環上兩人都可獲得自己想要的餐具。而其餘長度為 2k 的環，至多能有 k 個人坐在自己喜歡的餐具前，並且方案有兩種。
• 每個環各自判斷哪種方案字典序最小，即可 \(O(N)\) 解出此題。

• 若只拿到子題 2 的分數，大概是你陣列開太小了。

子題 1

• 為了迎合題目敘述，雖然不知道怎麼估時間複雜度，但出題者有測試過，寫了個暴力搜索枚舉所有合法的可能 cycle 就通過所有測試資料了

子題 2

• 先把原有的 '#' 上下左右都標記為不能走

方法一：

• 接著找到兩個留下來的 path 頭尾端，用 BFS 找他們間合法路徑的最短路，一定滿足環自身沒有在不該相鄰的地方相鄰

方法二：

• 接著找到兩個留下來的 path 頭尾兩端，從其中一端使用 DFS，過程中只走不會和兩步以前走過的地方相鄰的格子，並且不要走已拜訪過的格子，有辦法證明若存在解，最終一定能走到另外一端

子題 1

• 首先呢，\((x1,y1),(x2,y2),(x3,y3)\) 三個點構成的三角形的重心為 \((\frac{x1+x2+x3}{3},\frac{y1+y2+y3}{3})\)

• 算出重心後套範例測試資料的海龍公式即可 AC 此子題

子題 2

• 會算重心座標的話，可直接套用 CSES2191 Polygon Area 的解法解此子題
• 算簡單多邊形的面積可利用 Shoelace formula(中文似乎被稱作鞋帶定理)

子題 3

• 請參考題目附圖，可以證明 \(\triangle p_1C_1C_2\) 面積是 \(\triangle p_1m_2m_3\) 的面積的 \(\frac{4}{9}\)
• 所以每個詢問其實都是 \(p_i\) 以及沒和 \(p_i\) 相鄰的邊的中點所形成的凸多邊形面積的 \(\frac{4}{9}\)，可發現在計算鞋帶定理時，共通的項非常多，不用重新計算。
• 時間複雜度為 \(O(n)\)

子題 1

• 觀察一：每一列黑格是連續的，只需維護左右界
• 觀察二：每一列的黑格左界是先遞減在遞增，右界是先遞增再遞減

只要暴力枚舉遞迴枚舉所有可能情況可以，有辦法計算出在 \(\max(N,M) \le 8\) 的情況下，滿足上頁兩個觀察的不同黑格塗色方式並不多。

子題 2

• 使用 DP，令 \(dp[i][l][r][dec][inc]\) 代表現在考慮到第 \(i\) 列，且第 \(i\) 列黑格左界是 \(l\)，右界是 \(r\)，\(dec\) 是個布林值代表黑格左界是否正在遞減，\(inc\) 是個布林值代表黑格右界是否在遞增。
• 如此一來就有個 \(O(N^5)\) 的 dp 作法

子題 3

• 子題 2 的轉移使用噁心的二維 RMQ 優化大概能變成 \(O(n^3 log n)\)
• 歡迎大家提供優美的作法

子題 4

• 引理：假設 \(i < j < k\) 且 row \(i,k\) 都至少有一個黑格，定義 \(row\_ma_i\) 為第 \(i\) row 的黑格最大的 column 座標
  那麼 \(row\_ma_j \ge \min(row\_ma_i, row\_ma_k)\)

• 根據此引理可以 \(O(n)\) 找出每個 row 的最大 coumn 座標至少有多大，最小的 column 座標至少有多小也能用類似方法求出

• 例如左邊的測試資料，考慮完上頁的情況後，我們會得到右邊的 # 是一定要有黑格的位置

11 13
#............    #............
..#..........    .##..........
.#...........    .##..........
.............    .............
.....#.......    ...###.......
...#..#......    ...####......
.....#.......    .....##......
.............    .............
.............    .............
..........#..    .........##..
.........#.#.    .........###.

• 可能會有數個連通塊，但每個連通塊的 x 和 y 座標必單調遞增或遞減
• 不妨假設 這些連通塊座標 x 和 y 是同時遞增，並把連通塊編號為 \(1 \sim k\)，考慮每個連通塊的最小包矩形，每個編號 \(2 \sim k\) 的連通塊最小包矩形左上角一定是黑格；每個編號 \(1 \sim k-1\) 的連通塊最小包矩形右下角一定是黑格
• 把編號 \(i\) 的連通塊 右下角和編號 \(i+1\) 的連通塊左上角以任意最短路連接，就會是最佳解

• 第三張圖的 X 展示一種可能的連接所有連通塊的方式

11 13
#............    #............    #............
..#..........    .##..........    X##..........
.#...........    .##..........    .##..........
.............    .............    ..XX.........
.....#.......    ...###.......    ...###.......
...#..#......    ...####......    ...####......
.....#.......    .....##......    .....##XXX...
.............    .............    .........X...
.............    .............    .........X...
..........#..    .........##..    .........##..
.........#.#.    .........###.    .........###.

子題 1

• 暴力枚舉每個詢問的所有路徑求最小的字串即可通過

子題 2 & 3

此題在考驗大家用正確的順序 DP

要搞清楚一件事：

• 令 \(s1, s2\) 是字串，\(c\) 是字元
• \(s1\) 字典序 < \(s2\) 不代表 \(s1+c\) < \(s2+c\)
• 例如：\(s1=\) a，\(s2=\)aa，\(c=\)b

• 引理：點 x 到點 y 的字典序最小路徑一定是 x 走恰一條邊至某個點 i，再從點 i 走字典序最小路至點 y
  • 請不要覺得這件事很顯然， 若把它改成：「點 x 到點 y 的字典序最小路徑一定是 x 走字典序最小路到某個點 i，再從點 i 走恰一條邊至 y」就是錯的

• dp[i][j] 代表點 i 至點 j 路徑上字典序最小字串，根據引裡可列出轉移式：
  \(dp[i][j] = \min\limits_{k=i+1}^j{s_i[k-j-1]+dp[k][j]}\)
• 此作法時間複雜度為 \(O(N^4)\)

子題 4

• 對於所有的詢問，\(ed_i\) 值相同 (令其為 \(t\)) 的答案可用 \(O(N^2)\) 的時間算出
• 只要用 \(x\) 從大到小的順序依序計算出 \(x\) 至 \(t\) 的字典序最小最短路，此最短路不需要儲存整個字串，只需要儲存離開 \(x\) 第一個走到的點是哪個點即可。

• 「只需要儲存離開 \(x\) 第一個走到的點」是因為我們可以維護一個 list 按照字典序大小排列所有編號大於 \(x\) 的點到 \(t\) 的字典序最小路。
• 要比較第一個走到的點是誰比較好，只要比較第一個字母以及走到的點在 list 裡的順序即可。
• 可用 \(O(N)\) 時間插入新的點到 list 裡。

• 若用一些高級的平衡樹資料結構，邊數非 \(O(N^2)\) 時能做到更好的時間複雜度