--- title: TNHSPA_二月試辦場 tags: TNHSPA,contest description: View the slide with "Slide Mode". --- # **TNHSPA_二月試辦場** ## 公告 :::success 2/28 公告 TNHSPA_二月試辦場 題解已上線 ::: :::success 2/26 公告 TNHSPA_二月試辦場 已結束，感謝大家的參與 ::: :::danger 2/24 臨時修正公告 親愛的參賽者們，我們在此通知 本次題數由 7 題改為 6 題，其餘並無更動 對於此次修改造成的不便，我們深表歉意 謝謝您的支持和理解 ::: --- ## 比賽資訊 * 時間 ： 2 月 26 日 14:00 ~ 17:00 * 地點 ： [Codeforces Group](https://codeforces.com/group/vyc3POHHoZ/contests) * 賽制 ： IOI制 * 題數 ： 7題 * 命題範圍 ： 大約比照能競南區賽、資奧初選（包含但不限於：貪心、DP、暴搜、基礎圖論、資結等） * 程式語言使用限制 ： 無 ###### 註：因本次比賽為試辦場，故範圍較廣，旨在了解程度 --- ## 比賽結果 ### 最終排名 ![](https://i.imgur.com/4WNZHvi.png) ### 題解 #### 第一題 其實不用考慮哪個是正確哪個是錯誤，只要求兩個時間相差就好，但因為時間有循環的概念，因此除了用大的減小的，還要考慮大的循環到完整24小時後回到0時，具體做法可以以互補的概念處理，先求大減小的值，用24小時減去該值。 :::spoiler AC code ```cpp= //waiting ``` ::: #### 第二題 由於大桶子的容量大於所有 $q_i$，因此保證在大桶子中操作一定不會有容量不足的問題，接著將水瓶 $i$ 裝滿後倒入 $x_i$ 次，可以使得大桶子增加水量 $c_ix_i$，若將大桶子中的水倒入水瓶 $i$ 並露空其中的水 $x_i$ 次，可以使大桶子減少水量 $c_ix_i$。 考慮以上方法，我們可以將達到所求水量的目標，設為找到 $c_1x_1+c_2x_2+…+c_nx_n=q_i$ 的一組整數解。 而透過貝祖定理(證明請參考維基百科)，$ax+by=m$ 有整數解 $(x,y)$ 若且唯若 $m$ 是 $gcd(a,b)$ 的倍數，該定理同樣適用更多項的方程，如本題例子，若 $m$ 是 $gcd(c_1,c_2,…c_n)$ 的倍數，則答案為是，否則為否。 :::spoiler AC code ```cpp= //waiting ``` ::: #### 第三題 因為對於題目中的每個子樹，最小的前序遍歷是固定的，與子樹以外的任何節點皆沒有關係，也因此我們可以先求每個子樹的最小前序遍歷，而由題目所述，葉節點的前序遍歷為其己身，而非葉節點則是先經過自身，而因為可以交換左右子樹，因此字典序最小的前序遍歷是先走訪前序遍歷字典序較小的子樹。可以利用遞迴實現該方法。 :::spoiler AC code ```cpp= //waiting ``` ::: #### 第四題 * Subtask 1 利用二維dp紀錄花費，其中兩個維度分別代表位置、還剩下的燃油量，複雜度 $O(nl)$。 * Subtask 2 延續上一子任務的做法，不過因為途中若沒有加油站無法加油，因此讓燃油量恰巧可以到達加油站才是有意義的，因此將dp的第二個維度改為燃油足夠到達第幾個加油站，複雜度 $O(n^2)$。 * Subtask 3 其實這題只是貪心而已，首先最好的情況一定是在終點用完燃油，多出來的燃油沒有意義，此時我們可以選擇在路途上任意加油站補充剛好可以到達終點的燃油，而為了達到最小花費，因此在燃油最便宜的地方購買，接著為了能達到該加油站，我們需要在此加油站以前燃油最便宜的加油站加足夠到達此加油站的燃油，以此類推。而實作部分，可以對燃油價格進行sort，或者使用set等結構維護，複雜度 $O(n log n)$。 :::spoiler AC code ```cpp= //waiting ``` ::: #### 第五題 * Subtask 1 利用vector等結構維護，每次用lower_bound查詢位置，並且在該位置插入，複雜度 $O(n^2)$ * Subtask 2 先將所有資料讀入，並且一次進行sort，取得每個學生在最終的排名，該步驟即離散化，再用原本輸入的順序，利用Fenwick tree等結構維護前綴和。複雜度 $O(n log n)$。 * 另解 使用pbds中tree的order_of_key函式，可以求得當前數組中，嚴格小於某數的元素數量，每次查詢複雜度 $O(log n)$，總複雜度 $O(n log n)$。 :::spoiler AC code ```cpp= //waiting ``` ::: #### 第六題 * 官解 先計算出該圖的最小生成樹，因為在網路中移動時，我們希望路徑上的邊權盡可能的小，因此對於所有詢問，走在該圖的最小生成樹上一定能達到題目所求。另外，對於每筆詢問從 $l$ 到 $r$ 能連通的最小權限級別，其實相當於 $l$ 到 $l+1$、$l+1$ 到 $l+2$、…、$r-1$ 到 $r$ 的最大值，因此我們可以用線段樹等結構維護，使其對於每筆查詢有 $O(log n)$ 的複雜度。而要計算每個 $i$ 到 $i+1$ 連通所需的最小權限級別，我們可以對一開始計算出的最小生成樹，採用倍增法求其LCA，並記錄倍增法途中的最大邊權，以求的所需的最小權限級別。以上做法建表複雜度 $O(n log n)$，查詢總複雜度 $O(q log n)$，總複雜度 $O((n+q) log n)$。 * 另解 也可以使用dsu計算最小生成樹，將邊由邊權小至大進行排序，並在計算最小生成樹的同時記錄使 $i$ 與 $i+1$ 連通的邊權為多少。 :::spoiler AC code ```cpp= //waiting ``` ::: --- [DC群組 Join us](https://discord.gg/jpxZT9nZ5k) [回到首頁](https://hackmd.io/@TNHSPA/intro) [Codeforces使用教學](https://hackmd.io/@TNHSPA/cf_intro)