Codeforces Round #296 (Div. 2) A/B/C/D 題解彙總

A. 最大公約數步數計數

輸入 a,b，輸出輾轉相除法商之和。實際為 `gcd(a,b)` 過程中 `a/b` 累加。遞歸實現：

ll gcd(ll a, ll b) {
    if (!b) return a;
    ans += a / b;
    return gcd(b, a % b);
}

B. 字符串最小修改使相等

兩字符串 s,t 長度 n。允許交換 s 中任意兩字符一次，求最小差異位數。
策略：統計差異位。若存在 i,j 使 s[i]=t[j] 且 s[j]=t[i] → 差異減 2。
否則若存在 i,j 使 s[i]=t[j] 或 s[j]=t[i] → 減 1。
否則不變。代碼用數組 `g[26][26]` 記錄配對。

C. 玻璃切割 (Codeforces 527C 同題)

矩形 w×h，依次垂直/水平切割。每次切割後求最大塊面積。
用兩個 `set` 維護切割座標，兩個 `multiset` 維護段長。切割時更新：移除原段長，插入兩新段長。答案 = 最大寬段 × 最大高段。

D. 區間不重疊最大子集

每個物品對應區間 [x-w, x+w]。求最大不重疊區間數。貪心：按右端點排序，依次選取右端點最小且不重疊的區間。經典活動安排問題。

代碼彙總

四題代碼均在原文中，均為 O(n log n) 或 O(n) 解法，屬於 Div. 2 常規難度。