您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Codeforces Round #303 (Div. 2) 題解匯總 (A~E)

編輯：關於C++

比賽概覽

Codeforces Round #303 (Div. 2) 包含五道題目，涵蓋模擬、貪心、動態規劃、排序、最短路樹構造等經典技巧。以下逐題給出核心思路與關鍵代碼片段。

A. 簡單模擬

題意：給定 n×n 矩陣，元素為 -1, 0, 1, 2。規則：
1 或 2 表示該行/列「不合格」；3 表示兩者都不合格。求所有合格的行索引。

做法：直接掃描矩陣，標記不合格行。O(n²)。

for (int i = 1; i <= n; ++i) ok[i] = 1;
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
        if (mat[i][j] == -1 || mat[i][j] == 0) continue;
        if (mat[i][j] == 1) ok[i] = 0;
        else if (mat[i][j] == 2) ok[j] = 0;
        else ok[i] = ok[j] = 0;
    }

B. 字符串構造

題意：給兩個等長字符串 s, t，需構造字符串 r，使 r 與 s、t 在不同位置的數量相同。若不可能輸出 impossible。

做法：統計 s[i] ≠ t[i] 的位置數 cnt。若 cnt 為奇數則無解。否則前 cnt/2 取 s[i]，後 cnt/2 取 t[i]，相同位置直接取該字符。O(n)。

int cnt = 0;
for (int i = 0; i < len; ++i) if (s[i] != t[i]) ++cnt;
if (cnt & 1) puts("impossible");
else {
    bool flip = false;
    for (int i = 0; i < len; ++i) {
        if (s[i] == t[i]) putchar(s[i]);
        else { putchar(flip ? t[i] : s[i]); flip = !flip; }
    }
    puts("");
}

C. 砍樹 DP

題意：n 棵樹，第 i 棵位置 x_i、高度 h_i。每棵樹可選：不砍、向左倒、向右倒。倒下區間不能覆蓋其他樹位置。求最大砍倒數。

狀態定義：dp[i][0/1/2] 表示前 i 棵樹，第 i 棵狀態為不砍/左倒/右倒的最大砍倒數。
轉移需檢查區間重疊：
- 左倒：x_i - h_i > 前一棵樹的右端點
- 右倒：x_i + h_i < x_i+1 (或 i=n)

dp[1][1] = 1;
if (x[1] + h[1] < x[2]) dp[1][2] = 1;
for (int i = 2; i <= n; ++i) {
    dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
    if (x[i] - h[i] > x[i-1]) dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + 1;
    if (x[i] - h[i] > x[i-1] + h[i-1]) dp[i][1] = max(dp[i][1], dp[i-1][2] + 1);
    if (i == n || x[i] + h[i] < x[i+1]) {
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 1;
        if (x[i-1] + h[i-1] < x[i]) dp[i][2] = max(dp[i][2], dp[i-1][2] + 1);
    }
}

D. 排序貪心

題意：給 n 個數，選最多多少個數使得其和不超過後面選的每一個數？等價於：排序後，維護前綴和 sum，若 sum ≤ a[i] 則可選，sum += a[i]。

sort(a+1, a+n+1);
int sum = 0, ans = 0;
for (int i = 1; i <= n; ++i)
    if (sum <= a[i]) { ++ans; sum += a[i]; }

E. 最短路樹構造 (Dijkstra 變體)

題意：給無向圖，從源點 s 跑 Dijkstra。每次鬆弛時，若距離相同則選邊權較小的邊。最終輸出最短路樹的邊權和與邊編號。

關鍵點：
- 用 cost[v] 記錄到達 v 的最後一條邊權。
- 鬆弛時：if (d[v] > nd) { d[v]=nd; cost[v]=w; use[v]=id; } else if (d[v]==nd && cost[v] > w) { cost[v]=w; use[v]=id; }
- 最後遍歷所有邊，vis[id] 標記樹邊，邊權和除以 2（無向圖每條邊存兩次）。
- 距離用 long long，初始值 1LL<<60。

void Dijkstra(int s) {
    d[s] = 0; cost[s] = 0;
    priority_queue, greater> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != d[u]) continue;
        vis[use[u]] = true;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w, id = e[i].id;
            if (d[v] > du + w) {
                d[v] = du + w; cost[v] = w; use[v] = id;
                pq.push({d[v], v});
            } else if (d[v] == du + w && cost[v] > w) {
                cost[v] = w; use[v] = id;
            }
        }
    }
}