***Lời giải***
- Ta nhận thấy các phần tử cách ô $(i,j)$ không quá $k$ sẽ tạo thành một hình thoi
- Vì thế chúng ta cần phải xoay ma trận $45$ độ để các phần tử cần tính tổng trở thành hình vuông, sau đó sử dụng prefix sum hai chiều để tìm tổng các phần tử
***Xoay ma trận 45 độ:***
- Mỗi ô $(i, j)$ trong hệ tọa độ ban đầu được ánh xạ sang hệ mới:
$$
(X = i + j, \quad Y = i - j + n)
$$
- Điều này giúp tất cả các ô có cùng tổng chỉ số $X$ nằm trên cùng một đường chéo, giúp ta dễ dàng xác định phạm vi cộng dồn.
***Prefix sum hai chiều:***
- Chúng ta tạo mảng prefix sum $P$ để tính tổng nhanh với $R$ là ma trận đã xoay 45 độ:
$$
P[x][y] = R[x][y] + P[x-1][y] + P[x][y-1] - P[x-1][y-1]
$$
- Sau đó, tổng giá trị trong phạm vi $k$ của một ô $(i, j)$ được tính như sau:
$$
\text{sum}(x_1, y_1, x_2, y_2) = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1]
$$
***Kết luận:***
- Việc sử dụng phép xoay ma trận kết hợp với prefix sum, thì độ phức tạp sẽ là $O(n^2)$, phù hợp với giới hạn bài toán.
***Code mẫu:***
```
//CODE BY NHANZZZZ
#include <bits/stdc++.h>
using namespace std;
const int MX = 2005;
int n, k, a[1005][1005], r[MX][MX], p[MX][MX], res[1005][1005];
int sum(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return 0;
return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// nhap mang va xoay 45 do
cin >> n >> k;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> a[i][j];
int x = i + j, y = i - j + n;
r[x][y] = a[i][j];
}
}
// xay dung prefix sum hai chieu
for(int i = 1; i < MX; ++i){
for(int j = 1; j < MX; ++j){
p[i][j] = r[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
}
}
// tinh tong
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
int x = i + j, y = i - j + n;
int x1 = max(1, x - k), y1 = max(1, y - k);
int x2 = min(MX-1, x + k), y2 = min(MX-1, y + k);
res[i][j] = sum(x1, y1, x2, y2);
}
}
// in ket qua
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cout << res[i][j] << " ";
}
cout << "\n";
}
}
```
nhanzzzz
Created at
9 likes