Hướng dẫn thuật toán - Đăng - Chuyên Sơn La Online Judge

Nhận xét:

Đây là một bài toán tối ưu về thao tác bit (Bitwise operation), cụ thể là phép XOR (). Do ràng buộc của và lên đến , ta không thể duyệt tất cả các cặp , mà cần một thuật toán hiệu quả hơn, dựa trên biểu diễn nhị phân của số.

1. Phân tích đề bài

Yêu cầu: Tìm giá trị lớn nhất của (XOR) với điều kiện .
Đầu vào: Hai số nguyên và ().
Đầu ra: Giá trị lớn nhất của .
Ràng buộc quan trọng: Cần sử dụng kiểu dữ liệu 64-bit (ví dụ: long long trong C++, int trong Python 3) để chứa và .

2. Ý tưởng Thuật toán

Để tối đa hóa giá trị của , ta muốn các bit có trọng số lớn nhất (tính từ trái sang) của kết quả là 1. Bit thứ của bằng 1 nếu và chỉ nếu bit thứ của và khác nhau (một là 0, một là 1).

Ý tưởng cốt lõi là tìm bit khác nhau quan trọng nhất giữa và .

Tính . cho biết các vị trí bit mà và khác nhau.
Tìm vị trí bit có trọng số lớn nhất (Most Significant Bit - MSB) của . Gọi vị trí đó là .
- Các bit ở vị trí của và là giống nhau. Do , nên các bit này của và cũng buộc phải giống nhau. Do đó, .
- Tại vị trí , . Vì , nên phải là 0 và phải là 1.
Tối đa hóa XOR:
- Để tối đa hóa , ta cần và khác nhau ở vị trí và tất cả các vị trí thấp hơn ().
- Vì và đã khác nhau ở bit (), ta có thể chọn có bit và có bit (hoặc ngược lại).
- Sự khác biệt giữa và ở bit cho phép ta chọn các số và trong phạm vi sao cho và khác nhau tại bit và tất cả các bit thấp hơn.
Kết quả tối đa: Giá trị XOR lớn nhất có thể đạt được là một số có các bit từ trở xuống đều là 1.

3. Các bước cơ bản của Thuật toán

Đọc và xử lý đầu vào: Đọc hai số và dưới dạng số nguyên 64-bit.
Tính XOR: Tính .
Trường hợp đặc biệt: Nếu (tức là ), kết quả là .
Tìm vị trí MSB (): Tìm vị trí bit của bit 1 có trọng số lớn nhất trong . ( là chỉ số bắt đầu từ 0).
- .
- Ví dụ: . . .
- Ví dụ: . . .
Tính kết quả: Kết quả lớn nhất là .

Minh họa cho Ví dụ:

.
.
MSB của là ở vị trí (bit thứ hai từ phải sang).
Kết quả: . (Kiểm tra: Chọn . ).

4. Lưu ý khi triển khai bằng C++/Python

Kiểu dữ liệu: Bắt buộc phải dùng kiểu 64-bit:
- C++: Sử dụng long long.
- Python: Mặc định số nguyên là lớn, nên không cần lo lắng về kích thước.
Tìm MSB ():
- Sử dụng logarit: k = floor(log2(X)) (cần thư viện <cmath>).
- Dùng hàm dựng sẵn (C++): Đối với long long, có thể dùng __builtin_clzll (Count Leading Zeros Long Long) để tính nhanh chóng:
```
// long long X;
int num_leading_zeros = __builtin_clzll(X);
int k = 63 - num_leading_zeros; // Giả sử 64-bit
```
- Vòng lặp (cách đơn giản nhất): Dùng vòng lặp dịch bit để tìm vị trí .
```
k = 0
while (1 << (k+1)) <= X:
    k += 1
# hoặc đơn giản hơn:
k = X.bit_length() - 1
```
Tính : Đây chính là trừ đi 1. Có thể tính bằng phép dịch bit:
- Kết quả (trong C++)
- Kết quả (trong Python)