這篇文是在 12/12 寫的，但因為隔天還有社會組所以會晚一點發 (?)。

不知不覺離全國賽只剩一個星期了，很幸運地我第一年比全國賽（去年）開始就有模擬賽，今年也辛苦工作人員了 > < 。

題本．計分板．程式碼

題目

pA 蘋果與橘子

100/100

給兩個長度 $N$ 的數列 $a$、$b$，求有幾對 $(i,j)$ 滿足 $1 \leq i < j \leq N$ 且 $a_i+a_j$ 與 $b_i+b_j$ 都是偶數。

因為加起來是偶數所以奇偶性要一樣，就數每一種奇偶性組合有幾個就可以算了。

pB 典獄長與斯芬克斯

100/100

給一個 $N \times M$ 矩陣 $A$，你可以做任意次這兩種操作：

• 選一個 $2 \times 2$ 的子矩陣，將左上和右下角減 1、左下和右上角加 1。
• 選一個 $2 \times 2$ 的子矩陣，將右上和左下角減 1、左上和右下角加 1。

求有沒有辦法讓整個矩陣的元素都是 0。

我看完題目就想到因為做完操作後，總和不會改變，所以所有元素和必須是 0，又看到備註寫「你能想到空間複雜度不到 $O(NM)$ 的作法嗎」就覺得應該八九不離十了，結果交上去後 WA，想了一下發現同一行和列的和也不會變，所以必須同一行跟列的和都是 0，而且這樣肯定能構出解，從左上角開始讓格子變 0 就好了。

pC 橢圓曲線

100/100

給 $A$、$B$、$C$、$D$、$E$、$F$、$G$、$H$、$I$ 和質數 $p$，求所有的 $0 \leq x, y < p$ 滿足： $Ax^3+Bx^2y+Cxy^2+Dy^3+Ex^2+Fxy+Gy^2+Hx+Iy \equiv 0 \pmod{p}$

題目給的資訊：當 $y = 0$ 時要特判。$y$ 不是 0 的話，可以令 $x \equiv wz^{-1} \pmod{p}$、$y \equiv z^{-1} \pmod{p}$，式子可以整理成 $(Hw+I)z^2 + (Ew^2+Fw+G)z + (Aw^3+Bw^2+Cw+D) \equiv 0 \pmod{p}$ 枚舉 $w$ 就可以得到一個二次方程 $az^2+bz+c \equiv 0 \pmod{p}$，配方後會變成 $(2az+b)^2 \equiv b^2-4ac \pmod{p}$。 當 $a=0$、$a=b=0$、$a=b=c=0$ 時要特判，剩下的狀況要開根號，開根號可以預處理。

就是一個數學閱讀測驗，我去年全國賽和今年入營考的數學閱讀測驗都燒雞，這次終於過了，好開心。

就是照著題目說的做就可以了，一些特殊狀況：

• 特判 $y=0$ ：直接枚舉 $x$，然後檢查。
• $a=0$、$b,c \neq 0$：一次方程式，可以直接移項。
• $a=b=0$、$c \neq 0$：顯然不會有解。
• $a=b=c=0$：所有 $0 \leq z < p$ 都可以。

我交上去後 WA 第一個子題，這個子題是 $p=2$，我想說可能 $p=2$ 的時候模逆元會壞掉之類的，特判就過了，但第三個子題 TLE，把模逆元預處理後過了。

pD 和尚端湯上塔堂

100/100

給數字 $N$ 和 $K$，以及一個長度 $N$ 的數列 $h$，求全距 $\leq K$ 的區間數量。

我以前聽到的版本都是和尚端湯上塔沒有堂 (?)。

如果固定區間左界的話，右界往越右邊移全距會越大，所以枚舉左界再二分搜右界就好。我用 sparse table 算全距，聽說有人用線段樹然後 TLE。

pE 量子糾纏

100/100，首殺

給兩張圖 $G$ 和 $H$，分別有 $N$ 和 $M$ 個點，$G$ 上的點 $v$ 記作 $G_v$、$H$ 上的點 $v$ 記作 $H_v$，每個點都有各自的特徵，記作 $f(v)$。 求最大的 $k$ 使得存在 $G$ 上的可重複點路徑 $v_G(1),v_G(2),...,v_G(k)$ 和 $H$ 上的可重複點路徑 $v_H(1),v_H(2),...,v_H(k)$ 滿足：

• $\forall 1 \leq i \leq k,\ f(v_G(i))=f(v_H(i))$。
• $\forall 1 < i < k,\ v_G(i-1) \neq v_G(i+1) \lor v_H(i-1) \neq v_H(i+1)$，也就是不能同時往上一步的地方走。

先做一張有 $N \times M$ 個點的圖 $T$，上面的點記作 $T_{u,v}$（$1 \leq u \leq N$、$1 \leq v \leq M$），如果有 $G_a$、$G_b$、$H_c$、$H_d$ 滿足 $G_a=H_c$、$G_b=H_d$，那麼就在 $T_{a,c}$ 和 $T_{b,d}$ 間連一條無向邊（這個關係會是雙向的，連一條就好）。

然後問題會變成在 $T$ 上找一條不往回走的最長路徑，如果有環就可以一直繞圈圈，所以這樣答案會是無限大。沒有環就是找森林裡的最長樹直徑。

在建圖的時候可能會有 $O(N^2M^2)$ 條邊，如果邊數 $> NM - 1$ 就可以直接停止。

pF 鬧鐘設置

100/100

給數字 $N$、$K$ 和一個長度 $N$ 的數列 $a$，你可以在每個位置 $K < i \leq N - K$ 都設置任意個鬧鐘，並決定每個鬧鐘什麼時候要響，每個鬧鐘的影響範圍是 $[i-K,i+K]$，某一個位置 $j$ 的起床時間是影響到他的所有鬧鐘中，最早響的時間，而這個時間必須 $\leq a_j$。求最大的起床時間總和。

首先就是如果 $a$ 裡最小的 $a_i$，這樣就一定要有一個包含 $i$ 的長 $2K+1$ 的區間，起床時間會是 $a_i$，接著會被砍成兩半起床時間還不確定的部分，那兩半可以分開做事，因為中間已經確定的長度是 $2K+1$，能影響到其中一半的鬧鐘一定影響不到另一半。

看到 $N \leq 500$ 就想到應該是某種三維 DP，$dp[l][r]=$ $[l,r]$ 範圍內的答案，轉移就是找到區間裡最小那個後枚舉鬧鐘的位置，把區間切兩半。

pG 白銀柵欄

100/100

給 $N$ 個點，所有點的 $y$ 座標都是非負的，你可以決定一個角度 $\theta$，然後將所有點以原點為圓心，旋轉 $\theta$，旋轉後必須滿足所有點的 $y$ 座標都仍是非負的，求最小的「最大 $x$ 座標絕對值」。

題目敘述比較複雜一點，經過一些想像 (?) 後就可以變成這樣。

我看到這題本來以為是旋轉卡尺，然後發現我不會平行線距離公式（我知道數學課有教），然後自己導了一個用直角三角形算的算法 (?)，應該好好把高一上數學學好的 QQ，高一下和高二上太友善了，高一上有一些超級難的東西，直線與圓超難。

不過後來發現跟旋轉卡尺無關，把題目轉化成上面那樣後，可以很直覺地發現 $\theta$ 對答案是一個單峰函數，所以可以三分搜。決定 $\theta$ 後，把每個點的座標轉成極座標旋轉後再轉回來就行了（沒錯我不會旋轉矩陣）。傳上去後第一個子題過了，第二個 WA，看到只錯幾筆而已就想應該是誤差太大，把精度調高後就過了第二個子題，但後面 TLE，明明複雜度乘一乘也沒多大 QQ，心想大概是三分搜次數太多 + 三角函數跟根號常數太大。

踩幾場地雷後想到可以對答案二分搜，每個點轉到答案範圍之內的角度會是一個區間，取每個點的區間交集，如果不是空的就表示這個角度可以，實作細節：

1. 假設答案是 $d$。
2. 枚舉點，算出這個點的極作標是 $[r, \theta_0]$。
   1. 如果 $r \leq d$ 就可以不用管它。
   2. 不是的話它一定有辦法轉到 $x$ 座標是 $d$ 或 $-d$。
   3. 把 $[r, \theta_0]$ 轉到 $x$ 座標是 $t$ 需要轉的角度 $\theta$ 是 $\arccos(\frac{d}{r}) - \theta_0$。 （$\theta$ 其實理論上有兩個，因為 acos 的值域是 $[0, \pi]$ 所以不會壞掉。）
   4. 轉到 $-d$ 的會比轉到 $d$ 的角度大，把每個點這兩個角度之間的區間交集。

還有個細節是我是用 $\arctan$ 算極作標的，因為 atan2 值域是 $[-\pi, \pi]$，所以如果是負的要加半圈。

傳上去後過了第三個子題，最後一個還是 TLE，我想說沒道理啊難到有 $O(N)$ 的解嗎，然後開始壓常，把精度調低也沒什麼用，還多了幾個 WA，然後決定開大絕——時間剪枝，但也沒什麼用，最後幾分鐘已經放棄了決定開始亂做，發現我每次都重算極座標，預處理居然就過了，atan2 常數到底多大 @@。

pH 螞蟻捷運

0/100

給一棵 $N$ 個點的樹，還有 $M$ 條捷運路線，第 $i$ 條路線是從節點 $a_i$ 到 $b_i$（雙向），在同一條路線上移動不論多遠都只要花 $c_i$（$0 \leq c_i \leq 6$）元，只能透過捷運移動，然後有 $Q$ 個詢問，每個詢問問從某個點到另一個點的最小花費是多少。

我好像在不知道哪裡看過類似的題目，但這題困難許多。

本來想說可以建一張圖，每個路線都是兩個點，一個是入口、另一個是出口，從入口連權重 $c_i$ 的邊到出口，然後從每個路線上的點連權重 0 的有向邊到入口、再從出口連權重 0 的有向邊到每個點，這樣就會變成單純的最短路徑。

然後以為可以過前兩個子題，但發現第一個子題 $N \leq 1000$ 但 $M,Q$ 沒有限制，節點數會有 $N + 2M$ 個，所以沒辦法在線詢問也沒辦法先預處理，第二個子題雖然 $N,M \leq 4000$ 但 $Q$ 還是沒限制，所以不知道怎麼做詢問。

這題滅台了，沒有人有分數。

過程

為了模擬比賽所以用 Ubuntu 打，題外話：其實在自己電腦以外的地方我比較喜歡用 Ubuntu 比賽，因為別人的 Windows 都會發生怪怪的事 (?)，而且 Ubuntu 有內建踩地雷。

預想的時間分配是先用半個小時讀完題目並且對每題都有初步的想法，花 1 小時寫掉所有水題，再花 2 小時寫完有比較多想法的難題，剩下 1.5 小時處理剩下的題目。

開場打完 .vimrc、讀完題目大概剛好半個小時，對 ADEF 都有幾乎完整的想法，pB 只想到全部和必須是 0，不太確定是不是但反正可以 proof by AC，而 C 是小麻煩的數學閱讀測驗，需要花比較多時間寫，在這個時候我還以為 pG 是旋轉卡尺裸題，而 pH 只有想到上面那些錯誤的想法。

接著開始寫，pA 馬上過了，pB 錯了一次想到正解了，這個時候才過 5 分鐘而已。接著想說 DEF 都很簡單那就先專心寫 pC 吧，寫累了再去寫後面的。跟 pC 纏鬥快一個小時總算過了，接著快樂地去寫 DEF，在 120:23 拿到 600 分，剩下來的時間都花在 pG 上。

發現 pG 不好用旋轉卡尺做之後沒什麼想法，在想會不會有一堆人都 600 分了，然後大家都會 pG 只有我不會。想了一陣子後終於想到是把點旋轉，然後可以三分搜角度，纏鬥一陣子後終於拿到 32 分，踩地雷踩了一陣子後想到可以對答案二分搜，拿到 69 分了，接著各種壓常，還有去想 pH，壓到最後 14 分鐘已經放棄了，決定去上廁所，上完應該就結束了吧。回來後還有時間，想說再亂壓一下，結果就過了，還好我有垂死掙扎 (?)。

結語

總分 700/800，1 首殺，rank 1

結束後馬上開計分板來看，發現我的擔心是錯誤的 (?)，一等線是 658，二等一是 544。沒想到我幾乎整個後半場都是 rank 1，感覺自己跟去年相比成長滿多的，在入營考的時候我還會被數學閱讀測驗嚇到，這次已經可以平靜 (?) 地面對了 > < ，而且還做出另一個數學題 pG（雖然過程中我把 $\sin$ 和 $\cos$ 搞反花了很多時間），然後我覺得我應該去學一下直線與圓。

這次題目的分佈跟去年全國賽滿像的，前三題有兩個水題、一個數學閱讀測驗，pD 是算裸的資料結構題，EFG 是需要稍微想一下的題目，pH 防破台。

距離全國賽還剩一個星期，希望那個時候也能像今天一樣好好發揮，不要被數學卡死。