Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Trie XOR tiền tố tìm đoạn con XOR lớn nhất

    Cho mảng a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​ các số nguyên không âm. Tìm giá trị XOR lớn nhất của một đoạn con liên tiếp khác rỗng al⊕al+1⊕⋯⊕ara_l \oplus a_{l+1} \oplus \dots \oplus a_ral​⊕al+1​⊕⋯⊕ar​.

    Gợi ý: duyệt tiền tố XOR và dùng trie nhị phân để truy vấn cực đại.

    • Định dạng đầu vào:

      Dòng đầu: nnn. Dòng hai: nnn số aia_iai​.

    • Ràng buộc đầu vào:

      1≤n≤2⋅1051 \le n \le 2\cdot10^51≤n≤2⋅105, 0≤ai<2300 \le a_i < 2^{30}0≤ai​<230.

    • Định dạng đầu ra:

      Một số nguyên: XOR đoạn con lớn nhất.

    Ví dụ:

    Đầu vào:

    4
1 2 3 4

    Đầu ra:

    7

    Giải thích:

    Xét các đoạn con: a2⊕a3 = 3⊕4 = 7 là giá trị lớn nhất; mọi đoạn khác cho XOR nhỏ hơn hoặc bằng 7.

    Đang tải editor...