NHDK TPR #17
(Div.1+2, Sponsored by YTP)
題解
特別感謝
AA 競程
YTP 少年圖靈計畫
驗題者們
sam571128、franklee1015、btlllbill、dreamoon、littlecube、Fysty、SFeather、wcwu、Darren、user1519、KTK2538、amano_hina
給定兩隊的隊員 球第 \(q\) 次是誰上場
子題 1 (20)：\(n+m = 2\)
判斷奇偶，奇數就是第一隊，反之第二隊
子題 2 (80)：無額外限制
將只有一人的隊伍變成有兩個一樣的隊員 然後判斷兩次奇偶
給笑點、接收到的好笑指數及好笑指數門檻 求豪邁大笑的時間
子題 1 (30)：\(k=0\)
對接收到的好笑指數做前綴和 若超過笑點就歸零並記錄時間
子題 2 (70)：無額外限制
一樣做前綴和，但是改為 \(\ge k\) 才加
最大可以交易兩倍的價錢 問最少的硬幣交易量
子題 1 (40)：\(d_{i-1}\mid d_i\)
子題 2 (60)：無額外限制
二分圖塗色問題
子題 1 (13)：\(n \le 20\), 若可以使每一家都團圓,那麼總統規劃的一定是最佳方案
子題2 (27)：\(n \le 20\)
子題 3(18) 若可以使每一家都團圓,那麼總統規劃的一定是最佳方案
同子題 1
時間複雜度 \(O(m)\)
子題 4(42)：無額外限制
在同一個連通塊中，合法的二分途圖色方法只有兩種 因此我們對於每個連通塊都 DFS 一次 若每個連通塊其中一種塗色方法與總統分配的差為 \(cnt\) 那麼這個連通塊的最少更改數量就是 \(\min(cnt, 點的數量-cnt)\)
將每個連通塊的最少數量相加就是最後的答案
時間複雜度：\(O(m)\)
在 \(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)\)
子題 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)\)
但實際上
前兩子題只要從 \(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)\)
子題 4 (39)： 無額外限制
因為 \(r\) 有限制，因此不能像子題 2 一樣用前綴 DP 這時候觀察我們的 DP 轉移式 \(\displaystyle dp[i][j] = \max_{j-r \le l < j}(dp[i - 1][l] + h[l])\) 看到區間最大值，不知道各位會聯想到什麼
線段樹？
不，我才不是 Colten
求最長、長度相同且相似程度 \(\ge 90\%\) 的子字串長度
子題 1 (19)： \(n = m = 10\)
判斷兩個字串不一樣的字母有幾個 若 \(> 1\) 那答案就是 \(-1\)
子題 2 (37)： \(n, m \le 30\)
枚舉開頭、長度 找出最長的相似程度 \(\ge 90\%\) 的子字串
時間複雜度 \(O(n^5)\)
子題 4 (44)： 無額外限制
可以發現到 我們在做編輯距離的時候 若我們做到長度 \(n\) 那麼在 DP 表格中就含有長度為 \(1\) ~ \(n\) 的編輯距離了 因此可以把枚舉長度的步驟省略
時間複雜度 \(O(n ^ 4)\)
子題 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\)
子題 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))\)
子題 1 (11)： \(n, q \le 1000,\ k=0\)
暴力找就可以了
時間複雜度：\(O(nq)\)
子題 2(17)： \(n, q \le 1000\)
暴力搜尋 + 修改
時間複雜度：\(O(nq)\)
子題 3 (29) \(k = 0\)
子題 4 (43)： 無額外限制