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

ZOJ Monthly June 2014 B-H 題詳細題解與代碼

     編輯:C++ 入門

B. Gears - 並查集維護旋轉關係

(詳見 209968 總覽,此處補充核心代碼結構)
關鍵:fa[] 父節點,dist[] 到父節點的相對深度(奇偶性決定同向/反向)。
刪除操作用 id[] 映射新節點,舊位置保留佔位。

C. Consecutive Blocks - 離散化 + 雙指針

值離散化後,記錄每個值的位置列表 pos[val]。
對每個值,雙指針 l,r 維護窗口內需刪除數 ≤ k,最大化 r-l+1。
時間 O(n log n)。

D. An Easy Game - DP + 組合數

同 ZOJ 3791,dp[step][diff] 記憶化搜尋,預處理 C[n][m]。

E. Romantic Value - 最小割建模

邊權 c' = c*(E+1)+1,Dinic 最大流。
流值 flow,最小花費 flow/(E+1),最少邊數 flow%(E+1)。

F. First Digit

直接輸出 1。

G. Greedy Driver - 雙向 SPFA

正向:起點→各點最大剩餘油量 f[i](經加油站置滿)。
反向:終點→各點最短距離 dis[i](經加油站距離歸零)。
枚舉賣油站 i,利潤 (f[i]-dis[i])*price[i] 取最大。
若 f[n]==-1 輸出 -1。

H. Grouping - SCC 縮點 + 拓撲最長路

Tarjan 求強連通分量,縮點得 DAG,點權 = 原 SCC 大小。
拓撲序 DP:dp[v] = max(dp[u]+w[v]),答案為 max(dp)。
代碼見 209984。

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