Codeforces Round #257 Div.2 題解：A模擬、B找週期、C貪心、D最短路+邊刪減

A. Jzzhu and Children：隊列模擬

題意：n 個孩子排隊，第 i 個至少需要 a[i] 顆糖。每次給隊首 m 顆，若滿足需求則離隊，否則去隊尾。求最後離隊的孩子編號。

解法：直接用 queue<pair<int,int>> 模擬，存 {剩餘需求, 編號}。時間 O(總糖果數/m)，數據範圍內極快。

while(!q.empty()) {
    auto cur = q.front(); q.pop();
    if (q.empty()) { ans = cur.id; break; }
    if (cur.need > m) q.push({cur.need - m, cur.id});
}

B. Jzzhu and Sequences：找遞推週期

題意：f(1)=x, f(2)=y, f(n)=f(n-1)-f(n-2)，求 f(n) mod 1e9+7。

關鍵觀察：展開前幾項發現週期為 6：

f(3)=y-x, f(4)=-x, f(5)=-y, f(6)=x-y, f(7)=x, f(8)=y ...

預計算前 6 項取模（注意負數處理：(x%MOD+MOD)%MOD），直接按 (n-1)%6 索引。

C. Jzzhu and Chocolate：貪心切巧克力

題意：n×m 巧克力切 k 刀（橫/豎），最大化最小塊面積。k > n+m-2 無解。

貪心策略：為使最小塊最大，應盡量集中切在一邊。枚舉兩種極端：

• 先切橫向：s1 = (k ≤ m-1) ? n*(m/(k+1)) : n/(k-m+2)
• 先切縱向：s2 = (k ≤ n-1) ? m*(n/(k+1)) : m/(k-n+2)
• 答案 max(s1, s2)

D. Jzzhu and Cities：最短路 + 可刪邊計數

題意：給定圖（含雙向邊）和 k 條從 1 號點出發的單向邊（權重 y）。求最多能刪除多少條單向邊，使所有點到 1 的最短距離不變。

解法：

1. 將所有單向邊中同終點保留最小權重，加入圖中
2. 從 1 點跑 Dijkstra/SPFA 求 dis[i] 和最短路條數 cnt[i]（>1 視為 2）
3. 對每條原始單向邊 (1, s, y)：
   • 若 dis[s] < y：該邊無用，可刪
   • 若 dis[s] == y 且 cnt[s] > 1：有其他最短路，可刪
   • 否則必須保留

答案 = k - 保留邊數。需用長長整型防溢出。

比賽心得

前三題屬於基礎題庫題型（模擬、找週期、貪心），D 題是經典「最短路樹邊必要性判定」，考察對最短路性質的深度理解。比賽中靈活運用模板、注意細節（如負數取模、長整型）是關鍵。