Hướng dẫn giải của Bàn cờ và những con số
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính giá trị tuyệt đối của hiệu giữa tổng các số ở ô trắng và tổng các số ở ô đen trong một hình chữ nhật xác định trên bàn cờ vua n×n. Ô (1,1) được coi là ô trắng, và màu của các ô được xác định xen kẽ (tương tự bàn cờ vua). Với n tối đa 500 và q (số truy vấn) tối đa 10,000, ta cần một giải pháp đủ nhanh để trả lời các truy vấn trong thời gian ngắn.
Các cách tiếp cận
Cách Prefix Sum 2D (Tiền tố tổng 2 chiều)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long white_ps[501][501], black_ps[501][501];
int a[501][501];
long long get(const long long ps[501][501], int r1, int c1, int r2, int c2) {
return ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
}
}
// Xây dựng bảng tiền tố tổng riêng cho ô trắng và ô đen
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
bool isWhite = ((i + j) % 2 == 0);
white_ps[i][j] = white_ps[i-1][j] + white_ps[i][j-1] - white_ps[i-1][j-1] + (isWhite ? a[i][j] : 0);
black_ps[i][j] = black_ps[i-1][j] + black_ps[i][j-1] - black_ps[i-1][j-1] + (isWhite ? 0 : a[i][j]);
}
}
cin >> q;
while(q--){
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
long long s1 = get(white_ps, r1, c1, r2, c2);
long long s2 = get(black_ps, r1, c1, r2, c2);
cout << abs(s1 - s2) << "\n";
}
return 0;
}
- Time Complexity: O(n^2) để xây dựng và O(1) cho mỗi truy vấn.
- Space Complexity: O(n^2)
Giải pháp này sử dụng kỹ thuật tiền tố tổng (Prefix Sum) 2 chiều. Ta duy trì hai ma trận phụ: white_ps lưu tổng các số ở ô trắng tính từ (1,1) đến (i,j), và black_ps cho ô đen.
Công thức cập nhật:
PS[i][j] = PS[i-1][j] + PS[i][j-1] - PS[i-1][j-1] + Value(i,j)
Để tính tổng trong vùng chữ nhật (r1, c1) đến (r2, c2), ta dùng công thức:
Tổng = PS[r2][c2] - PS[r1-1][c2] - PS[r2][c1-1] + PS[r1-1][c1-1]
Phương pháp này rất hiệu quả để xử lý nhiều truy vấn trên một bảng dữ liệu tĩnh.
Cách Phép biến đổi dấu (Signed Prefix Sum)
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> dp(501, vector<int>(501, 0));
int main(){
cin >> n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int temp;
cin >> temp;
// Nếu (i+j) chia hết cho 2 là ô trắng, ta gán giá trị âm
// Ngược lại ô đen giữ nguyên giá trị dương
if((i + j) % 2 == 0){
dp[i][j] = -temp;
} else {
dp[i][j] = temp;
}
}
}
// Xây dựng bảng tiền tố tổng
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dp[i][j] += dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
}
}
int tc;
cin >> tc;
while(tc--){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// Tổng trong vùng = (Tổng đen) - (Tổng trắng)
// Giá trị tuyệt đối của hiệu là kết quả
int ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
cout << abs(ans) << "\n";
}
}
- Time Complexity: O(n^2) để xây dựng và O(1) cho mỗi truy vấn.
- Space Complexity: O(n^2)
Đây là biến thể tối ưu hơn của phương pháp Prefix Sum. Thay vì duy trì hai ma trận riêng biệt, ta chỉ cần một ma trận duy nhất. Quy ước:
- Nếu ô (i, j) là ô trắng ((i+j) % 2 == 0), ta lưu giá trị âm (-a[i][j]).
- Nếu ô (i, j) là ô đen, ta lưu giá trị dương (+a[i][j]).
Khi tính tổng trong vùng chữ nhật, kết quả nhận được sẽ là:
Tổng_O_Đen - Tổng_O_Trắng. Do đó, chỉ cần lấy giá trị tuyệt đối của kết quả là ra đáp án. Phương pháp này tiết kiệm bộ nhớ và giảm số lượng phép truy cập bộ nhớ so với giải pháp 2 bảng.
Cách Brute Force (Tối ưu hóa c cực)
// Code lấy từ solution nguyenn08
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; cin>>n;
// Pret lưu tổng các ô có cùng màu với ô (1,1) (màu Trắng)
// Pred lưu tổng các ô khác màu (màu Đen)
vector<vector<int> > pret(n+1,vector<int>(n+1,0));
vector<vector<int> > pred(n+1,vector<int>(n+1,0));
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
int a; cin>>a;
if ((i+j)%2 == 0){ // Ô trắng
pret[i][j] = a;
pred[i][j] = 0;
} else { // Ô đen
pret[i][j] = 0;
pred[i][j] = a;
}
}
}
// Xây dựng prefix sum theo từng hàng
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
pret[i][j] += pret[i][j-1];
pred[i][j] += pred[i][j-1];
}
}
// Xây dựng prefix sum theo cột
for (int j=1;j<=n;j++){
for (int i=1;i<=n;i++){
pret[i][j] += pret[i-1][j];
pred[i][j] += pred[i-1][j];
}
}
int q; cin>>q;
while (q--){
int x,y,z,t; cin>>x>>y>>z>>t;
long long s1 = pret[z][t] - pret[x-1][t] - pret[z][y-1] + pret[x-1][y-1];
long long s2 = pred[z][t] - pred[x-1][t] - pred[z][y-1] + pred[x-1][y-1];
cout << abs(s1 - s2) << "\n";
}
}
- Time Complexity: O(n^2 + q)
- Space Complexity: O(n^2)
Giải pháp này về cơ bản cũng là Prefix Sum 2D, nhưng quá trình xây dựng ma trận tiền tố tổng được thực hiện theo 2 giai đoạn riêng biệt:
- Tính tổng tiền tố theo hàng (duyệt cột tăng dần).
- Tính tổng tiền tố theo cột (duyệt hàng tăng dần). Cuối cùng, các truy vấn được xử lý tương tự như các giải pháp Prefix Sum khác. Đây là cách tiếp cận đúng đắn nhưng cấu trúc code phức tạp hơn và dễ gây lỗi logic nếu không cẩn thận trong việc xây dựng mảng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) để xây dựng và O(1) cho mỗi truy vấn. | O(n^2) | Prefix Sum 2D (Tiền tố tổng 2 chiều) |
| 2 | O(n^2) để xây dựng và O(1) cho mỗi truy vấn. | O(n^2) | Phép biến đổi dấu (Signed Prefix Sum) |
| 3 | O(n^2 + q) | O(n^2) | Brute Force (Tối ưu hóa c cực) |
Bài học kinh nghiệm
- Bài toán có thể quy về bài toán tính tổng trên hình chữ nhật bằng cách phân loại ô trắng/đen.
- Kỹ thuật Prefix Sum 2D cho phép trả lời truy vấn trong thời gian O(1) sau khi tiền xử lý O(n^2).
- Việc kết hợp hai giá trị (trắng và đen) thành một phép tính với dấu âm/dương giúp giảm bộ nhớ và số lượng phép tính.
Lỗi thường gặp
- Sai lệch trong việc xác định màu ô: Ô (1,1) là trắng, công thức thường dùng là
(i + j) % 2 == 0(nếu tính index bắt đầu từ 1). - Tràn số: Tổng các giá trị có thể lên tới 500500100 = 25,000,000, nhưng với nhiều truy vấn hoặc tổng lớn hơn, cần sử dụng kiểu dữ liệu
long long(64-bit integer) để tránh tràn số. - Lỗi truy cập mảng: Cần chú ý xử lý r1-1 hoặc c1-1 khi r1=1 hoặc c1=1 để tránh truy cập chỉ số âm (thường là lỗi Runtime Error).
Bình luận