最後更新日期 2024 / 01 / 01

調和級數

簡介

一個在因倍數相關題目可以用到的小技巧
程式碼大概像這樣
可以得到 O(nlog⁡n) 的時間複雜度

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j += i) {
        // to something
    }
}

公式

nlog⁡n≈∑k=1n1k=1+12+13+14+⋯+1n

例題

https://codeforces.com/contest/1850/problem/F
https://cses.fi/problemset/task/1081/

推薦文章

APCS 實作滿級完全攻略

筆者只是一個滿級的考生 以下內容都是根據個人經驗給出的建議考試名額不多 很快就會被搶完 所以開放報名第一時間記得趕快上去搶然後第一次應考前一定要先下載官方的虛擬環境 並且留意自己習慣的編輯器、IDE 有沒有在環境裡面 如果沒有的話就要事先練習好其他軟體的操作方式APCS 的實作題每次考試總共會有 4 題 每題 20 筆測資 每筆測資只要對了就可以獲得 5 分 所以就算沒辦法拿滿分 寫多少算多少 一定要傳上去- 基本程式語法如果只是要拿二級的話 其實練習方式還蠻廣的 基本上所有"會寫程式的人"都可以達到這個等級 也就是說 不管你想去寫網頁、開發遊戲、刷題目都應該可以達到 2 級這個目標- 二維陣列- 複雜模擬APCS 的 3 級範圍非常吃實作能力 需要邏輯清晰且可以處理複雜的操作才能達到 3 級 一個比較複雜的例子：APCS 202210 貨運站 而且在第二題當中 二維陣列操作出現的的頻率非常高 必須非常熟悉二維陣列 最後建議想達到 3 級分的話可以多練歷屆 APCS 第二題不過如果你的目標是更高的級分 其實不需要刷太多歷屆第二題 通常隨著能力提升實作能力也會自然提升- 排序- 搜尋- 貪心- 遞迴- 動態規劃- 資料結構4 級跟 5 級的範圍其實差不多 不過最大的差別就是要拿到 4 級只需要知道比較淺的知識就行了 那想達到 45 級的話就非常吃演算法和資料結構的運用能力 非常推薦這份 AP325 講義題目的部分 很常出現經典題或者經典題稍微改編 所以也很建議去 CSES 這個很多經典題的 Judge 多刷點題 可以配合 CSES 寶典 一起讀集結了多位 APCS 滿級分的出題者與驗題者 我們在每個月都會辦一場 APCS 模擬賽 如果還不清楚自己練習方向或想測試實力的話 歡迎加入 Discord 群組 重點是完全免費！！

APCS

[題解] TIOJ 2173 收集寶藏 (北市賽 2019 pE)

兩個人到一個 n times m 大的迷宮裡探險 在迷宮裡只能往右和往下走 而入口在 1, 1 出口在 n, m 求離開迷宮最多能帶走多少寶藏 迷宮示意圖如下problem image應該不難聯想到這題 CSES - Grid Paths 只要把狀態開成四維 分別代表第一個人的 xy 座標及第二個人的 xy 坐標 然後可以推出：begin{equation}dpijkl = gridij + text{max} begin{cases} dpi-1jk-1l dpi-1jkl-1 dpij-1k-1l dpij-1kl-1 end{cases}end{equation}不過加上 gridij 的部份有些細節要處理 詳細轉移的部份自己看下面的程式碼在本地測試了一下就順利通過了範測 ouob結果剛剛的作法傳上去之後很快就拿到 TLE 了 於是就想說順便來嘗試看看最近剛學到的壓常小技巧cpp加上去後通過了更多比測資但依然還是 TLE又仔細思考了一下題目 發現 i + j neq k + l 的狀態一定不合法 所以就把不合法的狀態 continue 掉然後就神奇的成功壓常 AC 了 :Dcppusing namespace std;const int MAXN = 1e2 + 3;const int INF = 32000;int mpMAXNMAXN;int dpMAXNMAXNMAXNMAXN;signed main { iosbase::syncwithstdio0; cin.tie0; cout.tie0; int n, m; cin n m; 把邊界都設定為 -INF for int i = 0; i = n + 1; i++ { for int j = 0; j = m + 1; j++ { for int k = 0; k = n + 1; k++ { for int l = 0; l = m + 1; l++ { if i == 0 || i == n+1 || j == 0 || j == m+1 || k == 0 || k == n+1 || l == 0 || l == m+1 { dpijkl = -INF; } } } } } 初始狀態 dp0000 = 0; dp0101 = 0; dp1010 = 0; dp0110 = 0; dp1111 = 0; 輸入整張地圖 for int i = 1; i = n; i++ { for int j = 1; j = m; j++ { cin mpij; } } DP for int i = 1; i = n; i++ { for int j = 1; j = m; j++ { for int k = 1; k = n; k++ { for int l = 1; l = m; l++ { 一點點剪枝 if i + j = k + l continue; if mpij == -1 || mpkl == -1 { dpijkl = -INF; continue; } 轉移 dpijkl = max{ dpi-1jk-1l, dpi-1jkl-1, dpij-1k-1l, dpij-1kl-1, }; 拿到寶藏增加分數 dpijkl += mpij == 1 + mpkl == 1 i = k || j = l; } } } } 輸出答案 cout maxdpnmnm, short0 endl;}

TIOJ

[題解] TIOJ 2195 粉刷護欄 (TOI 2021 初選 pC)

上下有個有一根木樑 然後中間有 n 條可能會相交的木板 找出最多可以釘上幾條木板並構造最大字典序的解 細節自己去 TIOJ 看 :因為這題看起來沒人寫題解 於是我就發了這篇文章 ouob仔細觀察問題 我們可以把問題轉換成 LIS 或 LCSLCS 的話應該不難理解 因為要釘最多木板其實就是要在上下兩條陣列各選一個共同的子序列 然後把每個數字一一對應釘起來 但是 LCS 需要 On^2 的時間複雜度才能計算 所以一定會 TLE接著是 LIS 的作法 仔細觀察題目的話可以發現 如果木板有"座標"的話 其實我們在做的事情就是"對木板做 LIS" 更精確一點的說 就是我們其實可以把木板在上樑的點跟下樑的點綁成一個 pair 做 LIS 我們說木板 A 的座標小於木板 B 代表 A 的下樑座標跟上樑座標都小於 B至於座標的部分大概就是這個意思： 以附圖為例 木板 3 的座標就是 2, 1 木板 4 的座標就是 5, 3 木板 5 的座標就是 4, 4如果用最普通的 DP 方式 就算能構造解也很難求最大字典序 於是我們修改一下計算方式 把轉移式改成 "定義 dpi 為把第 i 個元當頭素能構造出的 LIS" 其實就只是倒著做 LIS 然後 Increasing 改成 Decreasing 就好了做完 DP 之後 我們要從 dp 值大的開始構造 先找一個 dp 值跟最終 LIS 一樣長而且字典序最大的元素 接著往右找小一點的直到 1 為止關於上面提到的"座標" 實際上不需要真的把座標算出來 我們只需要把第二個陣列代表下梁座標的陣列每一個元素替換成該元素在第一個陣列出現的位置 並對第二個陣列做 LIS 就可以了 ~~原因的話講起來有點麻煩 自己想吧~~第一次傳 WA 了一片 然後 debug 的時後測出這樣的測資會出錯 如果你也找不到你的程式坐在哪裡的話 不仿測試看看這筆測資33 1 21 2 3cppusing namespace std;const int MAXN = 2e5 + 10; map 會超時，所以改 unorderedmapunorderedmapint, int rpos;unorderedmapint, int pos;vectorint lensMAXN;int vMAXN;bool cmpint a, int b { return rposva rposvb;}signed main { io; int n; cin n; for int i = 1; i = n; i++ { int tmp; cin tmp; 紀錄元素座標 postmp = i; } for int i = 1; i = n; i++ { int tmp; cin tmp; 將陣列的值設定為目前元素在上面陣列的出現位置 vi = postmp; 把坐標在映射回他的值，輸出的時候會用到 rpospostmp = tmp; } LIS 的部分 作法類似： int len = 0; vectorint dp; for int i = n; i = 1; i-- { int ans = 0; 儲存目前 dp 值：以 i 為開頭能構造出多長的 LIS if dp.empty || dp.back vi { dp.pushbackvi; 紀錄目前的 dp 值 ans = dp.size; } else { auto ite = upperboundalldp, vi, greaterint; ite = vi; 紀錄目前的 dp 值 ans = ite - dp.begin + 1; } len 維護最終 LIS 長度 len = maxlen, ans; 紀錄每個長度的解 lensans.pushbacki; } 構造解 int cur = 0; for int i = len; i = 1; i-- { 依照字典序做 sort sortalllensi, cmp; for auto j : lensi { 排除在目前選到的元素左邊的元素 if j = cur continue; 排除加入後會相交的元素 用於排除文章中寫的“一個小測資”那段的 Case if vj vcur continue; cur = j; 把 index 映射回去並輸出 cout rposvj " "; break; } }}

TIOJ

© Copyright 2023 dada878.com