第三年打 NPSC 了，這次的隊友是 joylintp 和 shaun_0124，跟以前一樣借了電腦教室來打。

題本．計分板．程式碼

題目

pA 邊緣人

AC, penalty: 182 + 1 * 20 = 202, solved by WiwiHo

有 $N$ 個人，當 $x$ 人分成一組時，最後 $N \bmod x$ 個人會自成一組，這些人稱為邊緣人。 令 $f(i)=$ 所有 $1 \leq x \leq N$ 中，會使第 $i$ 人是邊緣人的 $x$ 數量。 求 $f(L),f(L+1),...,f(R)$ $N \leq 2^{40}$，$R-L \leq 3 \times 10^5$

首先，$f(i) = \sum_{x=1}^N [\lfloor \frac{N}{x} \rfloor x < i]$，$[b]$ 表示 b ? 1 : 0，也就是要數有幾個 $x$ 能使 $\lfloor \frac{N}{x} \rfloor x$ 小於 $i$。

第一個發現是 $\lfloor\frac{N}{x}\rfloor$ 最多只有 $\sqrt{N}$ 種，因為：

1. 當 $x > \sqrt{N}$ 時，$\lfloor\frac{N}{x}\rfloor < \sqrt{N}$。
2. 當 $x \leq \sqrt{N}$ 時，結果顯然只有 $\sqrt{N}$ 種。

接著是要處理 $\lfloor\frac{N}{x}\rfloor x$ 實際是多少，在 $x \leq \sqrt{N}$ 的狀況很好解決，暴力算就好了，接著討論 $x > \sqrt{N}$ 的狀況。

決定一個 $t$，我們試圖讓 $\lfloor\frac{N}{x}\rfloor=t$，這樣的 $x$ 範圍會在 $(\lfloor \frac{N}{t+1} \rfloor, \lfloor \frac{N}{t} \rfloor]$，令這個範圍是 $(l,r]$。

我本來以為這樣的 $tx$ 會是 $(lt, rt]$，所以直接拿掃描線做，連範測都沒過。但其實是 $(lt, rt]$ 內所有 $t$ 的倍數才對，我亂想了一個 $O(n)$ 的作法以為是 $O(\sqrt{N})$，就這樣 WA 了一次。後來想到可以先把小於 $L$ 的 $tx$ 算好，數量是 $\lceil \frac{L}{t} \rceil - l$，接著暴力找在 $[L,R]$ 範圍內的 $tx$。

這樣做暴搜到的總數會是 $\frac{R-L}{1} + \frac{R-L}{2} + ... + \frac{R-L}{\sqrt{N}} \in O((R-L) \log \sqrt{N})$，總複雜度是 $O(\sqrt{N} + (R-L) \log \sqrt{N})$。

pB 握手

AC, penalty: 7, solved by joylintp

有 $n$ 個人，第 $i$ 個人的電力是 $d_i$，當兩個人 $i$ 和 $j$ 握手時，會釋放出 $|d_i-d_j|$ 的電力，求每兩個人都握過手後，釋放的總電力為和。 $n \leq 2 \times 10^5$

pC 俄羅斯方塊

AC, penalty: 91 + 2 * 20 = 131, solved by joylintp

有一個 $N \times M$ 的俄羅斯方塊盤面，有些格子是障礙物（障礙物可以飛），給一個大小不超過 11、正在掉落的方塊，還有它的旋轉中心，每次操作都可以把它平移和旋轉無限次，但平移和旋轉後它不能碰到障礙物，每次操作完後它會往下掉一格，如果往下掉會卡進障礙物或掉出去，就直接結束。求最後那個方塊的旋轉中心可能的位置和旋轉的方向。 $N, M \leq 10^3$

一開始 joy 沒看到方塊大小最多是 11，所以想了很久。其實就是 BFS 而已，狀態數只有 $4NM$ 個。

pD 隨機並查集

No try

有 $N$ 個元素，本來每個人是自己一個集合，並且給一個函數 $f(a,b)$，一開始令 $c=0$，然後每次操作會：

1. 把 $c$ 加 $1$
2. 隨機選兩個元素 $x$、$y$，它們分別屬於集合 $A$ 和 $B$
3. 如果 $A = B$ 就結束這個操作
4. 把 $c$ 加上 $f(|A|+|B|)$
5. 合併 $A$ 和 $B$

當集合只剩一個了就停止，求 $c$ 的期望值。 $N \leq 40$

沒有任何想法 QQ。

pE 貓貓排序

11 tries by joylintp, some idea from shaun_0124

有長度 $N$ 的序列 $a$，可以做兩種操作：

1. 把一個長度為 2 的子陣列反轉。
2. 把一個長度為 3 的子陣列反轉。

有 $Q$ 筆詢問，每筆詢問求至少要有多少次操作一，才能把 $a_l,a_{l+1},...,a_r$ 排序，操作二可以做任意次。 $N,Q \leq 4 \times 10^4$

shaun_0124 的發現：操作一是把兩個位置奇偶性不同的數交換，操作二是把兩個位置奇偶性相同的位置交換，所以可以任意地排列位置奇偶性相同的位置，答案就是位置奇偶性錯誤的數量除以 2。

看到 $N$、$Q$ 很小要幹嘛？暴搜啊 (X)，joy 壓常壓超久，據說他從本機 40 秒壓到本機 9 秒，但時限是 5 秒 QQ。

我做完 pA 後來想這題的認真解，發現它很莫隊。先將序列離散化，然後用線段樹維護目前區間內有哪些數字的位置奇偶性錯誤或正確，然後：

1. 在目前區間後加入或刪除一個數字 $x$，不影響任何數字的位置奇偶性，但改變所有 $>x$ 的數字的目標位置奇偶性。
2. 在目前區間前加入或刪除一個數字 $x$，改變所有數字的位置奇偶性，並改變所有 $>x$ 的數字的目標位置奇偶性。

有奇偶性改變就是對的變成不對的、不對的變成對的，所以就用區間反轉的懶標線段樹就可以維護。

時間複雜度是 $O(N \sqrt{Q} \log N)$，但是據說有人這樣被卡常，反而有人 $O(NQ)$ 過了 OAO？！因為時間不夠所以就沒寫完了。

pF 兔田建設

AC, penalty: 119 + 1 * 20 = 139, solved by WiwiHo, idea from shaun_0124

給一個長度 $n$ 的序列 $a$，有 $q$ 筆詢問，給定 $k$，每筆詢問求 $a_l,a_{l+1},...,a_{r}$ 有沒有長度為 $k$ 的區間中，恰好有 $c$ 個 $\leq v$ 的數。 $n,q,k \leq 10^6$

把詢問按 $v$ 排序，就可以先把 $< v$ 的位置都塗上顏色，可以用線段樹維護每個位置開頭的長度 $k$ 的區間中，有幾個位置塗顏色，最難的地方是找有沒有出現 $c$。

開頭在 $i$ 的區間和開頭在 $i+1$ 的區間，塗色的位置數量最多只會差 1，所以可以用類似介值定理的想法，$c$ 在最小值和最大值之間就表示有出現 $c$。

pG 排隊

first AC, penalty: 25, solved by WiwiHo

有 $N$ 個人在排隊，第 $i$ 個人在位置 $i$。 有 $Q$ 個事件，第 $i$ 個事件中，隊伍最前面的那個人（就是第 $i$ 個人）會走到位置 1，然後消失，接著，排在最前面的 $k_i$ 個人（就是第 $i+1$ 到 $i+k_i$ 個人）會移動到位置 $1 \sim k_i$。 求每次事件中，所有人移動的總距離。 $N \leq 10^9$，$Q \leq 10^6$

整個隊伍可以被分成一些連續的段，每次事件時，先把第一個人移到位置 1，算移動距離後把它丟掉，接著抓出前 $k_i$ 個人（可能有一段會被砍成兩半），因為每一段中的人的位置都是等差數列，所以可以 $O(1)$ 算一段的位置和，算完後把這些人都移掉，再放 $1 \sim k_i$ 的段進去，而到達的位置也是等差數列，所以加上舊位置和減去新位置和就是答案。

結語

5 AC, penalty: 564, rank 5, 1 first AC

打得還不錯，比較可惜的是 pE 來不及寫，不過我很久沒寫莫隊了，大概會 debug 到死吧。

開場的分配是 shaun_0124 看 AB，joy 看 CDE，我看 FG，開場後沒多久看到計分板中有人做出 pB，joy 就去把那題寫掉了，然後我讀到 pG 馬上有想法就開始寫，聽說我連續兩年 pG 首殺，看明年能不能繼續 (?)。

感覺今年的我跟去年相比進步了很多，如果是去年的我，看到 pA 很數學大概就不會想做了，我以前很容易看到煩人的題目就直接 WiwiHo.exe 已停止運作，這次雖然 pA 長得很煩，我換了好幾種做法，最後還是做出來了。

除了心態好很多外，實力也有提升了，雖然大部分題目都不是我想的 (X)，就希望決賽也能好好表現囉。