Bài toán B: Tìm quy luật trong dãy số

Cho một dãy a có độ dài k. Dựa trên yêu cầu của đề bài, hãy xây dựng một dãy b có độ dài n. Câu hỏi là: có bao nhiêu cặp chỉ số (i, i+1) thỏa mãn bi % m ≤ bi+1 % m?

Vì phạm vi dữ liệu quá lớn, rõ ràng không thể giải quyết bằng phương pháp vét cạn. Đầu tiên, chúng ta có thể lấy phần dư của mỗi phần tử trong dãy a khi chia cho m, điều này không ảnh hưởng đến kết quả cuối cùng. Bằng cách thử nghiệm với các ví dụ, ta nhận thấy rằng khi bi + aj > m, thì bi-1 > bi. Do đó, số lần dãy b giảm (tức là bi-1 > bi) bằng bn / m, trong đó bn là tổng của dãy b. Vậy, số lần dãy b không giảm (tức là bi % m ≤ bi+1 % m) chính là n - bn / m.

#include <iostream>
using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 10;

ll day_a[MAXN], tong_tu_dau[MAXN];
ll so_dong_a, do_dai_b, so_chia, gia_tri_cuoi;

void giai_bai_toan() {
    cin >> so_dong_a;
    for (int i = 1; i <= so_dong_a; ++i) {
        cin >> day_a[i];
    }
    cin >> do_dai_b >> so_chia >> gia_tri_cuoi;

    // Lấy phần dư của dãy a
    for (int i = 1; i <= so_dong_a; ++i) {
        day_a[i] %= so_chia;
    }

    // Tính tổng tiền tố của dãy a
    for (int i = 1; i <= so_dong_a; ++i) {
        tong_tu_dau[i] = tong_tu_dau[i - 1] + day_a[i];
    }

    ll tong_day_a = tong_tu_dau[so_dong_a];
    ll du_cua_tong_a = tong_day_a % so_chia;
    ll so_lan_chia_het = tong_day_a / so_chia;
    ll so_lan_lap_lai = do_dai_b / so_dong_a;

    // Tính số lần dãy b giảm
    ll so_lan_giam = so_lan_lap_lai * so_lan_chia_het;
    so_lan_giam += (so_lan_lap_lai * du_cua_tong_a + gia_tri_cuoi % so_chia) / so_chia;
    so_lan_giam += tong_tu_dau[do_dai_b % so_dong_a] / so_chia;

    // Kết quả là số lần dãy b không giảm
    cout << do_dai_b - so_lan_giam << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    giai_bai_toan();
    return 0;
}

Bài toán C: Trò chơi với các đống sỏi

Cho n đống sỏi. Trong mỗi lượt, người chơi có thể lấy đi một số lượng sỏi bằng lũy thừa của p. Nếu người đi trước thắng, hãy in ra "GOOD", ngược lại in ra "BAD".

Đối với các bài toán trò chơi, chúng ta thường phải tìm quy luật. Ban đầu, có thể viết một hàm SG cơ bản để tạo bảng và tìm ra quy luật (vì việc tính SG trực tiếp sẽ quá tốn thời gian, chúng ta cần tối ưu hàm SG). Sau khi phân tích, ta có thể rút ra các quy tắc sau:

• Nếu p là số lẻ: Giá trị SG của một đống sỏi x bằng 1 nếu x lẻ, và bằng 0 nếu x chẵn.
• Nếu p là số chẵn:
  • Giá trị SG của x bằng 2 nếu x bằng chính p.
  • Giá trị SG của x bằng 1 nếu x lẻ.
  • Giá trị SG của x bằng 0 nếu x chẵn.

Dựa trên các quy tắc này, chúng ta có thể tối ưu hàm SG và giải quyết bài toán bằng cách tính XOR của các giá trị SG của tất cả các đống sỏi.

#include <iostream>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;

int so_dong_soi, co_so_luy_thua;
ll so_soi[MAXN];

int ham_sg(ll x) {
    if (x == co_so_luy_thua) {
        return 2;
    }
    // Nếu x lẻ, trả về 1; nếu chẵn, trả về 0
    return (x & 1);
}

void giai_bai_toan() {
    cin >> so_dong_soi >> co_so_luy_thua;
    ll ket_qua_xor = 0;

    if (co_so_luy_thua % 2 == 1) {
        // Trường hợp p là số lẻ
        for (int i = 0; i < so_dong_soi; ++i) {
            cin >> so_soi[i];
            ket_qua_xor ^= (so_soi[i] & 1);
        }
    } else {
        // Trường hợp p là số chẵn
        for (int i = 0; i < so_dong_soi; ++i) {
            cin >> so_soi[i];
            ket_qua_xor ^= ham_sg(so_soi[i] % (co_so_luy_thua + 1));
        }
    }

    if (ket_qua_xor != 0) {
        cout << "GOOD" << endl;
    } else {
        cout << "BAD" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    giai_bai_toan();
    return 0;
}