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

Codeforces 300 題解分析：A、B、C 三題完整解法

編輯：關於C++

前言

Codeforces Round 300 是一場經典的競賽，包含三道極具代表性的題目。本文將詳細解析 A、B、C 三題的核心思路與代碼實現，幫助讀者掌握分類討論、圖論建模與組合數學等關鍵技巧。

A 題：簡單分類統計

題目大意

給定 n 個整數，將其分為正數、負數、零三類，並按特定格式輸出每類的數量與元素。

解題思路

直接遍歷輸入，使用三個陣列分別存儲正數、負數、零。注意輸出格式：第一行輸出一個負數（若無負數則從零中取兩個轉為負數），第二行輸出所有正數，第三行輸出剩餘零與負數。時間複雜度 O(n)，空間複雜度 O(n)。

代碼關鍵點

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int n, cnt1, cnt2, cnt3, a[110];
    int b1[110], b2[110], b3[110];
    while (scanf("%d", &n) != EOF) {
        cnt1 = cnt2 = cnt3 = 0;
        for (int i = 0; i < n; i++) {
            int x; scanf("%d", &x);
            if (x < 0) b1[cnt1++] = x;
            else if (x > 0) b2[cnt2++] = x;
            else b3[cnt3++] = x;
        }
        // 輸出邏輯：確保第一行有一個負數
        printf("1 %d\n", b1[0]);
        if (cnt2 == 0) { // 無正數時從零中取兩個補充
            b2[cnt2++] = b3[--cnt3];
            b2[cnt2++] = b3[--cnt3];
        }
        printf("%d ", cnt2);
        for (int i = 0; i < cnt2; i++) printf("%d ", b2[i]);
        printf("\n%d ", cnt3 + 1);
        for (int i = 0; i < cnt3; i++) printf("%d ", b3[i]);
        printf("\n");
    }
    return 0;
}

B 題：組隊問題（DFS + 貪心）

題目大意

n 個學生需分成 n/3 支隊伍，每隊恰好 3 人。已知 m 對必須同隊的關係，判斷能否完成分組並輸出方案。

解題思路

用鄰接矩陣建圖，DFS 將必須同隊的學生標記為同一組（連通分量）。
檢查每組人數：若 >3 則無解；若 <3 從未分組學生中補充至 3 人。
最終驗證所有隊伍人數是否均為 3，輸出分組或 -1。

代碼關鍵點

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int M[50][50], vis[50];
int n, m;
void dfs(int x, int cnt) {
    vis[x] = cnt;
    for (int i = 1; i <= n; i++)
        if (M[x][i]) {
            M[x][i] = M[i][x] = 0;
            dfs(i, cnt);
        }
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(vis, 0, sizeof(vis));
        memset(M, 0, sizeof(M));
        for (int i = 1; i <= m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            if (a != b) M[a][b] = M[b][a] = 1;
        }
        int flag = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            int j;
            for (j = 1; j <= n; j++) if (M[i][j]) break;
            if (j <= n) dfs(i, ++cnt);
        }
        // 補充邏輯與驗證...
        if (flag) printf("-1\n");
        else {
            for (int i = 1; i <= n/3; i++) {
                for (int j = 1; j <= n; j++)
                    if (vis[j] == i) printf("%d ", j);
                printf("\n");
            }
        }
    }
    return 0;
}

C 題：構造與組合數學（費馬小定理）

題目大意

枚舉構造結果並驗證合法性，核心涉及組合數計算：C(n, k) 模素數 mod = 1e9+7。

核心公式

利用費馬小定理求逆元：(a/b) % mod = a * pow(b, mod-2) % mod，其中 pow 為快速冪。

解題步驟

預處理階乘 f[i] = i! % mod。
枚舉 i (0~n)，計算 sum = i*a + (n-i)*b。
若 sum 的每位數字均為 a 或 b，則累加 C(n, i) 到答案。

代碼關鍵點

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 1000000007
#define ll long long
ll f[1000009];
ll pow_mod(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return ans;
}
bool check(ll x) {
    while (x) {
        int d = x % 10;
        if (d != a && d != b) return false;
        x /= 10;
    }
    return true;
}
int main() {
    f[0] = 1;
    for (int i = 1; i <= 1000001; i++) f[i] = f[i-1] * i % mod;
    while (scanf("%d%d%d", &a, &b, &n) != EOF) {
        ll ans = 0;
        for (int i = 0; i <= n; i++) {
            ll sum = (ll)i * a + (ll)(n - i) * b;
            if (check(sum)) {
                ll d = f[i] * f[n - i] % mod;
                ans = (ans + f[n] * pow_mod(d, mod - 2) % mod) % mod;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}