Codeforces Round #274 (Div. 2) 題目原文與解法詳解

A 題：Expression

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

解法：只有 6 種合法表達式，直接枚舉求最大值。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define LL long long
const int MOD = 1e9+7;
using namespace std;

int main() {
    int a, b, c;
    while (cin >> a >> b >> c) {
        int d = a + b * c;
        int e = a * (b + c);
        int f = a * b * c;
        int g = (a + b) * c;
        int h = a + b + c;
        int Max = max(h, max(d, max(max(e, f), g)));
        cout << Max << endl;
    }
    return 0;
}

B 題：Towers

題目大意：n 座塔，高度 ai。每次操作將一塊方塊從某塔移到另一塔，最多 k 次。不穩定度 = 最高塔 - 最低塔。求最小不穩定度及操作序列。

解法：暴力排序模擬。每次排序，將最高塔移一塊到最低塔。若移動後最高 < 最低則停止。

struct Node { int x, id; } d[200];
struct Op { int a, b; } p[10005];

bool cmp(Node a, Node b) { return a.x < b.x; }

int main() {
    int n, k;
    while (cin >> n >> k) {
        for (int i = 1; i <= n; i++) { cin >> d[i].x; d[i].id = i; }
        int cha = 0, cent = 0;
        sort(d + 1, d + n + 1, cmp);
        int m = 0;
        for (int i = 0; i < k; i++) {
            if (d[1].x + 1 > d[n].x - 1) { cha = d[n].x - d[1].x; break; }
            d[1].x += 1; d[n].x -= 1;
            cent++;
            p[m].a = d[n].id; p[m++].b = d[1].id;
            sort(d + 1, d + n + 1, cmp);
            cha = d[n].x - d[1].x;
        }
        cout << cha << " " << cent << endl;
        for (int i = 0; i < m; i++) cout << p[i].a << " " << p[i].b << endl;
    }
    return 0;
}

C 題：Exams

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

解法：按 ai 升序、bi 升序排序。貪心掃描：當前日期 last，若 bi ≥ last 選 bi，否則選 ai。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
P p[5010];

bool cmp(P a, P b) {
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
        sort(p, p + n, cmp);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (p[i].second >= ans) ans = max(ans, p[i].second);
            else ans = max(ans, p[i].first);
        }
        cout << ans << endl;
    }
    return 0;
}

D 題：Long Jumps

題目大意：尺子長度 l，n 個刻度 (a1=0, an=l)。需測量 x 和 y (x < y)。可添加最少整數刻度使兩者均可測量。

解法：答案 ∈ {0,1,2}。用二分查找檢查現有刻度能否測出 x, y。若不能，嘗試添加 1 個刻度（檢查 a[i]±x, a[i]±y, a[i]+x-y, a[i]+y-x 等位置）。否則直接添加 x, y。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
int n, l, x, y;

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

bool check1() {
    for (int i = 0; i < n; i++) {
        if (binary_search(a, a+n, a[i]+x) && a[i]+y >= 0 && a[i]+y <= l) { cout << 1 << endl << a[i]+y << endl; return true; }
        if (binary_search(a, a+n, a[i]+y) && a[i]+x >= 0 && a[i]+x <= l) { cout << 1 << endl << a[i]+x << endl; return true; }
        if (binary_search(a, a+n, a[i]+y-x) && a[i]-x >= 0 && a[i]-x <= l) { cout << 1 << endl << a[i]-x << endl; return true; }
        if (binary_search(a, a+n, a[i]-y+x) && a[i]+x >= 0 && a[i]+x <= l) { cout << 1 << endl << a[i]+x << endl; return true; }
        if (binary_search(a, a+n, a[i]+x+y) && a[i]+x+y >= 0 && a[i]+x+y <= l) { cout << 1 << endl << a[i]+x+y << endl; 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; }
        else if (!check1()) { cout << 2 << endl << x << " " << y << endl; }
    }
    return 0;
}