Codeforces Round #221 Div.2 B.I.O.U. C.Divisible by S 完整解析

B. I.O.U. (債務優化)

模型：n 人，m 條有向債務 u -> v 欠 w。
淨流入 in[i] - out[i]：in[i] 被欠總額，out[i] 欠出總額。
最優結算：所有淨流入 > 0 的人收錢，總和即答案。
證明：任意債務鏈可重組為「淨欠款人直接付給淨債權人」，中間環節抵消，總交易額 = Σ max(0, in[i]-out[i])。
複雜度 O(n+m)。

C. Divisible by Seven (同 375A/374A)

構造法核心：1689 排列覆蓋模 7 全餘數。
代碼關鍵：取出 1,6,8,9 各一 → 剩餘構成前綴 → 計算 prefix*10000%7 → 查表輸出後綴 → 補零。
注意前導零：前綴若全為 0 則跳過，直接輸出後綴+零。

D. Maximum Submatrix 2 (行可排序最大全 1 子矩陣)

關鍵觀察：列順序固定，行可任意排序 → 對每列 j，統計有多少行在該列向左有 ≥ L 個連續 1。
預處理：dp[i][j] = 第 i 行第 j 列向左連續 1 數。
統計：cnt[j][L] = 有多少行 dp[i][j] ≥ L。
後綴和優化：對每列 j，從大到小累加 cnt[j][L] += cnt[j][L+1]。
答案：max(dp[i][j] * cnt[j][dp[i][j]])。
複雜度 O(n*m + m²)，n,m ≤ 5000 通過。
完整代碼見 Round #221 總題解。