NPSC 2020 決賽

比賽前三天請了三天公假團練，不過星期三下午我跑去教育科技展玩所以沒練到 (X)，星期四打得還不錯，星期五打到一半睡著 (??)。

題本．計分板．程式碼

題本官網還沒放，放程式碼的隨身碟好像不見了 OAO，等找到再放上來。

題目

pA

AC, penalty: 37, solved by WiwiHo, idea from joylintp

有一張 個點的圖，任兩點最多共一個環，求最小著色數和著色方法。

其實就是給仙人掌，joy 聽完題目就想到除了 答案是 1 外，答案一定是 2 或 3，然後我想了一下，既然把 BCC 縮點後是樹，那每個 BCC 的塗色方法不會互相影響塗色數，然後每個 BCC 都是一個環，所以就先用兩種顏色塗一圈後，最後一格不能塗就用第三種顏色。

這題有一個雷點就是 ，有人的顏色是從 2 開始放，然後就爛掉了，我們有特判不過我也是從 1 開始放的。

還有就是這題首殺是 36 分鐘，我們差一分鐘 QQ。

pB

AC, penalty: 14, solved by shaun_0124

我沒看題目，好像很多人都沒看過題目 (?)，有來的人都有過。

pC

AC, penalty: 21, solved by joylintp

我也沒看。

pD

給一張 個點的有向圖，第 個點的出度是 ，還有一個函數 ，如果現在在第 個點上，要走第 步，就要往這個點的第 條邊（0-indexed）走，要走 步，求每一步會到哪個點。

這題的困難點是 算出來的數字會超大，而且每次都要模不同數字，我們就想到可以取一些度數的最小公倍數，這樣可以少模幾個，我們最後弄到剩 240 個模數，但壓常壓很久都沒過，據說有人弄到剩 40 個，emanlaicepsa 說有 30 個的作法但他沒寫。

pE

燒雞 by WiwiHo

給一個 到 的排列 ，還有 個排列，第 個排列是把上一個排列的第 和 項交換，求字典序排序後的結果（輸出編號）。

我用的作法是把每一個排列當成一個時間點，每次交換其實是兩個單點修改，然後一開始把所有時間當成一段，接著看第一個位置在哪些時間被改變，如果被改變了，就把那個時間所在的那段切開，先找到同一段要被切的所有地方，切完後再把它們排序，再去看第二個位置，做一樣的事情。這個作法會假設同一段裡的排名都是連續的，但是如果有兩個不同的段的前綴一樣，這樣就可能會壞掉。好像燒雞的人都是這個解 (?)。

正解是一樣把每一個排列當成時間，交換當成兩個單點修改，然後弄一棵維護前綴 hash 的持久化線段樹，第 個版本就是第 個排列，比較字串時，在線段樹上二分搜兩個排列的最長共同前綴，這樣就可以用 的時間比較排列，總時間複雜度會是 。

我完全沒往資料結構的方向想 QQ，以為這題有美麗的解法，結果沒有。

pF

AC, penalty: 41, solved by WiwiHo, idea from shaun_0124

給 個點，你可以決定一個數字 ，然後以每一個點為圓心作半徑 的圓，求最多可以有幾個交點。

我看完題目發現是數學就先丟給隊友了，然後 shaun_0124 跟我說答案好像是 ，我想了一下想到交點都會在兩個點的中垂線上，那麼如果有兩對圓的交點在同個地方，那一定是中垂線的交點，如果是同一條中垂線的話也不會是同一個點， 超級大的話就不會有交點一樣了。

pG

，給一個你不知道長怎樣的一一對應函數 ，它的反函數是 ，你可以詢問任意次 ，然後有 筆詢問，問你 是多少。
強制在線，記憶體限制 8 MB。

算了算發現平均每個 只能使用 0.5 B 的記憶體，然後就不會了。

pH

給一個數列 ，然後有兩種詢問：

1. 詢問一個區間 ，你每次操作可以在這個區間裡選一個區間，然後反轉，求「相同的相鄰數字的對數」最少可以是多少，還有達到這個最少值至少需要多少次操作。
2. 區間改值。

「相同的相鄰數字」的最少對數可以用眾數的出現次數算，然後我就不會了。官解有什麼戰鬥線段樹、Treap 什麼的東西，超噁。

結語

4 AC, penalty: 113, rank 6

很幸運地得獎了，前五名都做出來 5 題，剛好我們是 4 題裡面最快的。不過我還是覺得不太滿意，沒把 pE 做出來，我居然完全沒往資料結構的方向想 @@，如果有做出來的話，我們就是第二名了 QQ。

這次到第 19 名都做出了 4 題，我們在 41 分鐘就把 4 題做完了，所以後面四個小時都在燒雞。我中間有因為腦袋停止運作睡了一個小時，好像不太應該在比賽的時候睡覺，我的腦袋滿常停止運作的，大概就是一種腦袋在抗拒思考的感覺。