Hướng dẫn giải của [Beginner Free Contest 17] XORMATRIX
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.
Hướng dẫn giải
Cần ma trận ~N \times M~ có xor hàng ~i~ bằng ~A_i~ và xor cột ~j~ bằng ~B_j~. Bài là bài xây dựng, chỉ có một cách làm hợp lý (không có vét cạn tự nhiên), nên chương trình chỉ có 1 sub. Nó đạt 10/10 test.
Sub 1: Xây dựng trực tiếp — ~O(N \cdot M)~
Xor của tất cả phần tử tính theo hàng bằng ~A_1 \oplus \dots \oplus A_N~, tính theo cột bằng ~B_1 \oplus \dots \oplus B_M~. Hai giá trị này phải bằng nhau, nếu không thì in NO. Nếu bằng nhau: đặt ~C_{i,M} = A_i~ với ~i < N~, ~C_{N,j} = B_j~ với ~j < M~, các ô còn lại bằng 0, riêng ô góc ~C_{N,M} = A_N \oplus B_1 \oplus \dots \oplus B_{M-1}~. Khi đó hàng cuối có xor đúng ~A_N~, và cột cuối có xor ~A_1 \oplus \dots \oplus A_{N-1} \oplus A_N \oplus B_1 \oplus \dots \oplus B_{M-1} = B_M~ nhờ điều kiện hai xor tổng bằng nhau. Mọi giá trị nhỏ hơn ~2^{27}~ nên không vượt ~10^9~. Máy chấm chấp nhận một ma trận hợp lệ bất kỳ.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi gọi sub1 (chỉ có một sub).
#include <bits/stdc++.h>
using namespace std;
int n, m;
int A[1005], B[1005];
int C[1005][1005];
// Sub 1: xây ma trận theo cách thủ công, dùng chung (bài chỉ có một cách xây hợp lý)
void sub1() {
int xa = 0, xb = 0;
for (int i = 0; i < n; i++) xa ^= A[i];
for (int j = 0; j < m; j++) xb ^= B[j];
if (xa != xb) { cout << "NO\n"; return; } // xor mọi phần tử tính theo hàng và theo cột phải bằng nhau
// Các ô còn lại để 0; cột cuối giữ A_i, hàng cuối giữ B_j; ô góc sửa lại cho khớp
int rowLast = 0;
for (int i = 0; i < n - 1; i++) C[i][m - 1] = A[i];
for (int j = 0; j < m - 1; j++) { C[n - 1][j] = B[j]; rowLast ^= B[j]; }
C[n - 1][m - 1] = A[n - 1] ^ rowLast;
cout << "YES\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cout << C[i][j] << (j + 1 < m ? ' ' : '\n');
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> A[i];
for (int j = 0; j < m; j++) cin >> B[j];
sub1();
return 0;
}
Bình luận