前言
勞動節期間刷 Codeforces 多道題目，記錄解題思路、踩坑經驗與代碼優化過程。
題目 A：987654321 Problem
打表找規律，屬於水題。
題目 B：Self-numbers 2
初版：哈希表 → 內存超限/超時
將不符合條件的數存入哈希表，第 5 組 PE，第 6 組 TLE。
優化：滾動數組（滑動窗口）
- 最大影響範圍：7 位數 × 9 = 63
- 開長度 126 數組，以 63 為滾動節點
f1 記錄當前波影響，f2 記錄對下一波影響- 空間 O(1)，時間 O(N)
題目 C：Boxes
模擬法通過
- 數據最大 2^31，最差 31×31=961 步
- 每次移動雙方接近，實測 50 步內結束
- 代碼簡潔，無需 O(1) 數學解
題目 D：Palindrome pairs
- 統計回文子串頭尾位置
- 字符長度為 1 的情況處理困難，暫未完全解決
- Manacher 算法可優化
題目 E：模擬大法
- 找最近有效段落，然後按規則模擬輸出
- 邏輯直觀，注意邊界條件
題目 F：排序 + 模擬
- 按坐標排序後依次處理
- 輸出格式嚴格，注意 PE 風險
題目 G：模擬 + 畫圖
- 記錄路徑轉折點
- 下界計算易錯，導致 2 次 WA
- 最終通過，但代碼可進一步優化
題目 H：Wall Painting（異或運算）
核心洞察
- 異或和可拆解：每位獨立計算
- 所有組合總和 = 各位貢獻之和
- 無需容斥原理，直接組合數學計算
- 組合數
C(n,k) 預處理，模 1000003
題目 I：Railway Tickets（DP）
- 終點可在起點前（需 swap）
- 三種票價區間，狀態轉移 O(n×max_len)
- 交 11 次才 AC，邊界條件極其關鍵
題目 J：Ministry（二維 DP + 滾動數組）
- 每層只依賴上一層 → 滾動數組優化空間
- 左右掃描兩遍取最小（順序無關）
- 路徑回溯輸出
題目 K：規律題
- 1×n: (n+1)/2
- 2×n: 可轉化為 1×n
- 3 是關鍵：優先用 1×3 消除
- 取模 3 後處理殘餘
題目 L：Gentlemen（01 背包變體）
- DP 計算方案數，pre 數組記錄路徑
- 方案數 >1 輸出 -1，=0 輸出 0，=1 回溯輸出
- 比標準 01 背包寫法更直觀
題目 M：Broken Line
- 題目實為矩形邊界判斷（非任意圖形）
- 向量法過度複雜，幾何判斷極簡
- 判斷點在線段上、射線法判斷內外
題目 N：Beat（DFS）
- 數據極小（n≤20），暴力 DFS 即可
- 狀態：當前節點、已選邊數、上一邊權重
- 剪枝：要求邊權非遞減
總結心得
- 模擬題佔多數，邏輯清晰比優化重要
- 滾動數組是 DP 空間優化利器
- 組合數學可化繁為簡（題目 H）
- 讀題細節決定生死（題目 I swap、題目 M 矩形）
- CF 寬容 PE，但嚴格格式仍需遵守
