A. Xác định Ngày Đặc Biệt

Bài toán yêu cầu kiểm tra xem cặp số nguyên (a, b) có trùng với một trong các ngày cố định: (1,7), (3,3), (5,5), (7,7), hay (9,9). Nếu khớp, in ra "Yes", ngược lại in "No".

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

int main() {
    int day, month;
    cin >> day >> month;

    vector<pair<int, int>> special = {{1,7}, {3,3}, {5,5}, {7,7}, {9,9}};
    bool found = false;
    for (auto& p : special) {
        if (p.first == day && p.second == month) {
            found = true;
            break;
        }
    }

    cout << (found ? "Yes" : "No") << endl;
    return 0;
}

B. Vẽ Khung Hình Chữ Nhật

Cho kích thước chiều cao a và chiều rộng b, cần in ra một khung hình chữ nhật bằng ký tự '#', bên trong là khoảng trắng '.'. Hàng đầu và hàng cuối gồm toàn '#'; các hàng giữa bắt đầu và kết thúc bằng '#', phần giữa là '.'.

#include <iostream>
using namespace std;

int main() {
    int height, width;
    cin >> height >> width;

    // Hàng trên
    cout << string(width, '#') << '\n';

    // Các hàng giữa
    for (int i = 1; i < height - 1; ++i) {
        cout << '#' << string(width - 2, '.') << '#';
        if (i < height - 2) cout << '\n';
    }

    // Hàng dưới (nếu có hơn 1 hàng)
    if (height > 1) {
        cout << '\n' << string(width, '#');
    }

    return 0;
}

C. Kiểm Tra Chuỗi Trung Tâm

Cho danh sách m chuỗi và n ràng buộc dạng (độ dài mong muốn, vị trí ký tự, ký tự mong đợi). Với mỗi chuỗi s_i có độ dài đúng bằng n, ta kiểm tra liệu với mọi ràng buộc thứ j, tồn tại ít nhất một chuỗi khác trong danh sách có độ dài bằng a_j và ký tự tại vị trí b_j bằng s_i[b_j]. Sử dụng mảng đếm ba chiều cnt[len][pos][ch] để ghi nhận tần suất.

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

int main() {
    int n; cin >> n;
    vector<pair<int, int>> constraints(n);
    for (int i = 0; i < n; ++i) {
        cin >> constraints[i].first >> constraints[i].second;
        constraints[i].second--; // chuyển sang chỉ số 0-based
    }

    int m; cin >> m;
    vector<string> words(m);
    // Đếm: cnt[length][position][char_index]
    int cnt[15][15][26] = {};

    for (int i = 0; i < m; ++i) {
        cin >> words[i];
        int len = words[i].size();
        if (len < 15) {
            for (int j = 0; j < len; ++j) {
                char c = words[i][j];
                if (c >= 'a' && c <= 'z') {
                    cnt[len][j][c - 'a']++;
                }
            }
        }
    }

    for (const string& s : words) {
        if (s.length() != (size_t)n) {
            cout << "No\n";
            continue;
        }

        bool valid = true;
        for (int j = 0; j < n; ++j) {
            int req_len = constraints[j].first;
            int req_pos = constraints[j].second;
            char req_char = s[j];
            if (req_pos < 0 || req_pos >= 15 || req_len >= 15 ||
                req_char < 'a' || req_char > 'z' ||
                cnt[req_len][req_pos][req_char - 'a'] == 0) {
                valid = false;
                break;
            }
        }
        cout << (valid ? "Yes" : "No") << '\n';
    }

    return 0;
}

D. Đếm Đoạn Không Chứa Chuỗi Con

Với hai chuỗi S và T, đếm số đoạn con liên tiếp S[l..r] sao cho T không xuất hiện dưới dạng chuỗi con (không nhất thiết liên tục) trong đoạn đó. Giải pháp: với mỗi vị trí bắt đầu l, tìm vị trí nhỏ nhất pos sao cho S[l..pos] chứa T như một chuỗi con — sử dụng bảng next_pos[i][c] để truy vấn nhanh ký tự tiếp theo.

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

int main() {
    string S, T;
    cin >> S >> T;
    int lenS = S.size(), lenT = T.size();

    // Bảng next: next_pos[i][c] = vị trí nhỏ nhất >= i của ký tự c trong S
    vector<vector<int>> next_pos(lenS + 1, vector<int>(26, lenS));
    for (int i = lenS - 1; i >= 0; --i) {
        for (int c = 0; c < 26; ++c) {
            next_pos[i][c] = next_pos[i + 1][c];
        }
        next_pos[i][S[i] - 'a'] = i;
    }

    long long result = 0;
    for (int l = 0; l < lenS; ++l) {
        int ptr = l;
        bool complete = true;
        for (char c : T) {
            int idx = c - 'a';
            if (ptr >= lenS || next_pos[ptr][idx] == lenS) {
                complete = false;
                break;
            }
            ptr = next_pos[ptr][idx] + 1;
        }
        if (!complete) {
            result += lenS - l;
        } else {
            result += ptr - l - 1;
        }
    }

    cout << result << '\n';
    return 0;
}

E. Tổng Có Điều Kiện Trên Phép Chia Nguyên

Tính tổng: \[ \sum_{i=1}^{N}\sum_{j=1}^{M} A_i B_j \cdot (i \bmod j) \] Chuyển đổi thành: \[ \left(\sum_i i A_i\right)\left(\sum_j B_j\right) - \sum_j j B_j \left(\sum_i A_i \left\lfloor \frac{i}{j} \right\rfloor\right) \] Phần thứ hai được tính bằng cách chia miền giá trị của \(\left\lfloor i/j \right\rfloor\) thành các đoạn \([k \cdot j,\; (k+1) \cdot j - 1]\), rồi dùng mảng tổng tiền tố để lấy tổng \(A_i\) trên từng đoạn.

#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 998244353;

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

    int N, M;
    cin >> N >> M;

    vector<long long> A(N + 1), B(M + 1), prefix(N + 1);
    long long sumB = 0;

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        prefix[i] = (prefix[i - 1] + A[i]) % MOD;
    }
    for (int j = 1; j <= M; ++j) {
        cin >> B[j];
        sumB = (sumB + B[j]) % MOD;
    }

    long long ans = 0;

    // Phần đầu: sum(i * A_i) * sum(B_j)
    for (int i = 1; i <= N; ++i) {
        ans = (ans + i % MOD * A[i] % MOD * sumB) % MOD;
    }

    // Phần sau: sum_j [ j * B_j * sum_i A_i * floor(i/j) ]
    for (int j = 1; j <= M; ++j) {
        long long inner = 0;
        for (int k = 0; k * j <= N; ++k) {
            int left = max(1, k * j);
            int right = min(N, (k + 1) * j - 1);
            if (left <= right) {
                long long seg_sum = (prefix[right] - prefix[left - 1] + MOD) % MOD;
                inner = (inner + k % MOD * seg_sum) % MOD;
            }
        }
        ans = (ans - j % MOD * B[j] % MOD * inner % MOD + MOD) % MOD;
    }

    cout << ans << '\n';
    return 0;
}

F. Đếm Đoạn Con Với Số Nghịch Thế Cố Định

Đếm số đoạn con [l, r] của dãy A sao cho số nghịch thế trong đoạn đúng bằng k. Dùng kỹ thuật "hai con trỏ" kết hợp cây Fenwick (Binary Indexed Tree) để duy trì số nghịch thế khi mở rộng hoặc thu hẹp đoạn. Hàm count_at_most(k) trả về số đoạn có tối đa k nghịch thế; kết quả cuối là count_at_most(k) - count_at_most(k-1).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Fenwick {
    vector<long long> tree;
    int n;
    Fenwick(int size) : n(size), tree(size + 1) {}
    void update(int i, long long delta) {
        for (++i; i <= n; i += i & -i) tree[i] += delta;
    }
    long long query(int i) {
        long long res = 0;
        for (++i; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
    long long range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

long long count_at_most(const vector<int>& A, int k) {
    int n = A.size();
    vector<int> sorted = A;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int sz = sorted.size();

    auto get_id = [&](int x) {
        return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    };

    Fenwick bit(sz);
    long long inv = 0;
    long long ans = 0;
    int left = 0;

    for (int right = 0; right < n; ++right) {
        int id = get_id(A[right]);
        inv += bit.range_query(id + 1, sz - 1);
        bit.update(id, 1);

        while (inv > k && left <= right) {
            int lid = get_id(A[left]);
            bit.update(lid, -1);
            inv -= bit.range_query(0, lid - 1);
            ++left;
        }
        ans += right - left + 1;
    }
    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    cout << count_at_most(A, k) - count_at_most(A, k - 1) << '\n';
    return 0;
}