Codeforces Round #287 (Div. 2) A-E 題解總覽

A. 貪心排序

輸入 n 個數與 k，選最多不超過 k 總和的數，輸出個數與下標。
解法：結構體存 {value, index}，按值升序排序，貪心累加直到超過 k。

B. 幾何圓移動

兩圓半徑 r，圓心距 d。每步可將圓心沿連線移動 ≤2r。最少步數 = ceil(d / (2r))。注意浮點精度，用整數運算：(d + 2r - 1) / (2r) 或 sqrt 後判斷。

C. 完美二叉樹模擬

高度 h，葉子編號 n。命令串 "LRLRLR..."，規則：已訪問跳過，連續跳兩次回父節點，走到非目標葉子回父節點。求訪問節點數。
解法：按層從根到葉模擬。當前節點 x，層高 rem。若 n 在左子樹（n ≤ 2^{rem-1}）且下一命令為 L，或在右子樹且命令為 R，則只訪問 1 個節點並翻轉命令；否則需訪問整棵另側子樹（2^{rem} - 1 節點）再回來，命令不變。累加答案。

D. 數位 DP

n 位數，存在後綴能被 k 整除。dp[pos][rem][has]：前 pos 位，模 k 餘 rem，是否已有合法後綴（has=0/1）。轉移枚舉當前位 0~9（首位 1~9），更新餘數與 has。最終求 dp[n][*][1] 和模 m。

E. 圖論最短路 + 權值最大化

n 城市，m 條邊（權重 0/1 表示壞/好）。求 1→n 最短路（邊數最少），在最短路中使好邊數最多（即壞邊最少）。
解法：SPFA/BFS 計算 dist[u] 到 1 的最短距離，同時維護 good[u] 最大好邊數。轉移時優先更新距離，距離相等時最大化 good。最後從 n 回溯構造最短路，標記路上邊。輸出：路上壞邊修好(1)，路外好邊炸毀(0)。

代碼片段（E 題核心）

// SPFA 求最短路且好邊最多
queue q; q.push(1);
dist[1]=0; good[1]=0; inq[1]=true;
while(!q.empty()){
    int u=q.front(); q.pop(); inq[u]=false;
    for(auto [v,w,id]:adj[u]){
        if(dist[v] > dist[u]+1 || (dist[v]==dist[u]+1 && good[v] < good[u]+w)){
            dist[v]=dist[u]+1; good[v]=good[u]+w; pre[v]=u; preId[v]=id;
            if(!inq[v]){ q.push(v); inq[v]=true; }
        }
    }
}
// 回溯標記路徑邊
vector onPath(m+1,0);
for(int v=n; v!=1; v=pre[v]) onPath[preId[v]]=1;
// 輸出受影響邊
for(int i=1;i<=m;++i){
    if(onPath[i] && w[i]==0) ans.push_back({u[i],v[i],1}); // 修好
    if(!onPath[i] && w[i]==1) ans.push_back({u[i],v[i],0}); // 炸毀
}

總結

本場比賽涵蓋貪心、幾何、樹模擬、數位 DP、圖論 SPFA 變體，難度遞增。關鍵技巧：C 題層次模擬翻轉命令、D 題數位 DP 狀態壓縮、E 題雙準則 SPFA + 路徑回溯。適合作為綜合訓練題單。