BZOJ 2709:二分答案 + 驗證
輸入讀取優化需注意,核心為單調性二分 + 可行性判斷。
BZOJ 3229:強大算法(文中未展開)
被大神推薦,寫了一下午,具體算法待補充。
BZOJ 3631:樹上差分 + Tarjan LCA
- 區間修改(路徑加值)最終查詢點值 → 樹上差分(前綴和思想)。
- 路徑
u-v 加 k:val[u]++, val[v]++, val[lca]-=2,最後 DFS 後序累加子樹和。
- LCA 用 Tarjan 離線算法
O(n+q),避免倍增 O(log n) 常數大。
- 代碼片段展示了 BFS 序 + 後序累加的實現。
BZOJ 3609:打表找規律
版權原因不展開,屬於找數學規律類題目。
BZOJ 1212:DP 解決
具體狀態轉移未詳述,屬於動態規劃經典題。
BZOJ 2823/1666/1667:最小覆蓋圓(Welzl 算法 / 隨機增量)
代碼給出了經典的三層循環隨機增量構建最小覆蓋圓:
- 初始圓為前兩點直徑圓。
- 新點不在圓內 → 以舊點和新點為直徑更新。
- 再檢查更早的點,三點確定圓。
期望線性時間 O(n)。
BZOJ 1802:相鄰紅格子 + DP
- 若有相鄰紅格,答案第一問 0;第二問 DP 掃描左右擴展。
- 無相鄰紅格 → 必在偶數格放棋子,直接掃描統計。
BZOJ 3574:參考題解
鏈接至 SYC 大神題解。
BZOJ 1873:Dota 解說事件模擬
完整代碼實現:擊殺連擊、首殺、雙殺/三殺、團隊壓制等邏輯,字符串映射、時間解析、狀態機模擬。
BZOJ 1925:奇特 DP / 組合數遞推
有空深入研究。
BZOJ 1819:DFS 序 + 樹狀數組 + LCA
子樹查詢用 DFS 序區間,樹狀數組維護,需 LCA 輔助。
總結
本記錄涵蓋二分、樹上差分、最小覆蓋圓、模擬、DP、DFS 序等多種進階算法,代碼片段可作模板參考。