<style> .reveal .slides { font-size: 32px; } </style> # NHDK TPR #17 (Div.1+2, Sponsored by YTP) 題解 --- ## 特別感謝 ---- ### AA 競程  ---- ### YTP 少年圖靈計畫  ---- ### 驗題者們 sam571128、franklee1015、btlllbill、dreamoon、littlecube、Fysty、SFeather、wcwu、Darren、user1519、KTK2538、amano_hina --- ## A ### [Colten 的撞球對決記 (Pool)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/A) AC: 38 First Kill: Paul Liao ---- 給定兩隊的隊員 球第 $q$ 次是誰上場 ---- 子題 1 (20)：$n+m = 2$ ---- 判斷奇偶，奇數就是第一隊，反之第二隊 ---- [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/A.%20Pool/Koying_sub1.cpp) ---- 子題 2 (80)：無額外限制 ---- 將只有一人的隊伍變成有兩個一樣的隊員 然後判斷兩次奇偶 ---- [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/A.%20Pool/Koying.cpp) --- ## B ### [豪邁大笑的Koying (Laughing Koying)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/B) AC: 39 First Kill: Paul Liao ---- 給笑點、接收到的好笑指數及好笑指數門檻 求豪邁大笑的時間 ---- 子題 1 (30)：$k=0$ ---- 對接收到的好笑指數做前綴和 若超過笑點就歸零並記錄時間 ---- [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/B.%20Laughing%20Koying/Koying_sub1.cpp) ---- 子題 2 (70)：無額外限制 ---- 一樣做前綴和，但是改為 $\ge k$ 才加 ---- [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/B.%20Laughing%20Koying/Koying.cpp) --- ## C ### [Coding 夢之國的付錢問題 (Coin)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/C) AC: 12 First Kill: Paul Liao ---- 最大可以交易兩倍的價錢 問最少的硬幣交易量 ---- 子題 1 (40)：$d_{i-1}\mid d_i$ ---- 使用貪心法 建出 $\le 2p$ 所需的最少硬幣數量表 最後枚舉 Jack 付的價錢 時間複雜度：$O(np)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/C.%20Coin/Koying_sub1.cpp) ---- 子題 2 (60)：無額外限制 ---- 經典的硬幣問題 使用 DP 建出 $\le 2p$ 所需的最少硬幣數量表 最後枚舉 Jack 所付的價錢，找到最後的答案 時間複雜度：$O(np)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/C.%20Coin/Koying.cpp) --- ## D ### [Coding 夢之國的過年分配問題 (New Year)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/D) AC: 10 First Kill: Paul Liao ---- 二分圖塗色問題 ---- 子題 1 (13)：$n \le 20$, 若可以使每一家都團圓,那麼總統規劃的一定是最佳方案 ---- 若可成功團圓則一定是最佳方案，因此只需要判斷是否為二分圖 並利用邊所連接的兩點是否分配到不同數字來驗證二分圖 時間複雜度：$O(m)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/D.%20New%20Year/Koying_sub13.cpp) ---- 子題2 (27)：$n \le 20$ ---- 利用二元枚舉，枚舉每個家庭分配到 $0/1$ 判斷是否為二分圖之後，再跟總統規劃的方案比較 找到最佳的方案 時間複雜度 $O(2^n\times m)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/D.%20New%20Year/Koying_sub12.cpp) ---- 子題 3(18) 若可以使每一家都團圓,那麼總統規劃的一定是最佳方案 ---- 同子題 1 時間複雜度 $O(m)$ ---- 子題 4(42)：無額外限制 ---- 在同一個連通塊中，合法的二分途圖色方法只有兩種 因此我們對於每個連通塊都 DFS 一次 若每個連通塊其中一種塗色方法與總統分配的差為 $cnt$ 那麼這個連通塊的最少更改數量就是 $\min(cnt, 點的數量-cnt)$ 將每個連通塊的最少數量相加就是最後的答案 時間複雜度：$O(m)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/D.%20New%20Year/Koying.cpp) --- ## E ### [Koying 的彈跳床飛行記 (Flying Koying)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/E) AC: 6 First Kill: Paul Liao ---- 在 $1$ ~ $n-1$ 中最多選 $k$ 個點，點與點之間最多不能超過 $r$ 求最大總和 ---- 子題 1 (15)： $r = n, n \le 500$ ---- 訂狀態 $dp[i][j]$ 為跳了 $i$ 次並落地在 $j$ 的最大快樂指數總和 則 $\displaystyle dp[i][j] = \max_{l < j}(dp[i - 1][l] + h[l])$ 每次轉移 $O(n)$ 時間複雜度 $O(n^2k)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/E.%20Flying%20Koying/Koying_sub1.cpp) ---- 子題 2 (35)： $r=n$ ---- 基於子題 1 的 DP 式 我們可以利用前綴 DP 將其優化 將 $dp[i][j]$ 訂為跳了 $i$ 次並落地不遠於 $j$ 的最大快樂指數總和 如此一來，我們的 DP 轉移式就會變成 $dp[i][j] = \max(dp[i][j - 1], dp[i - 1][j - 1] + h[j - 1])$ 時間複雜度 $O(nk)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/E.%20Flying%20Koying/Koying_sub2.cpp) ---- 但實際上 前兩子題只要從 $h[1]$ ~ $h[n - 1]$ 中挑前 $k$ 大的 將其相加就是答案了 時間複雜度 $O(nlogn)$ 不過大家可以用前兩個子題來練習一下自己的 DP ouobbb ---- 子題 3 (11)： $n \le 500$ ---- 套用子題 $1$ 的 DP 式 $dp[i][j]$ 為跳了 $i$ 次並落地在 $j$ 的最大快樂指數總和 但是這次的轉移式不是 $\displaystyle dp[i][j] = \max_{l < j}(dp[i - 1][l] + h[l])$ 了 由於 $r$ 的限制，所以我們只能從 $j - r$ ~ $j - 1$ 跳過來 因此轉移式為 $\displaystyle dp[i][j] = \max_{j-r \le l < j}(dp[i - 1][l] + h[l])$ 時間複雜度 $O(n^2k)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/E.%20Flying%20Koying/Koying_sub13.cpp) ---- 子題 4 (39)： 無額外限制 ---- 因為 $r$ 有限制，因此不能像子題 2 一樣用前綴 DP 這時候觀察我們的 DP 轉移式 $\displaystyle dp[i][j] = \max_{j-r \le l < j}(dp[i - 1][l] + h[l])$ 看到區間最大值，不知道各位會聯想到什麼 ---- 線段樹？ 不，我才不是 Colten ---- 這題的滿分需要用到單調佇列 monotonic queue 來優化 時間複雜度 $O(nk)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/E.%20Flying%20Koying/Koying.cpp) --- ## F ### [Colten 的科學展覽會 (Science Fair)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/F) AC: 5 First Kill: Paul Liao ---- 求最長、長度相同且相似程度 $\ge 90\%$ 的子字串長度 ---- 子題 1 (19)： $n = m = 10$ ---- 判斷兩個字串不一樣的字母有幾個 若 $> 1$ 那答案就是 $-1$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/F.%20Science%20Fair/Koying_sub1.cpp) ---- 子題 2 (37)： $n, m \le 30$ ---- 枚舉開頭、長度 找出最長的相似程度 $\ge 90\%$ 的子字串 時間複雜度 $O(n^5)$ ---- 子題 4 (44)： 無額外限制 ---- 可以發現到 我們在做編輯距離的時候 若我們做到長度 $n$ 那麼在 DP 表格中就含有長度為 $1$ ~ $n$ 的編輯距離了 因此可以把枚舉長度的步驟省略 時間複雜度 $O(n ^ 4)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/F.%20Science%20Fair/Koying.cpp) --- ## G ### [高乘載管制 (High‐occupancy vehicle)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/G) AC: 0 真 防破台 ---- 子題 1 (1)： 題目範例 ---- 因為我不會輸出 所以出一個子題讓我練習輸出 ---- 子題 2 (13)： $N, M, K \le 5$ ---- 因為我不會 Debug 所以出一個子題讓我 Debug ---- 子題 3 (27)： $K = 0$ ---- 因為我不會 Dijkstra 所以出一個子題讓我練習 Dijkstra 時間複雜度：$O(n + mlogn)$ ---- 子題 4 (21)： $K = 1$ ---- 因為我不會建虛點 所以出一個子題讓我練習建虛點 時間複雜度：$O(n + mlogn)$ 建虛點空間複雜度：$O(mK^2)$ ---- 子題 5 (25)： $K \le 10$ ---- 空間爆炸，我很勇 我用 priority_queue 裝 將使用了幾次折價券合併入 pq 的狀態中 省去建虛點的步驟 時間複雜度：$O(n + 10mlogn)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/G.%20High-occupancy%20vehicle/Koying_sub12345.cpp) ---- 子題 6 (13)： 無額外限制 ---- priority_queue 也爆炸，沒關係 早上好 Ten Point Round，現在我有兩個 D Dijkstra 與 Dynamic Programming ---- 做 $k + 1$ 次 Dijkstra 第 $i$ 次代表使用 $i$ 次折價券的情況 每次做完 Dijkstra 之後，枚舉 $t (t > i)$ 將每個邊使用 $t-i$ 次折價券之後的邊權對使用 $t$ 次的狀態鬆弛 時間複雜度：$O(k\times(n + mlogn + mk))$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/G.%20High-occupancy%20vehicle/Koying.cpp) --- ## H ### [Coding 夢之國的大胃王 Jack (Big Stomach Jack)](https://codeforces.com/group/H0qY3QmnOW/contest/376232/problem/H) AC: 2 First Kill: Gino ---- 子題 1 (11)： $n, q \le 1000,\ k=0$ ---- 暴力找就可以了 時間複雜度：$O(nq)$ ---- 子題 2(17)： $n, q \le 1000$ 暴力搜尋 + 修改 時間複雜度：$O(nq)$ ---- 子題 3 (29) $k = 0$ ---- 利用單調佇列維護每個點最多可以吃到哪裡 時間複雜度：$O(n + q)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/H.%20Big%20Stomach%20Jack/Koying_sub13.cpp) ---- 子題 4 (43)： 無額外限制 ---- 使用線段樹維護區間內最小的美味指數以及其位置 利用線段樹上二分搜，得出最多可以吃幾個食物 並利用查詢到的位置做修改 時間複雜度：$O(qloglogn)$ [參考程式](https://github.com/NHDK-Ten-Point-Round/ten-point-round-17/blob/main/solution/H.%20Big%20Stomach%20Jack/Koying.cpp)