NPSC 2020 初賽

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

題本．計分板．程式碼

題目

pA 邊緣人

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

有 個人，當 人分成一組時，最後 個人會自成一組，這些人稱為邊緣人。
令 所有 中，會使第 人是邊緣人的 數量。
求
，

首先，， 表示 b ? 1 : 0，也就是要數有幾個 能使 小於 。

第一個發現是 最多只有 種，因為：

1. 當 時，。
2. 當 時，結果顯然只有 種。

接著是要處理 實際是多少，在 的狀況很好解決，暴力算就好了，接著討論 的狀況。

決定一個 ，我們試圖讓 ，這樣的 範圍會在 ，令這個範圍是 。

我本來以為這樣的 會是 ，所以直接拿掃描線做，連範測都沒過。但其實是 內所有 的倍數才對，我亂想了一個 的作法以為是 ，就這樣 WA 了一次。後來想到可以先把小於 的 算好，數量是 ，接著暴力找在 範圍內的 。

這樣做暴搜到的總數會是 ，總複雜度是 。

pB 握手

AC, penalty: 7, solved by joylintp

有 個人，第 個人的電力是 ，當兩個人 和 握手時，會釋放出 的電力，求每兩個人都握過手後，釋放的總電力為和。

pC 俄羅斯方塊

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

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

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

pD 隨機並查集

No try

有 個元素，本來每個人是自己一個集合，並且給一個函數 ，一開始令 ，然後每次操作會：

1. 把 加
2. 隨機選兩個元素 、，它們分別屬於集合 和
3. 如果 就結束這個操作
4. 把 加上
5. 合併 和

當集合只剩一個了就停止，求 的期望值。

沒有任何想法 QQ。

pE 貓貓排序

11 tries by joylintp, some idea from shaun_0124

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

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

有 筆詢問，每筆詢問求至少要有多少次操作一，才能把 排序，操作二可以做任意次。

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

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

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

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

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

時間複雜度是 ，但是據說有人這樣被卡常，反而有人 過了 OAO？！因為時間不夠所以就沒寫完了。

pF 兔田建設

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

給一個長度 的序列 ，有 筆詢問，給定 ，每筆詢問求 有沒有長度為 的區間中，恰好有 個 的數。

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

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

pG 排隊

first AC, penalty: 25, solved by WiwiHo

有 個人在排隊，第 個人在位置 。
有 個事件，第 個事件中，隊伍最前面的那個人（就是第 個人）會走到位置 1，然後消失，接著，排在最前面的 個人（就是第 到 個人）會移動到位置 。
求每次事件中，所有人移動的總距離。
，

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

結語

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)，就希望決賽也能好好表現囉。