owned this note changed 2 years ago
Published Linked with GitHub

AA 競程 2023 TOI 模擬賽 決賽


  • 賽前難易度猜測
    \(E ≈ A < C < D < B\)
  • 實際每題 AC 人數(包含同步賽)

A:12 人
B:0 人
C:16 人
D:6 人
E:12 人


E. 這是 TOI 會考的普通題嗎?

首殺:Fysty (47 mins)


子題 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 的分數,大概是你陣列開太小了。

A. TOI 也會出搜索題?

首殺:hank55663 (16 mins)


子題 1

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

子題 2

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

方法一:

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

方法二:

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

C. TOI 也會出 IMO 題?

首殺:PixelCat (44 mins)



子題 1

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

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

子題 2


子題 3

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

D. TOI 也會出構造題?

首殺:8e7 (81 mins)


子題 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...
..........#..    .........##..    .........##..
.........#.#.    .........###.    .........###.

B. TOI 也會出字串題?

首殺:可惜此題沒人 AC :(
~~賽後 alvingogo 把賽中的 code 做常數優化後就 AC 了(但時限是標程 3 倍,應該不算卡常唷) ~~


子題 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)\) 時能做到更好的時間複雜度
Select a repo