A - Full House 2

Yêu cầu

Cho 4 số nguyên, hỏi có thể thêm một số nguyên để có đúng 3 số a và 2 số b không?

Cách giải

Sử dụng mô phỏng

Mã nguồn

Xem mã nguồn

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    map<int, int> m;
    m[A]++;
    m[B]++;
    m[C]++;
    m[D]++;
    int countA = 0, countB = 0;

    for (const auto& i : m) {
        if (i.second == 3) {
            countA++;
        } else if (i.second == 2) {
            countB++;
        }
    }
    if (countA > 0 || countB >= 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}

B - Máy tính

Yêu cầu

Các ký tự cơ bản là "00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9". Cho chuỗi s, tìm số lượng ít nhất của các ký tự cơ bản cần để tạo ra s.

Cách giải

Sử dụng mô phỏng

Mã nguồn

Xem mã nguồn

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;
    if (s.find('0') == -1) {
        cout << s.size();
        return;
    }
    int cnt = 0, ans = s.size();
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            if (cnt) {
                cnt = 0;
                ans--;
            } else {
                cnt++;
            }
        } else {
            cnt = 0;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}

C - Thao tác 1 lần

Yêu cầu

Trong chuỗi s, thực hiện tối đa 1 thao tác: chèn, xóa, hoặc thay thế một ký tự. Kiểm tra xem có thể biến s thành t không.

Cách giải

Do chỉ được thao tác 1 lần, độ dài của s và t có thể khác nhau tối đa 1 (thêm/xóa). Nếu độ dài bằng nhau, chỉ có thể có tối đa 1 ký tự khác nhau (thay thế).

Mã nguồn

Xem mã nguồn

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int k;
    string s, t;
    cin >> k >> s >> t;
    if (s == t) {
        cout << "Yes" << endl;
        return;
    }
    int lenS = s.size(), lenT = t.size();
    if (abs(lenS - lenT) > 1) {
        cout << "No" << endl;
        return;
    }
    if (lenS == lenT) {
        int diff = 0;
        for (int i = 0; i < lenS; i++) {
            if (s[i] != t[i]) {
                diff++;
                if (diff > 1) {
                    cout << "No" << endl;
                    return;
                }
            }
        }
        cout << "Yes" << endl;
        return;
    }
    int diff = 0;
    for (int i = 0, j = 0; i < s.size() && j < t.size(); i++, j++) {
        if (s[i] != t[j]) {
            diff++;
            if (diff > 1) {
                cout << "No" << endl;
                return;
            }
            if (s.size() > t.size()) {
                i++;
            } else {
                j++;
            }
        }
    }
    cout << "Yes" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}

D - Phân cách đường chéo

Yêu cầu

Cho lưới n×n, ban đầu có m ô được tô màu (cho biết x, y và màu). Cần tô tất cả các ô thành đen hoặc trắng sao cho: mỗi hàng có một i sao cho ô thứ i và bên trái nó đều đen, còn lại trắng; mỗi cột có một j sao cho ô thứ j và bên trên nó đều đen, còn lại trắng. Hỏi có thể thỏa mãn yêu cầu không?

Cách giải

Đối với ô đen, khu vực bên trái và bên trên không được có ô trắng. Chỉ cần ghi nhớ vị trí gần nhất của ô trắng, kiểm tra có ô đen ở bên phải hoặc bên dưới không.

Mã nguồn

Xem mã nguồn

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y;
    char color;
    bool operator < (const Node& a) const {
        if (x == a.x) {
            return y < a.y;
        }
        return x < a.x;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<Node> v(m);
    for (int i = 0; i < m; i++) {
        int x, y;
        char color;
        cin >> x >> y >> color;
        x--, y--;
        v[i].x = x, v[i].y = y, v[i].color = color;
    }
    sort(v.begin(), v.end());
    int minY = 1e18;
    for (int i = 0; i < m; i++) {
        int x = v[i].x;
        int y = v[i].y;
        char color = v[i].color;
        if (color == 'W') {
            minY = min(minY, y);
        } else if (minY <= y) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}

E - Tối đa XOR

Yêu cầu

Cho dãy số không âm A có kích thước n, chọn k phần tử để thực hiện phép XOR, tìm giá trị lớn nhất có thể.

Cách giải

Nếu k nhỏ, có thể sử dụng đệ quy (dfs). Nếu k lớn, tính tổng XOR của tất cả các phần tử, sau đó duyệt qua các phần tử không cần thiết.

Mã nguồn

Xem mã nguồn

#include <bits/stdc++.h>
using namespace std;

int n, k, result = -1;
vector<int> a;

void dfs(int p, int res, int m) {
    if (m == 0) {
        result = max(result, res);
        return;
    }
    if (p == n) {
        return;
    }
    dfs(p + 1, res ^ a[p], m - 1);
    dfs(p + 1, res, m);
}

void solve() {
    int totalXOR = 0;
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        totalXOR ^= a[i];
    }
    if (k <= n - k) {
        dfs(0, 0, k);
    } else {
        dfs(0, totalXOR, n - k);
    }
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while (T--) {
        solve();
    }

    return 0;
}