Hướng dẫn giải của VO 16 Bài 4 - Trò chơi với những viên bi


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Dựa theo luật chơi có thể phát hiện ra một bất biến: "tính chẵn lẻ của số bi màu đỏ là không đổi". Vì vậy nến kết quả của bài toán chính là số bi màu đỏ modulo 2!!! Để giải quyết trọn vẹn bài toán ta chỉ cần để ý là dãy ~A~ được sinh ra theo quy tắc trong đề tuẩn hoàn theo chu kỳ ~(D + 1)~, nhờ vậy có thể tính ra số bi đỏ trong ~O(D)~.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, d;
int a[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int nTest; cin >> nTest;
    while (nTest--) {
        cin >> n >> d;
        for (int i = 1; i <= d; ++i) cin >> a[i];
        for (int i = d + 1; i <= d + 1; ++i) {
            int x = 0;
            for (int j = i - 1; j >= i - d; --j)
                x ^= a[j];
            a[i] = x;
        }
        int one = 0;
        for (int i = 1; i <= d + 1; ++i) one ^= a[i] == 1;
        int loop = d + 1;
        int cnt = n / loop;
        if (cnt % 2 == 0) one = 0;
        int mod = n % loop;
        if (mod != 0) {
            for (int i = 1; i <= mod; ++i)
                one ^= a[i] == 1;
        }
        cout << one << '\n';
    }
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.