Codeforces Round #274 (Div. 2) 解題報告：A-D 題完整分析

比賽概況

Codeforces Round #274 (Div. 2) 四道題目難度適中，本文提供完整解題思路與代碼實現。

A 題：Expression（表達式最大值）

題意：給定三個正整數 a, b, c (1 ≤ a,b,c ≤ 10)，在它們之間插入 +、* 和括號，求最大值。不能改變數字順序。

解法：枚舉所有 6 種合法表達式：

• a + b + c
• a * b * c
• (a + b) * c
• a * (b + c)
• a + b * c
• a * b + c

取最大值即可。數據範圍極小，直接暴力枚舉。

#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long

int main() {
    LL a, b, c, d[6];
    while (cin >> a >> b >> c) {
        d[0] = a * b * c;
        d[1] = (a + b) * c;
        d[2] = a + b + c;
        d[3] = a * (b + c);
        d[4] = a + b * c;
        d[5] = a * b + c;
        sort(d, d + 6);
        cout << d[5] << endl;
    }
    return 0;
}

B 題：Towers（塔的不穩定度）

題意：n 座塔，每次操作將最高塔頂部方塊移到最低塔，最多 k 次操作，求最小不穩定度（最高-最低）及操作序列。

解法：貪心 + 排序模擬。每次排序，將最高塔移一塊到最低塔，記錄操作。若最高-最低 ≤ 1 提前結束。

struct Node { int h, id; } a[105];
struct Op { int from, to; } ans[1005];

bool cmp(Node x, Node y) { return x.h < y.h; }

int main() {
    int n, k; 
    while (cin >> n >> k) {
        for (int i = 1; i <= n; i++) { cin >> a[i].h; a[i].id = i; }
        int m = 0;
        for (int i = 0; i < k; i++) {
            sort(a + 1, a + n + 1, cmp);
            if (a[1].h + 1 > a[n].h - 1) break;
            a[1].h++; a[n].h--;
            ans[++m] = {a[n].id, a[1].id};
        }
        sort(a + 1, a + n + 1, cmp);
        cout << a[n].h - a[1].h << " " << m << endl;
        for (int i = 1; i <= m; i++) cout << ans[i].from << " " << ans[i].to << endl;
    }
    return 0;
}

C 題：Exams（考試安排）

題意：n 門考試，第 i 門考試計劃日期 ai，可提前至 bi (bi < ai)。考試記錄按 ai 記錄，要求記錄日期非遞減，求最後考試最早日期。

解法：按 ai 升序、bi 升序排序。貪心掃描：維護當前日期 last，若 bi ≥ last 則選 bi，否則選 ai。last 取所選日期的最大值。

struct Exam { int a, b; } e[5005];
bool cmp(Exam x, Exam y) {
    if (x.a != y.a) return x.a < y.a;
    return x.b < y.b;
}

int main() {
    int n; 
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> e[i].a >> e[i].b;
        sort(e, e + n, cmp);
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (e[i].b >= last) last = e[i].b;
            else last = e[i].a;
        }
        cout << last << endl;
    }
    return 0;
}

D 題：Long Jumps（長跳測試）

題意：尺子長度 l，有 n 個刻度。需測量距離 x 和 y (x < y)。可添加最少刻度使兩者均可測量。輸出添加數量和位置。

解法：答案只能是 0, 1, 2。檢查現有刻度能否測出 x, y（二分查找）。若不能，嘗試添加 1 個刻度使兩者同時可測（檢查 a[i]±x, a[i]±y, a[i]+x-y 等位置）。否則添加 x 和 y 兩個刻度。

const int MAXN = 100005;
int a[MAXN], n, l, x, y;

bool check0() {
    bool fx = false, fy = false;
    for (int i = 0; i < n; i++) {
        if (binary_search(a, a+n, a[i]+x)) fx = true;
        if (binary_search(a, a+n, a[i]+y)) fy = true;
    }
    return fx && fy;
}

bool check1(int &pos) {
    for (int i = 0; i < n; i++) {
        // 嘗試在 a[i]+x 處添加刻度，檢查能否測出 y
        if (a[i]+x <= l && binary_search(a, a+n, a[i]+x+y)) { pos = a[i]+x; return true; }
        if (a[i]+x <= l && binary_search(a, a+n, a[i]+x-y)) { pos = a[i]+x; return true; }
        if (a[i]-x >= 0 && binary_search(a, a+n, a[i]-x+y)) { pos = a[i]-x; return true; }
        if (a[i]+y <= l && binary_search(a, a+n, a[i]+y-x)) { pos = a[i]+y; return true; }
        // 直接添加 x 或 y
        if (a[i]+x <= l && binary_search(a, a+n, a[i]+x)) { pos = a[i]+x; return true; }
        if (a[i]+y <= l && binary_search(a, a+n, a[i]+y)) { pos = a[i]+y; return true; }
    }
    return false;
}

int main() {
    while (cin >> n >> l >> x >> y) {
        for (int i = 0; i < n; i++) cin >> a[i];
        if (check0()) { cout << 0 << endl; continue; }
        int pos;
        if (check1(pos)) { cout << 1 << endl << pos << endl; }
        else { cout << 2 << endl << x << " " << y << endl; }
    }
    return 0;
}