首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

BZOJ 刷題記錄 Part 6:多題解題思路匯總

     編輯:C++ 入門

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 算法 / 隨機增量)

代碼給出了經典的三層循環隨機增量構建最小覆蓋圓:

  1. 初始圓為前兩點直徑圓。
  2. 新點不在圓內 → 以舊點和新點為直徑更新。
  3. 再檢查更早的點,三點確定圓。

期望線性時間 O(n)。

BZOJ 1802:相鄰紅格子 + DP

  • 若有相鄰紅格,答案第一問 0;第二問 DP 掃描左右擴展。
  • 無相鄰紅格 → 必在偶數格放棋子,直接掃描統計。

BZOJ 3574:參考題解

鏈接至 SYC 大神題解。

BZOJ 1873:Dota 解說事件模擬

完整代碼實現:擊殺連擊、首殺、雙殺/三殺、團隊壓制等邏輯,字符串映射、時間解析、狀態機模擬。

BZOJ 1925:奇特 DP / 組合數遞推

有空深入研究。

BZOJ 1819:DFS 序 + 樹狀數組 + LCA

子樹查詢用 DFS 序區間,樹狀數組維護,需 LCA 輔助。

總結

本記錄涵蓋二分、樹上差分、最小覆蓋圓、模擬、DP、DFS 序等多種進階算法,代碼片段可作模板參考。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved