Codeforces Round #243 (Div.2) 題解：A/B/C 三題詳解

A 題：Sereja and Mugs (426A)

問題

n-1 個朋友，n 個杯子，每杯有水。每位朋友選一杯喝，問總飲水量是否 ≤ S。

解法

排序杯子容量，前 n-1 小的杯子總和若 ≤ S 則 YES，否則 NO。

sort(mug+1, mug+1+n);
int sum = 0;
for (int i = 1; i < n; i++) {
    sum += mug[i];
    if (sum > s) break;
}
printf(i < n ? "NO\n" : "YES\n");

B 題：Sereja and Mirroring (426B)

問題

給定矩陣，若當前行數為偶數且上半部與下半部鏡像對稱，則可「折疊」去掉下半部。重複直到不可折疊，輸出最終行數。

解法

模擬折疊過程：檢查前半段與後半段是否逐行相等。

bool check(int x) {
    if (x & 1) return false;
    for (int i = 1, j = x; i < j; i++, j--)
        if (s[i] != s[j]) return false;
    return true;
}
while (n % 2 == 0 && check(n)) n /= 2;
printf("%d\n", n);

C 題：Sereja and Swaps (425A)

問題

n 個數，最多交換 k 次，求最大連續子段和。

解法：枚舉區間 + 優先隊列貪心替換

n ≤ 200，可枚舉所有區間 [l, r]。對於固定區間，用最小堆維護區間內元素；每次從區間外挑選最大元素，若大於堆頂則替換，最多 k 次。

int cal(int l, int r) {
    priority_queue<int, vector<int>, greater<int>> q;
    int ret = 0;
    for (int i = l; i <= r; i++) { ret += a[i]; q.push(a[i]); }
    int ktmp = k;
    while (ktmp--) {
        int maxt = -INF, maxv = -1;
        for (int i = 1; i <= n; i++)
            if ((i < l || i > r) && !vis[i] && a[i] > maxt)
                maxt = a[i], maxv = i;
        if (maxt > q.top()) {
            ret = ret - q.top() + maxt;
            vis[maxv] = true;
            q.pop(); q.push(maxt);
        }
    }
    return ret;
}

枚舉所有 l, r 取最大值。複雜度 O(n^3 log n)，對 n=200 可接受。

總結

• A 題：排序 + 前綴和，O(n log n)
• B 題：模擬折疊，O(n^2 m)（m 為列數）
• C 題：枚舉區間 + 貪心替換，O(n^3 log n)