Bài A — Kiểm tra khả năng xây dựng chuỗi đích từ hai nguồn

Bài toán yêu cầu xác định xem có thể tạo chuỗi c độ dài n sao cho mỗi ký tự c[i] phải trùng khớp với ít nhất một trong hai ký tự a[i] hoặc b[i]. Nếu mọi vị trí đều thỏa mãn, kết quả là "NO" (tức là không tồn tại ký tự nào ở c mà không xuất hiện tại cùng chỉ số ở a hoặc b); ngược lại, in ra "YES".

#include <iostream>
#include <string>
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s1, s2, target;
        cin >> s1 >> s2 >> target;

        bool found_impossible = false;
        for (int i = 0; i < n; ++i) {
            if (target[i] != s1[i] && target[i] != s2[i]) {
                found_impossible = true;
                break;
            }
        }

        cout << (found_impossible ? "YES" : "NO") << '\n';
    }
    return 0;
}

Bài B — Đếm số tam giác hợp lệ từ dãy độ dài que

Một tam giác hợp lệ được hình thành bởi ba que thoả mãn một trong hai cấu trúc:

• Dạng đồng nhất: Ba que cùng độ dài → chọn 3 trong số cnt[x] que có độ dài x, số cách là C(cnt[x], 3).
• Dạng cân: Hai que cùng độ dài x, một que ngắn hơn y < x. Với mỗi giá trị x, tổng số cách bằng cnt[x] * (cnt[x] - 1) / 2 * (tổng số que có độ dài < x).

Sử dụng sắp xếp tăng dần và duyệt tuyến tính để duy trì tổng tiền tố của các độ dài đã gặp.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

ll nCr(ll n, ll r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    r = min(r, n - r);
    ll res = 1;
    for (ll i = 0; i < r; ++i) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> sticks(n);
        for (int &x : sticks) cin >> x;
        sort(sticks.begin(), sticks.end());

        map<int, int> freq;
        for (int x : sticks) freq[x]++;

        ll total = 0;
        ll prefix_count = 0;
        for (const auto& [length, count] : freq) {
            if (count >= 3) total += nCr(count, 3);
            total += prefix_count * nCr(count, 2);
            prefix_count += count;
        }
        cout << total << '\n';
    }
    return 0;
}

Bài C — Truy vấn chi phí di chuyển tối ưu giữa các điểm trên trục số

Cho dãy a[1..n] biểu diễn tọa độ các thành phố trên trục số. Với mỗi vị trí i, xác định thành phố gần nhất (so sánh khoảng cách tới a[i-1] và a[i+1], xử lý biên). Sau đó xây dựng hai mảng:

• pref[i]: tổng chi phí đi từ a[1] đến a[i] theo hướng tăng chỉ số, với chi phí giữa a[j-1] và a[j] là 1 nếu a[j-1] có thành phố gần nhất là a[j], ngược lại là |a[j] - a[j-1]|.
• suff[i]: tương tự nhưng theo hướng giảm chỉ số.

Với mỗi truy vấn (start, end), nếu end > start thì dùng pref[end] - pref[start], ngược lại dùng suff[end] - suff[start].

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> pos(n + 1);
        for (int i = 1; i <= n; ++i) cin >> pos[i];

        vector<int> nearest(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (i == 1) nearest[i] = 2;
            else if (i == n) nearest[i] = n - 1;
            else {
                ll left_dist = abs(pos[i] - pos[i - 1]);
                ll right_dist = abs(pos[i] - pos[i + 1]);
                nearest[i] = (left_dist <= right_dist) ? i - 1 : i + 1;
            }
        }

        vector<ll> pref(n + 1, 0), suff(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            if (nearest[i - 1] == i) pref[i] = pref[i - 1] + 1;
            else pref[i] = pref[i - 1] + abs(pos[i] - pos[i - 1]);
        }
        for (int i = n - 1; i >= 1; --i) {
            if (nearest[i + 1] == i) suff[i] = suff[i + 1] + 1;
            else suff[i] = suff[i + 1] + abs(pos[i] - pos[i + 1]);
        }

        int q;
        cin >> q;
        while (q--) {
            int u, v;
            cin >> u >> v;
            if (v > u) cout << pref[v] - pref[u] << '\n';
            else cout << suff[v] - suff[u] << '\n';
        }
    }
    return 0;
}