Hướng dẫn cho XOR3
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho ba đoạn số nguyên \([L_1, R_1]\), \([L_2, R_2]\) và \([L_3, R_3]\). Nhiệm vụ của bạn là chọn ra bộ ba số \((x_1, x_2, x_3)\) sao cho \(x_i \in [L_i, R_i]\) để:
- Giá trị \(x_1 \oplus x_2 \oplus x_3\) đạt giá trị nhỏ nhất.
- Giá trị \(x_1 \oplus x_2 \oplus x_3\) đạt giá trị lớn nhất.
Trong đó \(\oplus\) là phép toán XOR nhị phân.
Phân tích
- Giới hạn: \(L_i, R_i \le 10^{18}\). Với giới hạn này, chúng ta không thể duyệt qua từng số trong đoạn.
- Tính chất phép XOR: Phép XOR tác động độc lập trên từng bit. Tuy nhiên, việc chọn số trong đoạn \([L, R]\) tạo ra sự phụ thuộc giữa các bit (bit cao quyết định giới hạn của các bit thấp hơn).
- Dạng bài: Đây là bài toán điển hình sử dụng Quy hoạch động chữ số (Digit DP) kết hợp với xử lý bit.
Hướng giải quyết
Ý tưởng chính
Chúng ta sẽ xây dựng các số \(x_1, x_2, x_3\) bằng cách chọn từng bit từ cao xuống thấp (từ bit 60 về bit 0). Tại mỗi bước, ta cần duy trì trạng thái để biết liệu các số đang chọn có còn nằm trong phạm vi \([L_i, R_i]\) hay không.
Trạng thái Quy hoạch động
Với mỗi số \(x_i\), trạng thái giới hạn so với \([L_i, R_i]\) có thể biểu diễn bằng 2 bit (tổng cộng 4 trạng thái):
- Bit 1 (giá trị 2): Nếu bằng 1, số đang chọn vẫn đang khớp với các bit cao của \(R_i\) (chưa được tự do chọn bit nhỏ hơn bit của \(R_i\)).
- Bit 0 (giá trị 1): Nếu bằng 1, số đang chọn vẫn đang khớp với các bit cao của \(L_i\) (chưa được tự do chọn bit lớn hơn bit của \(L_i\)).
Cụ thể, trạng thái cnd của một số \(x\) so với \([L, R]\) tại bit thứ \(i\):
cnd & 2: Đúng nếu mọi bit từ \(N-1\) đến \(i+1\) của \(x\) đều bằng các bit tương ứng của \(R\).cnd & 1: Đúng nếu mọi bit từ \(N-1\) đến \(i+1\) của \(x\) đều bằng các bit tương ứng của \(L\).
Các bước thực hiện
- Hàm tìm giới hạn: Tại bit thứ \(pos\), dựa vào trạng thái hiện tại của số \(x_i\), ta xác định được \(x_i[pos]\) có thể chọn là 0 hay 1.
- Nếu đang bị giới hạn bởi \(L_i\), bit chọn phải \(\ge L_i[pos]\).
- Nếu đang bị giới hạn bởi \(R_i\), bit chọn phải \(\le R_i[pos]\).
- Hàm chuyển trạng thái: Sau khi chọn bit \(x[pos] = v\), trạng thái mới sẽ được cập nhật dựa trên việc \(v\) có bằng \(L[pos]\) và \(R[pos]\) hay không.
- Tính toán Min và Max:
- Để tìm Min: \(DP[i][cx][cy][cz]\) lưu giá trị XOR nhỏ nhất có thể tạo ra từ bit \(N-1\) đến bit \(pos\).
- Để tìm Max: Ta có thể dùng cùng một hàm DP nhưng đổi dấu giá trị XOR hoặc khởi tạo lại DP để tìm giá trị lớn nhất. Trong code tham khảo, tác giả sử dụng một mẹo nhỏ là nhân với
signđể tận dụng cùng một cấu trúc code cho cả hai yêu cầu.
Độ phức tạp
- Thời gian: \(O(N \times 4^3 \times 2^3)\), trong đó \(N \approx 60\) là số lượng bit, \(4^3\) là số trạng thái giới hạn của 3 số, và \(2^3\) là các lựa chọn bit \((0/1)\) cho \(x_1, x_2, x_3\). Đây là độ phức tạp rất nhỏ, phù hợp với thời gian cho phép.
- Bộ nhớ: \(O(N \times 4^3)\) để lưu bảng DP.
Code tham khảo
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int N = 62; // Đủ để chứa 10^18
const Int INF = 2e18; // Giá trị vô cùng lớn
Int dp[N][4][4][4];
// Lấy bit thứ i của x
int bit(Int x, int i) { return (x >> i) & 1; }
// Cập nhật trạng thái giới hạn mới sau khi chọn bit x tại vị trí i
int cond(Int l, Int r, int x, int i) {
int res = 0;
if (x == bit(r, i)) res |= 2; // Vẫn đang bám sát giới hạn trên R
if (x == bit(l, i)) res |= 1; // Vẫn đang bám sát giới hạn dưới L
return res;
}
// Xác định các giá trị bit (0 hoặc 1) có thể chọn tại vị trí i
void get_limit(Int l, Int r, int cnd, int i, int& low, int& high) {
low = (cnd & 1) ? bit(l, i) : 0;
high = (cnd & 2) ? bit(r, i) : 1;
}
void minimize(Int& var, const Int& val) { if (val < var) var = val; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Int a[3], b[3];
for (int i = 0; i < 3; i++) cin >> a[i] >> b[i];
Int sign = 1;
// Chạy 2 lần: lần 1 tìm Min, lần 2 tìm Max
for (int times = 0; times < 2; times++) {
// Reset DP với giá trị cực đại
for (int i = 0; i < N; i++)
for (int x = 0; x < 4; x++)
for (int y = 0; y < 4; y++)
for (int z = 0; z < 4; z++)
dp[i][x][y][z] = INF;
dp[0][3][3][3] = 0; // Trạng thái ban đầu: cả 3 số đều đang ở giới hạn [L, R]
for (int i = 0; i < N - 1; i++) {
int pos = N - i - 2; // Duyệt từ bit cao xuống thấp
for (int cx = 0; cx < 4; cx++) {
for (int cy = 0; cy < 4; cy++) {
for (int cz = 0; cz < 4; cz++) {
if (dp[i][cx][cy][cz] == INF) continue;
int l[3], h[3];
get_limit(a[0], b[0], cx, pos, l[0], h[0]);
get_limit(a[1], b[1], cy, pos, l[1], h[1]);
get_limit(a[2], b[2], cz, pos, l[2], h[2]);
// Thử tất cả các bộ bit (x, y, z) có thể chọn
for (int x = l[0]; x <= h[0]; x++) {
for (int y = l[1]; y <= h[1]; y++) {
for (int z = l[2]; z <= h[2]; z++) {
int ncx = cx & cond(a[0], b[0], x, pos);
int ncy = cy & cond(a[1], b[1], y, pos);
int ncz = cz & cond(a[2], b[2], z, pos);
// Tính giá trị XOR tại bit hiện tại
Int current_xor = (Int)(x ^ y ^ z) << pos;
minimize(dp[i + 1][ncx][ncy][ncz], dp[i][cx][cy][cz] + sign * current_xor);
}
}
}
}
}
}
}
Int ans = INF;
for (int cx = 0; cx < 4; cx++)
for (int cy = 0; cy < 4; cy++)
for (int cz = 0; cz < 4; cz++)
minimize(ans, dp[N - 1][cx][cy][cz]);
cout << sign * ans << "\n";
// Đổi bài toán tìm Max thành tìm Min bằng cách đổi dấu
sign = -1;
for (int i = 0; i < 3; i++) swap(a[i], b[i]); // Không thực sự cần thiết nếu dùng sign
}
return 0;
}
Bình luận