C++ Truy vấn xác suất số chẵn/lẻ trong khoảng cho trước

Cho mảng và các truy vấn khoảng. Mỗi truy vấn yêu cầu in p và q biểu diễn xác suất p/q. Ví dụ:

Input: N=5, arr[]={6,5,2,1,7}, truy vấn: 0 2 2, 1 2 5, 0 1 4
Output: 0, 3/4, 1/2

Trong truy vấn: k=0 (tìm số chẵn), k=1 (tìm số lẻ), l,r là khoảng.

Phương pháp giải

Duy trì 2 mảng tiền tố: even[i] = số số chẵn từ đầu đến i, odd[i] = số số lẻ. Xử lý truy vấn như bài toán prefix sum.

Ví dụ minh họa

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

void solve(int arr[], int n, int Q, int query[][3]) {
    int even[n+1], odd[n+1];
    even[0] = odd[0] = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] & 1) {
            odd[i+1] = odd[i] + 1;
            even[i+1] = even[i];
        } else {
            even[i+1] = even[i] + 1;
            odd[i+1] = odd[i];
        }
    }

    for (int i = 0; i < Q; i++) {
        int k = query[i][0], l = query[i][1], r = query[i][2];
        int q = r - l + 1;
        int p = (k == 1) ? (odd[r] - odd[l-1]) : (even[r] - even[l-1]);

        if (p == 0) cout << "0\n";
        else if (p == q) cout << "1\n";
        else {
            int g = __gcd(p, q);
            cout << p/g << " " << q/g << "\n";
        }
    }
}

int main() {
    int arr[] = {6, 5, 2, 1, 7};
    int n = sizeof(arr)/sizeof(int);
    int Q = 2;
    int query[2][3] = {{0,2,2}, {1,2,5}};
    solve(arr, n, Q, query);
    return 0;
}

Kết quả

0
3 4

Giải thích

Mảng tiền tố even/odd cho phép trả lời truy vấn O(1). Kết quả rút gọn bằng GCD.

Kết luận

Đã giải bài toán truy vấn xác suất chẵn/lẻ bằng mảng tiền tố. Code C++ chuyển được sang các ngôn ngữ khác. Hy vọng hữu ích.