109 學年度普通型高級中等學校資訊學科能力競賽決賽 模擬賽 題解

題目連結

自然組：https://drive.google.com/file/d/1KAaPOYdzBuoC0hXdFwS5W0ZEItY61ktk/view
社會組：https://drive.google.com/file/d/1L-SLEkVPJryKrFpP6bHox1sq0o4rDC3k/view

pA 蘋果與橘子 (Apple_Orange)

• author+setter: yp

Subtask 1

if else

$O(1)$。

Subtask 2

$O(N^2)$ 枚舉。

Subtask 3

將輸入的蘋果和橘子都和

$2$ 取餘數，因此會分成四種人。兩個人可以平分若且唯若他們是同一種。假設四種人分別有

$x_1,\dots ,x_4$ 個人，則答案是

$\sum (\genfrac{}{}{0ex}{}{x_i}{2})$，

$O(N)$。

pA' 蘋果與橘子 EX (Apple_Orange_EX)

• author+setter: erd1

Subtask 1

題目等價於求以下不定方程的正整數解個數。

$$N=\sum _{i=0}^3(\genfrac{}{}{0ex}{}{x_i}{2})=\frac{1}{2}\sum _{i=0}^3{x_i}^2-x_i$$

可以做

$O(4N)$ 的 DP 得到解數。

Subtask 2

此不定方程等價於

$$8N+4=\sum _{i=0}^{3}4{x_i}^2-4x_i+1=\sum _{i=0}^3(2x_i-1{)}^2$$

這等價於求

$8N+4$ 寫成四個正奇數的和的方法數。注意到

$8N+4$如果是四個平方數的和，必定是四個偶數或四個奇數的平方(平方數模

$8$ 餘

$0$ 或

$1$ 或

$4$)。
故所有奇數解有

$r_4(8N+4)-r_4(2N+1)$ 個。因為每個變數都可以任意給定正負號，因此答案是

$\frac{1}{16}(r_4(8N+4)-r_4(2N+1))$ 。
根據雅可比四平方和定理，這會化簡成

$\sigma (2N+1)$。
枚舉因數可以

$O(\sqrt{N})$ 做完。

Subtask 3

用個好一點的因式分解方法，例如暴力枚舉到

$O(\sqrt[3]{N})$ 再用 Pollard's rho 做完，或是 GNFS。

Note

這題在 OEIS 有 QQ

---

pB 典獄長與斯芬克斯 (Sphinx)

• author: tmwilliam
• setter: double

Subtask 1

矩陣必定要形如

$\left[\begin{array}{cc}k& -k\\ -k& k\end{array}\right]$，用 if 判就好了，

$O(1)$。

Subtask 2

你可以將最後一行和最後一列以外的每個元素都 greedy 變成

$0$，然後判斷最後一行和最後一列是否全為

$0$ 即可。

Extra

事實上每一行和每一列的總和在操作不變，所以你只要判斷每一行每一列的和是不是都是

$0$ 即可。這只需要

$O(N)$ 的額外記憶體。

pB' 典獄長與斯芬克斯 EX (Sphinx_EX)

• author: toxicpie
• setter: double

首先注意到

1. $A$ 可以被消到
   $B$ 若且唯若
   $A$ 的每個直行的和等於
   $B$ 的每個直行的和且
   $A$ 的每個橫列的和等於
   $B$ 的每個橫列的和。
2. 一定可以把他消到剩第一行和第一列。

2. 告訴你 rank 至多是

$2$，而是否能做到

$rank=0$ 是原題，因此我們只需要判斷答案是否為

$1$。
若矩陣

$A$可以消到

$B$使得

$\mathrm{rank}B=1$，則

$$B_{ij}:B_{ik}=colsu{m}_B[j]:colsu{m}_B[k]=colsu{m}_A[j]:colsu{m}_A[k]$$

因此你知道

$B$ 的一整列兩兩元素之間的比。
因為第

$i$ 列的總和是

$rowsu{m}_B[i]=rowsu{m}_A[i]$，因此你可以算出

$B$ 的每個元素，亦即

$$B_{ij}=\frac{rowsum[i]\cdot colsum[j]}{S}$$

其中

$S$ 是每個元素的總和。
（當

$S=0$，則每一項的分子必須也要有

$0$，亦即

$\mathrm{\forall }i[rowsum[i]=0]$ 或

$\mathrm{\forall }i[colsum[i]=0]$。此時只要把所有東西都消到剩第一行或第一列即可。）
因此你只要檢查對於所有

$i,j$，

$rowsum[i]\cdot colsum[j]/S$ 是否是整數。如果是整數答案便為

$1$，否則答案為

$2$。

---

pC 橢圓曲線 (Elliptic)

• author+setter: erd1

Subtask 1 & 2

暴力枚舉

$O(p^2)$。

Subtask 3

如題敘

$O(p\log p)$。

Extra

預處理模逆元可以線性做到。給定

$x$ 時，會是一個

$y$ 的三次方程，因此要嘛至多

$3$ 個解，要嘛所有

$y$ 都是解。因此利用 bucket sort 也可以去掉最後排序的

$\log$。因此這可以做到

$O(p)$。

一些 random ramble

• 在題敘裡面已經很努力明示說要預處理模逆元了，沒有預處理時間大概會到兩倍。
  原本想卡掉的最後被波路擋下來了。
• $p=2$ 的情況在各種地方會爛掉，例如配方乘以二的時候。把它分出來變單獨一個 subtask 就是為了讓你們看到你們到底錯在哪。
• 本來
  $a=0$ 的情況是沒有標在題本上的，範測也刻意避開了這個情形，想說這是這題唯一難的地方，但是還是被波路擋掉了。
  $a=0,b\ne 0$ 時解是
  $z=-c{b}^{-1}$，
  $a=b=0,c\ne 0$ 時無解，
  $a=b=c=0$時
  $z$ 可以是任意餘數。
• 原本是出到
  $p\le {10}^6$ 的，因為這個數字好看很多，並要求預處理以外都不能帶
  $\log$。但是被黃克崴擋下來了才變這麼鬆的。
• 根據Extra的性質以上，答案最多有
  $3N$ 筆。有一筆測資有出滿。我記得他是什麼
  $x(x+1)(x-1)\equiv 0(\mathrm{mod}p)$，然後
  $p$ 是最大的那個質數。
• 記得看小教室，我寫了好久。 我已經在五門課上看到橢圓函數的出現了，他應該是將數學的各個領域（分析、代數、幾何）結合應用的例子裡面最初等的例子了吧。我覺得很酷所以就丟上來了。另一個目的是為了模擬通篇廢話的閱讀素養題。
• 我們當初投票決定好要出一題閱讀素養題以後，原本要出 Tonelli-Shanks，可是又覺得它過於無聊，於是我就跑去翻 Computational Arithmetic Geometry ，就翻到 Schoof 的論文了。

pC 橢圓曲線 EX (Elliptic_EX)

• author+setter: erd1

Subtask 1

暴力枚舉

$O(p)$。

Subtask 2

參見Schoof's algorithm。以下簡述做法。

$p=2$ 或

$3$ 的情況一樣要分開處理。以下假設

$p>3$。
注意到題目沒有保證輸入是橢圓曲線，因此我們要先檢查他的判別式。
若

$x^3+ax+b$ 的判別式

$\mathrm{\Delta }=4a^3+27b^2=0$，則他不是光滑的。

若

$a=b=0$，則

$y^2=x^3=(x^{-1}y{)}^6$。每個

$x^{-1}y\ne 0$都對到一組解，而

$x=y=0$也是一組解。總共

$p$ 組。

否則令

$t=-3b(2a{)}^{-1}$，式子會變成

$y^2=x^3-3t^{2}x+2t^3=(x+2t)(x-t{)}^2$。注意到每個

$k=y(x-t{)}^{-1}$ 都可以對到一組解，除非此時

$k=\pm \sqrt{3t}\Rightarrow x=t$。另外還有

$x=t,y=0$ 的那組。
因此若

$3t$ 模

$p$ 是平方數，則只有

$p-1$ 組解。否則是

$p+1$。

接著處理橢圓曲線的情形。眾所周知，橢圓曲線上的點形成一個群，而事實上這個群一定是兩個循環群的積（

$E\simeq C_l\times C_m$,

$m|l$）。根據 Hasse's theorem，若

$F_q$ 上的橢圓曲線有

$|E|$ 個點，則

$||E|-(q+1)|\le 2\sqrt{q}$。因此我們隨便抓一個曲線上的點

$P$，並對在那個區間中尋找滿足

$nP=0$ 的

$n$。如果只有一個

$n$ 我們就做完了。否則就挑另一個點再做一次。這是

$O(\sqrt{p}\log p)$ 的，因為每次在曲線上做加法都要一個

$\log (p)$。

但前提是，這個隨機是好的。但好巧不巧他是爛的。如果你跟著維基百科做會TLE。
例如

$y^2=x^3-x(\mathrm{mod}p)$ 的群在

$p=4n^2+1$ 的時候會同構於

$C_n\times C_n$。因此每個點在那個區間都會有至少兩個

$n$ 滿足

$nP=0$，因此你永遠戳不到一個好的點。這個例子是在 這篇論文 找到的。

但是考慮曲線

$E^{\prime }:y^2=x^3+g^{2}x+g^{3}b$，其中

$g$ 是任意一個非二次剩餘。這個曲線滿足

$|E|+|E^{\prime }|=2p+2$，而且你可以證明，如果

$p>229$，則

$E^{\prime }$ 或

$E^{\prime }$ 上至少有一個點是好的。因為他是兩個循環群的積，所以事實上那條曲線上大多數的點都是好的(因為

$n/\phi (n)=O(n^{\epsilon })$)。

因此，你就只要在兩個曲線上交互戳點即可。複雜度

$O(\sqrt{p}\log p)$。

以上沒有證明的東西應該都可以在 這篇論文 找到證明。

Subtask 3

在那個區間做大步小步，可以做到

$O(\sqrt[4]{p}\log p)$。

Extra

另外，維基百科上面還有多項式時間的做法，例如 SEA演算法 是

$O({\log }^{4}p)$ 的。但是我找得到的他的實作都是上千行的，所以應該不適合當題目（？
然後其實這題意外好寫，要是我早點發現他就會跑到自然組了（Ｘ

---

pD 和尚端湯上塔堂 (Tower)

• author+setter: baluteshih

Subtask 1

$O(N^2)$ 窮舉所有區間，每個區間

$O(N)$ 求最大值、最小值檢查。
共

$O(N^3)$

Subtask 2

$O(N)$ 窮舉區間的左界，嘗試讓右界不斷遞增並同時維護最大和最小值，共

$O(N^2)$。

Subtask 3

觀察到

$O(N^2)$ 的作法中，每個左界看到合法的最遠右界是非嚴格遞增的，因此可以使用雙指針維護，最大最小值則因為序列遞增能

$O(1)$ 得出。

$O(N)$。

Subtask 4

使用雙指針並配合 multiset 或線段樹等可維護區間極值的資料結構控制全距。

$O(N\log N)$

Extra

維護區間極值時可以使用兩個 deque 維護兩種單調隊列，如此一來可以將複雜度壓到

$O(N)$。
或用

$⟨O(N),O(1)⟩$ RMQ

pD' 和尚端湯上塔堂 EX (Tower_EX)

• author+setter: erd1

Subtask 1

對每個詢問做一次原題

$O(NQ)$。

Subtask 2

莫隊

$O(N\sqrt{Q}\log N+Q)$。可能有不帶

$\log$ 的做法可是我不在乎。

Subtask 3

你可以算出在

$i$ 結束的區間最長可以從哪裡開始並稱他為

$left[i]$。
則詢問

$l,r$ 的答案是

$$\frac{(l+r+2)(r-l+1)}{2}-\sum _{i=l}^{r}max(l,left[i])$$
將第二項拆解後可得

$$\frac{(l+r+2)(r-l+1)}{2}-\sum _{i=l}^r[left[i]>l]\cdot left[i]-\sum _{i=l}^r[left[i]\le l]\cdot l$$
後兩項皆各為一個二維偏序問題，可以離線用 BIT 等資料結構完成 （或吉如一）。總複雜度是

$O((N+Q)\log N)$。

---

pE & pE' 量子糾纏 (Entanglement)

• author+setter: icube

Subtask 1

不失一般性假設

$N\le M$：
如果

$N=1$，輸出

$1$。
如果

$N=2$，由於小 E 不停在兩個地點間往返，小 C 無法回頭，因此答案為

$M$。
如果

$N\ge 3$，輸出

$\mathtt{\text{INF}}$。

Subtask 2

和前一子題類似，但是當

$N=2$，考慮

$H$ 是否有環。
如果

$H$ 有環，輸出

$\mathtt{\text{INF}}$。
否則輸出

$H$ 上的最遠點對距離（樹直徑）。

Subtask 3

假設

$G=(V_G,E_G),H=(V_H,E_H)$。
構造新圖

$Z=(V,E)$，其中

$V=\{(x,y)\mid 1\le x\le N,1\le y\le M,g_x=h_y\}$ 且

$E=\{\{(x_1,y_1),(x_2,y_2)\}\mid (x_1,y_1)\in V,(x_2,y_2)\in V,\{x_1,x_2\}\in E_G,\{y_1,y_2\}\in E_H\}$。

$O((NM{)}^2)$ 枚舉

$x_1,y_1,x_2,y_2$ 建圖。
若

$Z$ 有環，答案為

$\mathtt{\text{INF}}$。
否則對於每個連通塊計算樹直徑，輸出最大值。
樹直徑的計算可以使用平方時間的方法，不影響整體時間複雜度。

Subtask 4

延續 Subtask 3。
對於所有

$1\le c,d\le 2000$，紀錄

$G$ 裡有哪些

$\{u,v\}$ 的邊滿足

$g_u=c,g_v=d$。
枚舉

$H$ 的邊

$\{u,v\}$ 時直接查詢

$h_u,h_v$ 對應的邊，建圖時間化為

$O(N^2+M^2+|E|)$。
雖然

$|E|$ 的量級是

$O((NM{)}^2)$，但是當

$|E|\ge |V|$ 時必定有環，因此最終時間複雜度降為

$O(N^2+M^2+NM)$。
此子題的樹直徑須以線性時間計算，由於相關資料容易取得，於此不加贅述。

方便起見，以下假設

$N=M$。
Note 1: 此題建圖有

$O(N^3)$ 的做法，基本上無法通過測試。
Note 2: 假設

$\omega$-bit integer 的四則運算、位元運算和比較等等都是

$O(1)$，建圖有

$O(\frac{N^3}{\omega }+N^2\omega )$ 的做法，也能通過此題（提示： bitset）。

---

pF 鬧鐘設置 (Alarm_clock)

• author+setter: HNO2

Subtask 1

答案是

$\sum _{i=2K+2}^N{a}_i+(2K+1)a_1$。
注意到一定要有一個鬧鐘設定響的時間是這個序列的最小值(也就是

$a_1$)， 而且很顯然這個鬧鐘只能由第

$K+1$ 個人設定。因此，前

$2K+1$ 個人起來的時間點只能是

$a_1$，便證明了上面那個答案的上界。
欲證明這個答案是下界也很簡單: 讓第

$K+1$ 個人設置鬧鐘在

$a_1$ 響，再對於

$K+2\le i\le N-K$，設置一個鬧鐘在

$a_{i+K}$ 響起即可。

Subtask 2

因為每個人來的時間點不是

$1$ 就是

$2$，因此相當於最小化

$a_i=2$ 但是起來時間點是

$1$ 的人。令序列

$b$ 為每個人最後起來的時間點，則不難發現: 在序列

$b$ 中，

$b_i=1$ 的連續段長度至少要是

$2K+1$。這是因為，如果有一段連續段長度不足

$2K+1$，則沒有地方可以擺設鬧鐘。
則這個問題可以轉換為: 使用一些長度為

$2K+1$ 的區間覆蓋

$a$ ，且把所有

$1$ 都覆蓋的情況下，最少能覆蓋幾個

$2$。這個問題可以使用一個簡單的DP解決: 令

$d{p}_i$ 代表前

$i$ 個數字所有

$1$ 都覆蓋的情況下，最少能蓋到多少個

$2$。轉移如下:

$$\{\begin{array}{ll}d{p}_i=min(d{p}_{i-1},\underset{j\le i-2K-1}{min}(d{p}_j+sum[j+1,i])& \text{if}{a}_i=2\\ d{p}_i=\underset{j\le i-2K-1}{min}(d{p}_j+sum[j+1,i])& \text{if}{a}_i=1\end{array}$$

其中

$sum[l,r]$ 代表

$[l,r]$ 區間中

$2$ 的個數。

Subtask 3

考慮

$dp$ 狀態

$dp[L][R][i]$ 代表：把區間

$[L,R]$ 設好，並且指使用前

$i$ 小的數字的情況下，每個人可以睡覺的最大時間總和。
general 的轉移：

$dp[L][R][i]=dp[L][R][i-1]$ 。
此外，如果

$a[L],a[R]$ 比第

$i$ 個數字還大的話，還可以考慮轉移

$dp[L][R][i]=dp[L+1][R][i]+v[i]$，

$a[R]$ 的轉移類似。
除此之外，還要考慮轉移

$dp[L][R][i]=max(dp[L][i^{\prime }][i]+dp[i^{\prime }+1][R][i])$ 。
複雜度就是

$O(n^4)$
這是一個測題者寫出來很奇怪的解ww

Subtask 4

有多種作法，以下只介紹其中一種。
令

$i$ 為序列

$a$ 中最小值的出現位置。則可以發現，至少要有一個鬧鐘覆蓋位置

$i$，設置時間在

$a_i$ 時間點響。假設這個鬧鐘設在位置

$j$ ，則由於每個鬧鐘影響範圍都一樣，且這個鬧鐘響起的時間是最早的，

$j$ 左邊和右邊的鬧鐘不會互相干擾。
經由以上觀察，可以得到以下 DP 解: 令

$d{p}_l,r$ 代表在位置

$l,r$ 各設置一個鬧鐘的情況下，

$[l,r]$ 這個區間的人最大的睡眠時間總和。若

$r-l+1\le 2K+2$ 則

$d{p}_{l,r}$ 為

$0$。否則，令

$i$ 為區間

$[l+1,r-1]$ 最小值發生點，轉移為

$d{p}_{l,r}=\underset{max(l+1,i-K)\le j\le min(r-1,i+K)}{max}(d{p}_{l,j}+d{p}_{j,r}+a_i\cdot (min(r-K-1,j+K)-max(l+K+1,j-K)))$。也就是算出左右兩邊的DP值後再計算這個鬧鐘可以讓多少人起來。時間複雜度

$O(N^{2}K)$。

pF' 鬧鐘設置 EX (Alarm_clock_EX)

• author+setter: HNO2

Subtask5

前面 4 個 Subtask 跟自然組一樣就不贅述了。
跳脫一下前面區間 DP 的想法。在 Subtask 2 中提到，在序列

$b$ 中，

$b_i=1$ 的連續段長度至少要是

$2K+1$ 。在 General 的情況也有一個很類似的結論: 如果在序列

$b$ 區間

$[l,r]$ 數字都一樣，且滿足

$b_l<b_{l-1},b_r<b_{r+1}$，則這個區間的長度至少為

$2K+1$。若稱這種區間為一個「長區間」，則會發現任意兩個長區間

$b$ 必為先遞增後遞減。

這樣子整個 DP 的雛型就出來了: 令

$d{p}_{i,j,k}$ 代表序列

$b$ 中，最後一個數字一樣的區間結尾在

$i$ ，他的值是

$j$ (需將輸入的數字先離散化)。

$k$ 代表狀態:

$k=0$ 代表前一個區間的數字比他大，

$k=1$ 代表比他小，

$k=2$ 代表他處在一個長區間的結尾。

轉移的話基本上只要注意「任意兩個長區間

$b$ 必為先遞增後遞減」，也就是除了

$k=1$ 不能轉

$k=0$ 以外其他都可以轉。轉移的時候可以使用前後綴

$max$ 加速轉移，詳細轉移有些繁瑣就不附上來了。

最後答案是

$i=n,k=0\vee k=2$ 的最大值。總時間複雜度是

$O(N^2)$ 。

Extra

tmw 宣稱這題可以做到

$O(NK)$ 和

$O(N\log N)$，需要用到 CHT 線段樹等工具。只是因為我不會(X)就沒出進社會組了。

---

pG 白銀柵欄 (Fence)

• author+setter: toxicpie

因為木製柵欄不用錢，所以我們可以直接讓他超長。以下用

$R(w,\theta )$ 來表示白銀柵欄長度為

$2w$，木製柵欄超長，且矩形重心的極角為

$\theta$ 的矩形。注意到蓋出

$R(w,\theta )$ 的花費是

$4w$。

Subtask 1

可以發現若

$R(w,\theta )$ 同時包含

$(1,0)$ 和

$(-1,0)$，那

$\theta$ 一定是

${90}^{\circ }$ 或

${270}^{\circ }$。如果選擇

$\theta ={90}^{\circ }$，那麼該矩形會蓋住所有

$y\ge 0$ 且

$|x|\le w$ 的點。因此答案是所有樹的

$x$ 座標絕對值中的最大者

$\times 4$。

時間複雜度：

$O(n)$

Subtask 2+3+4

做法 1

固定

$w$ 的值，考慮

$R(w,{\theta }_0)$ 能蓋住

$(x,y)$ 時

${\theta }_0$ 的條件：

• 若
  $w\ge \sqrt{x^2+y^2}$，那
  $(x,y)$ 只要和矩形在白銀柵欄的同側就好，因此
  $-\frac{\pi }{2}\le {\theta }_0-\mathrm{atan}2(y,x)\le \frac{\pi }{2}$。
• 若
  $w<\sqrt{x^2+y^2}$，那麼除了前一項的條件，還要再滿足
  $(0,0)$ 和
  $(x,y)$ 都在木製柵欄的同側。這等價於
  $-\frac{\pi }{2}+\mathrm{acos}(\frac{w}{\sqrt{x^2+y^2}})\le {\theta }_0-\mathrm{atan}2(y,x)\le \frac{\pi }{2}-\mathrm{acos}(\frac{w}{\sqrt{x^2+y^2}})$。

也就是說，

${\theta }_0$ 的可能值一定是一個區間 (可以在腦中想像旋轉那個矩形，應該會很直觀 (?))。如果給定一個

$w$，那寬度

$w$ 的矩形能蓋住所有點若且唯若每棵樹對應的

${\theta }_0$ 區間的交集非空，而這可以在

$O(n)$ 的時間內判斷。

因此，我們可以對答案二分搜。時間複雜度：

$O(n\log (C))$，其中

$C={ϵ}^{-1}$ 且

$ϵ$ 是允許的誤差。

做法 2

做法 2 正確性的證明可能會需要 EX 版題解的某些 lemma ，但是在賽中應該不難猜出並相信結論是對的 (?)，並且實作拿到 AC。

假設不是所有點都在

$x$ 軸上。令

$R(w_m,{\theta }_m)$ 是一個最佳解，且

${\theta }_l,{\theta }_r$ 分別是所有可行解

$R(w,\theta )$ 中，

$\theta$ 的最小和最大值。可以想像

$\theta$ 連續的從

${\theta }_l$ 轉到

${\theta }_r$ 時都會有可行解，且對應的最小寬度在

$[{\theta }_l,{\theta }_m]$ 會遞減，而在

$[{\theta }_m,{\theta }_r]$ 會遞增。

因此，我們可以對

$\theta$ 做三分搜來找矩形寬度的最小值。時間複雜度：

$O(n\log (C))$，其中

$C={ϵ}^{-1}$ 且

$ϵ$ 是允許的誤差。

注意： 如果你寫了這兩種做法且常數很大 (像是使用了 long double 或是搜太多次)，那 Subtask 4 很有可能不會過。

pG' 白銀柵欄 EX (Fence_EX)

• author+setter: toxicpie

小知識：這題的浮點數版本才是原本的 pG。

Subtask 1

注意到 Subtask 1 等價於柵欄要圍住所有樹。觀察到有解若且唯若存在一條過原點的直線，使得所有樹都在他的同一側，所以極角排序後就可以簡單判斷有沒有解。

假設有解，且最佳解長這樣：

那麼，他一定會滿足這些條件：

1. $\overline{AD}\cup \overline{BC}$ 至少包含一棵樹。否則，我們可以縮小他的寬度，而矩形依然會包住所有樹，如下圖：

2. $\overline{OA}\cup \overline{AD}$ 至少包含一棵樹。否則，我們可以將矩形順時針旋轉並將寬度縮小，而依然會包住所有樹，如下圖：

3. $\overline{OB}\cup \overline{BC}$ 至少包含一棵樹，同 2.。

簡單的處理一下這些條件後，可以知道以下三點至少有一點會成立：

1. $\overline{OA}$ 上有一棵樹。
2. $\overline{OB}$ 上有一棵樹。
3. $\overline{AD}$ 上有一棵樹，且
   $\overline{BC}$ 上有一棵樹。

因此可以分 case 找答案，取其中的最小值。

Case 1

若

$\overline{OA}$ 上有一棵樹，則答案為所有點的向量投影到

$\overline{AB}$ 上長度的最小值

$\times 4$，即

$$\underset{1\le i\le n}{max}\frac{|\overrightarrow{OP}\cdot (x_i,y_i)|}{\left|\overline{OP}\right|}\times 4$$
，其中

$P$ 是

$\overline{OA}$ 上的一棵樹。

而

$P$ 最直觀的找法，就是求原點到所有樹凸包的右切線。

Case 2

同上，答案為

$$\underset{1\le i\le n}{max}\frac{|\overrightarrow{OP}\cdot (x_i,y_i)|}{\left|\overline{OP}\right|}\times 4$$
，其中

$P$ 是原點到所有樹凸包的左切線 (他會在

$\overline{OB}$ 上)。

Case 3

(這是實作較簡單的做法，其他做法如旋轉卡尺等也可以用。)

考慮所有樹對原點做對稱之後複製一份，如下圖：

可以發現，兩條木製柵欄分別為原本的樹和對稱後的樹的凸包切線，而答案即為原點到切線距離的 4 倍。不過，在更新答案之前，我們需要先檢查是否所有樹都在

$\overline{AB}$ 的同一側。

時間複雜度：

• 極角排序
  $O(n\log (n))$
• Case 1
  $O(n)$
• Case 2
  $O(n)$
• Case 3 凸包
  $+O(n)=O(n\log (n))$

總共為

$O(n\log (n))$ 。

Subtask 2

其實作法同 Subtask 3 ，只是實作上會簡單不少。

Subtask 3

我們需要找到一棵樹，使得砍掉他後，包住剩下的樹所需的矩形寬度會最小。有兩種情況：

1. 原本沒有解，但砍掉這棵樹後就有解了。發現到這種樹最多只有 4 個，而且可以通過極角排序簡單找出。一一嘗試砍掉他們並呼叫 Subtask 1 的解即可得到答案。
2. 原本的答案因為砍掉一棵樹後變小了。

由 subtask 1 的解法可以發現，砍掉一棵樹之後必須滿足以下其中一種，答案才有可能變小。

1. $\overline{AD}\cup \overline{BC}$ 上沒有樹。
2. $\overline{OA}\cup \overline{AD}$ 上沒有樹。
3. $\overline{OB}\cup \overline{BC}$ 上沒有樹。

再利用一次上面的性質，可以知道砍樹前的最佳解一定會是以下 case 的一種。

1. $\overline{AD}\cup \overline{BC}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。
2. $\overline{OA}\cup \overline{AD}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。
3. $\overline{OB}\cup \overline{BC}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。

總時間複雜度一樣是

$O(n\log (n))$。

Remark: 為何所有輸出的

$q$ 都不會是

${10}^9+7$ 的倍數呢？可以發現，以上所有 case 中算出的答案分母都是某兩個格子點之間的距離，也就是說，

$q=x^2+y^2$，其中

$x,y$ 是整數。由於

$-1$ 不是

${10}^9+7$ 的二次剩餘，

$x^2+y^2\equiv 0(\mathrm{mod}{10}^9+7)$ 只有在

$x\equiv y\equiv 0(\mathrm{mod}{10}^9+7)$ 才會滿足，而這在測資中不可能發生。

---

pH & pH' 螞蟻捷運 (Ant_MRT)

• author+setter: tmwilliam

Subtask 1

Floyd-Warshall + DP。
可以先對每個點對計算最小花費，之後再使用Floyd-Warshall。複雜度

$O(N^3)$ 但常數很小。

Subtask 2

建圖

Subtask 3

對於每一個節點

$u$，計算

$e_{i,j}=$用價格

$2^i+j$最高可以達到的節點（

$0\le i<17,-6<j<6$）。之後再用倍增算出最少需要多少花費才能抵達節點

$1$ 。

$O(((N+Q)C^2+M)\log N)$

Subtask 4

對於每一個節點

$u$，計算

$e_i=$用價格

$2^i$最高可以達到的節點（

$0\le i<17$）。
對於每一個詢問

$(u_i,v_i)$，一個詢問

$(u_i,v_i)$可以分成

$(u_i,w_i)$和

$(v_i,w_i)$。我們可以計算最少要從

$u$和

$v$到LCA的價格為

$c_u$和

$c_v$。如果有路連通

$c_u-1$和

$c_v-1$，答案就是

$c_u+c_v-1$。如果沒有，答案就是

$c_u+c_v$。找路可以用2D區間和，或者可以可以在樹壓平用BIT維護:

• 每個節點
  $v$ 在樹壓平以後可以對應一個區間
  $[l_v,r_v]$ 。
• 對樹做一次DFS，對於每條路
  $a_i,b_i$ ，在DFS到
  $a_i$ 時，在另一端
  $b_i$ 加1。
• 對於每個詢問
  $(u,v)$ ，DFS到
  $u$ 時紀錄
  $[l_v,r_v]$ 的總和。 在
  $u$ 的所有子樹DFS完以後，再詢問一次
  $[l_v,r_v]$ 。如果總和不一樣代表有路從
  $u$ 到
  $v$ 。

$O((N+Q+M)\log N)$

Subtask 5

結合Subtask4和Subtask5。先對於每一個節點

$u$，計算

$e_{i,j}=$用價格

$2^i+j$最高可以達到的節點（

$0\le i<17,-6<j<6$）。之後可以發現對於每個點對

$u,v$ ，計算最少要從

$u$和

$v$到LCA的價格為

$c_u$和

$c_v$。之後需要找是否有權重

$k$ 的路連通

$u-k$ 與

$v-k$ (

$1\le k\le 5$)。找路一樣可以使用之前介紹的方法。

Subtask 6

可以把三個數字塞進一個數字。

$O((N{C}^2+\frac{Q{C}^3}{3}+M)\log N)$

Note

這題的 Subtask 4 在 CF 上有，出出來以後就發現撞題了 QQ