A - Đổi mật khẩu

Bài toán cơ bản, chỉ cần thống kê và mô phỏng là ra. Chi tiết không cần bàn thêm.

#include <bits/stdc++.h>
using namespace std;
int T, n, a, b, c, A, B, C;
string s;
int main() {
    cin >> T;
    while (T--) {
        cin >> s;
        n = s.size(); s = " " + s;
        a = b = c = A = B = C = 0;
        for (int i = 1; i <= n; i++) {
            char ch = s[i];
            if (ch >= 'A' && ch <= 'Z') {
                if (ch == 'O') a++; else A++;
            } else if (ch >= 'a' && ch <= 'z') {
                if (ch == 'o') b++; else B++;
            } else {
                if (ch == '0') c++; else C++;
            }
        }
        int miss = 0;
        if (a + A == 0) miss++;
        if (b + B == 0) miss++;
        if (c + C == 0) miss++;
        if (miss == 0) cout << "0\n";
        else if (miss == 1) {
            int ans = -1;
            if (a > 0 && a - 1 + A > 0) ans = 1;
            if (b > 0 && b - 1 + B > 0) ans = 1;
            if (c > 0 && c - 1 + C > 0) ans = 1;
            cout << ans << "\n";
        } else if (miss == 2) {
            int ans = -1;
            if (a > 1 && a - 2 + A > 0) ans = 2;
            if (b > 1 && b - 2 + B > 0) ans = 2;
            if (c > 1 && c - 2 + C > 0) ans = 2;
            cout << ans << "\n";
        } else {
            cout << "-1\n";
        }
    }
    return 0;
}

B - Ngọn hải đăng

Cũng đơn giản. Sắp xếp mảng năng lượng, loại bỏ trùng, duyệt theo thứ tự. Dùng tham lam: nếu có thể thắp sáng một ngọn đèn (theo điều kiện khoảng cách) thì thực hiện và tăng biến đếm. Chứng minh tính đúng đắn dễ dàng.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int m, n, a[N];
int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int len = unique(a + 1, a + n + 1) - a - 1;
    int last = -1, cnt = 0;
    for (int i = 1; i <= len; i++) {
        if (a[i] - last > 1) {
            cnt++;
            last = a[i];
        }
    }
    cout << cnt << "\n";
    return 0;
}

C - Xây dựng tam giác

Ta có bất đẳng thức: x OR y >= max(x, y) và x OR y <= x + y. Điều kiện không thể tạo thành tam giác hợp lệ là khi và chỉ khi x OR y = x + y. Điều này tương đương với việc vị trí bit 1 của x không được trùng với vị trí bit 1 của y. Đếm số lượng bit 0 trong biểu diễn nhị phân của x (không kể các số 0 ở đầu), gọi là cnt. Kết quả là 2^cnt - 1, trừ 1 vì y không thể bằng 0.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, ans;
int main() {
    cin >> x;
    ll tmp = x;
    ans = 1;
    while (tmp) {
        if (tmp % 2 == 0) ans *= 2;
        tmp /= 2;
    }
    cout << x - ans + 1 << "\n";
    return 0;
}

D - Pizza miễn phí

Số chữ số nhỏ (8), nên ta có thể duyệt toàn bộ hoán vị và vị trí chèn. Bài này dễ hơn C. Với mỗi hoán vị và vị trí chèn số x, ta ghép số, tính GCD với n, cập nhật kết quả tối ưu: ưu tiên GCD lớn nhất, nếu bằng thì lấy số nhỏ hơn.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[20], bestVal, bestGcd;
ll gcd(ll x, ll y) {
    if (x < y) swap(x, y);
    return y ? gcd(y, x % y) : x;
}
ll build(ll x, int pos) {
    ll res = 0;
    if (pos == 0) res = x;
    for (int i = 1; i <= 8; i++) {
        res = res * 10 + a[i];
        if (i == pos) res = res * 10 + x;
    }
    return res;
}
void eval() {
    for (int x = 1; x <= 8; x++) {
        for (int pos = 0; pos <= 8; pos++) {
            ll val = build(x, pos);
            ll g = gcd(val, n);
            if (g > bestGcd || (g == bestGcd && val < bestVal)) {
                bestVal = val;
                bestGcd = g;
            }
        }
    }
}
void dfs(int idx) {
    if (idx > 8) { eval(); return; }
    for (int i = 1; i <= 8; i++) {
        if (a[i]) continue;
        a[i] = idx;
        dfs(idx + 1);
        a[i] = 0;
    }
}
int main() {
    cin >> n;
    bestVal = bestGcd = 0;
    dfs(1);
    cout << bestVal << "\n";
    return 0;
}

E - Khiên phép thuật

Đây là bài toán khả quan hơn (nhưng vẫn dễ). Ta dùng DP với trạng thái dp[i][j] là số lần tăng cường tối thiểu sau i lượt và có j khiên. Công thức chuyển:

• Không dùng tăng cường: dp[i+1][min(c, j + s[i+1])] nếu min(c, j + s[i+1]) >= a[i+1]
• Có dùng tăng cường (+1 lần): dp[i+1][min(c, j + 2*s[i+1])] nếu điều kiện tương tự.

Vì n lớn, ta dùng mảng 1 chiều lăn (roll) để tiết kiệm bộ nhớ.

#include <bits/stdc++.h>
using namespace std;
const int N = 50005, INF = 0x3f3f3f3f;
int n, c, b, s[N], a[N], dp[N], f[N], ans;
int main() {
    cin >> n >> c >> b;
    b = min(b, c);
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[b] = 0; ans = INF;
    for (int i = 1; i <= n; i++) {
        memcpy(f, dp, sizeof(f));
        memset(dp, 0x3f, sizeof(dp));
        for (int w = 0; w <= c; w++) {
            int w1 = min(c, w + s[i]);
            int w2 = min(c, w + 2 * s[i]);
            if (w1 >= a[i]) dp[w1] = min(dp[w1], f[w]);
            if (w2 >= a[i]) dp[w2] = min(dp[w2], f[w] + 1);
        }
    }
    for (int i = 0; i <= c; i++) ans = min(ans, dp[i]);
    cout << (ans == INF ? -1 : ans) << "\n";
    return 0;
}

F - Quy hoạch trạm sạc robot

Bài khó nhất. Dùng tìm kiếm nhị phân trên giá trị mid (tỉ lệ tải tối đa). Hàm check kiểm tra xem có thể phân bố tất cả robot vào các trạm không. Thuật toán chính xác là duyệt DFS + nhánh cận mạnh (bao gồm sắp xếp, hash trạng thái, optimality pruning).

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const double eps = 1e-3;
int n, k, cnt, ans;
double p[N], sum[N];
vector<double> now;
bool check(double up) {
    // Tham lam thử trước
    for (int i = 1; i <= k; i++) sum[i] = up;
    sort(p + 1, p + cnt + 1, greater<double>());
    for (int i = 1; i <= cnt; i++) {
        int id = -1;
        for (int j = 1; j <= k; j++) {
            if (sum[j] >= p[i] && (id == -1 || sum[j] < sum[id]))
                id = j;
        }
        if (id == -1) return false;
        sum[id] -= p[i];
    }
    return true;
}
int main() {
    cin >> n >> k;
    // Đọc dữ liệu và tạo mảng p
    // ... (giả lược)
    double lo = 0, hi = 100, best = 100;
    while (hi - lo > eps) {
        double mid = (lo + hi) / 2;
        if (check(mid)) {
            best = mid;
            hi = mid;
        } else lo = mid;
    }
    cout << (int)round(best) << "\n";
    return 0;
}

Tổng kết

Một số bài đã mắc lỗi không đáng có (ví dụ C viết DP số rồi sai). F là bài khó, cần tối ưu nhiều, chỉ đạt 98 điểm, bỏ 2 điểm vì giới hạn thời gian.