Vận Chuyển Gỗ (Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 2)
Đề bài
VẬN CHUYỂN GỖ (7 điểm)
Ở quốc gia Alpha, có một khu rừng rất rộng có thể được biểu diễn dưới dạng một lưới các ô vuông có kích thước $n \times m$ (km). Khu rừng được chia thành các ô vuông kích thước $1 \times 1$ (km). Ô vuông nằm tại giao của hàng thứ $i$ và cột thứ $j$ được ký hiệu là ô $(i, j)$. Nhà vua đã cử một nhóm lính đi khảo sát khu rừng. Sau khi khảo sát, nhà vua biết được rằng ô $(i, j)$ hiện có một số cây gỗ với tổng khối lượng là $a_{ij}$ tấn.
Nhà vua muốn xây dựng một lâu đài trong rừng. Để làm việc này, ông cần vận chuyển toàn bộ gỗ trong rừng đến một ô bất kỳ. Do kỹ thuật lạc hậu, nếu có $x$ tấn gỗ ở ô $(i, j)$, nhà vua chỉ có thể thuê một nhóm người vận chuyển $x$ tấn gỗ này sang một trong các ô $(i - 1, j)$, $(i + 1, j)$, $(i, j - 1)$, $(i, j + 1)$ với chi phí là $x$ đồng.
Yêu cầu: Bạn hãy giúp nhà vua tìm tổng chi phí vận chuyển nhỏ nhất có thể để xây dựng lâu đài.
Dữ liệu vào: Nhập từ file WTRANS.inp:
- Dòng đầu tiên gồm hai số nguyên dương $n, m$ $(1 \le n, m \le 10^6,\ n \times m \le 10^6)$.
- $n$ dòng tiếp theo, dòng thứ $i$ gồm $m$ số nguyên không âm $a_{i1}, a_{i2}, \ldots, a_{im}$ $(0 \le a_{ij} \le 10^6)$.
Dữ liệu ra: Ghi ra file WTRANS.out:
- Một dòng duy nhất là chi phí vận chuyển nhỏ nhất để xây dựng lâu đài.
Ràng buộc bổ sung:
- $15\%$ số điểm có $n = 1$ và có không quá 2 ô $(i, j)$ có $a_{ij} \gt 0$.
- $15\%$ số điểm khác có không quá 2 ô $(i, j)$ có $a_{ij} \gt 0$.
- $10\%$ số điểm khác có $n = 1$ và $m \le 1000$.
- $10\%$ số điểm khác có không quá 100 ô $(i, j)$ có $a_{ij} \gt 0$.
- $10\%$ số điểm khác có $n = 1$ và $a_{ij} = 1$.
- $10\%$ số điểm khác có $n = 1$.
- $10\%$ số điểm khác có $a_{ij} = 1$.
- $10\%$ số điểm khác có $n \le 100$.
- $10\%$ số điểm còn lại không có giới hạn gì thêm.
Lưu ý: đề gốc đọc/ghi file WTRANS.inp / WTRANS.out; nộp trên web thì đọc từ bàn phím, in ra màn hình (code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng).
2 3
1 2 3
4 5 620Giải thích (theo đề): Ô được chọn để xây lâu đài là ô $(2, 2)$. Việc vận chuyển gỗ sẽ được thực hiện như sau:
- Vận chuyển 1 tấn gỗ từ ô $(1, 1)$ đến ô $(1, 2)$ tốn chi phí là 1.
- Vận chuyển 3 tấn gỗ từ ô $(1, 3)$ đến ô $(1, 2)$ tốn chi phí là 3.
- Vận chuyển 4 tấn gỗ từ ô $(2, 1)$ đến ô $(2, 2)$ tốn chi phí là 4.
- Vận chuyển 6 tấn gỗ từ ô $(2, 3)$ đến ô $(2, 2)$ tốn chi phí là 6.
- Vận chuyển 6 tấn gỗ từ ô $(1, 2)$ đến ô $(2, 2)$ tốn chi phí là 6.
Tổng chi phí vận chuyển gỗ là: $1 + 3 + 4 + 6 + 6 = 20$.
Lời mở đầu
Đây là bài 2 ngày thi thứ nhất trong kỳ thi thử HSG lớp 9 năm 2025 của câu lạc bộ SQRT. Đề chia rất nhiều subtask, mỗi subtask là một "bậc thang" kiến thức: duyệt trâu → công thức → mảng cộng dồn 1 chiều → mảng cộng dồn 2 chiều. Mình viết lời giải đi đúng theo các bậc thang đó để các bạn luyện được cách lấy điểm từng phần nha. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Chuyển $x$ tấn gỗ qua 1 ô kề cạnh tốn $x$ đồng, nên chuyển $x$ tấn đi qua $d$ bước tốn $x \cdot d$ đồng. Đường ngắn nhất từ ô $(u, v)$ tới ô $(i, j)$ chỉ đi ngang/dọc có độ dài $|u - i| + |v - j|$ (gọi là khoảng cách Manhattan). Gộp gỗ "đi chung đường" hay đi riêng thì chi phí như nhau, nên nếu chọn ô lâu đài là $(i, j)$ thì:
Đề bài yêu cầu tìm $\min cost(i, j)$ trên mọi ô.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1n = 1, duyệt mọi vị trí – O(m · k)
Với $n = 1$, ta nhận xét bảng có thể quy thành một mảng một chiều độ dài $m$. Nếu chỉ có không quá $2$ phần tử mà $a_j \gt 0$, ta có thể duyệt qua tất cả các vị trí $i$ từ $1$ đến $m$ và xem xét thử phải mất bao nhiêu chi phí tổng cộng để dồn những ô có $a_j \gt 0$ về lại ô $i$ đang xét. Vì đây chỉ là mảng một chiều, nên đường đi tối ưu để di chuyển một vật từ vị trí $j$ sang vị trí $i$ là $|j - i|$, chi phí là $|j - i| \cdot a_j$.
Mình lưu các vị trí có gỗ vào vector ps để khỏi phải duyệt qua các ô trống. Gọi $k$ là số ô có $a_j \gt 0$, độ phức tạp là $O(m \cdot k)$. Code này cũng ăn luôn subtask 3 ($n = 1$, $m \le 1000$) vì khi đó $m \cdot k \le 10^6$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000005];
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
cin >> n >> m;
vector<int> ps;
for (int i = 1; i <= m; i++){
cin >> a[i];
if (a[i] > 0) ps.push_back(i);
}
long long ans = 1e18;
for (int i = 1; i <= m; i++){
long long cost = 0;
for (auto j : ps) cost += abs(j - i) * a[j];
ans = min(ans, cost);
}
cout << ans << endl;
}import sys, os
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] * (m + 1)
ps = []
for i in range(1, m + 1):
a[i] = int(data[1 + i])
if a[i] > 0:
ps.append(i)
ans = 10**18
for i in range(1, m + 1):
cost = 0
for j in ps:
cost += abs(j - i) * a[j]
ans = min(ans, cost)
print(ans)Subtask 2 + 3 + 4Duyệt trâu trên bảng 2 chiều – O(n · m · k)
Giả sử ta có hai điểm $(x_1, y_1)$ và $(x_2, y_2)$. Dễ dàng thấy rằng đường đi nhỏ nhất giữa hai điểm sẽ là $|x_1 - x_2| + |y_1 - y_2|$: dù đi theo thứ tự nào thì ta cũng phải đi đủ $|x_1 - x_2|$ bước dọc và $|y_1 - y_2|$ bước ngang.
Vì số lượng vị trí trên bảng có $a_{ij} \gt 0$ nhỏ nên đối với mỗi ô $(i, j)$ trên bảng, ta duyệt hết các điểm $(u, v)$ có $a_{uv} \gt 0$ và tính xem sẽ mất tổng chi phí là bao nhiêu để dồn được hết các tấn gỗ ở những ô đó vào ô $(i, j)$. Từ công thức trên, để dồn từ $(u, v)$ vào ô $(i, j)$ sẽ mất chi phí là $(|u - i| + |v - j|) \cdot a_{uv}$.
Gọi $k$ là số lượng vị trí có $a_{ij} \gt 0$ trên bảng. Độ phức tạp: $O(n \cdot m \cdot k)$. Với subtask 2 ($k \le 2$), subtask 3 ($n = 1$, $m \le 1000$ nên $k \le 1000$) và subtask 4 ($k \le 100$) thì số phép tính tối đa khoảng $10^8$ – vẫn chạy kịp.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> a[1000005];
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
cin >> n >> m;
vector<pair<int, int>> ps;
for (int i = 0; i <= n; i++) a[i].resize(m + 1);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
if (a[i][j] > 0) ps.push_back({i, j});
}
}
long long ans = 1e18;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
long long cost = 0;
for (auto g : ps) cost += (abs(g.first - i) + abs(g.second - j)) * a[g.first][g.second];
ans = min(ans, cost);
}
}
cout << ans << endl;
}import sys, os
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [[0] * (m + 1) for _ in range(n + 1)]
ps = []
pos = 2
for i in range(1, n + 1):
for j in range(1, m + 1):
a[i][j] = int(data[pos]); pos += 1
if a[i][j] > 0:
ps.append((i, j, a[i][j]))
ans = 10**18
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = 0
for (u, v, w) in ps:
cost += (abs(u - i) + abs(v - j)) * w
ans = min(ans, cost)
print(ans)Code dùng vector<int> a[1000005] và resize(m + 1) cho từng hàng: vì chỉ biết $n \times m \le 10^6$ chứ không biết $n$, $m$ riêng lẻ, khai báo mảng tĩnh a[1000005][1000005] là không thể, nên ta cấp phát mỗi hàng đúng $m + 1$ ô.
Subtask 5n = 1 và mọi a = 1 – công thức O(m)
Ta thấy dữ kiện khá tương tự ở subtask 1. Ở subtask 1, ta có chi phí tối thiểu để chuyển từ một ô $j$ sang một ô $i$ sẽ là $|j - i| \cdot a_j$. Nhưng vì đề bài đã cho $a_j = 1$ nên chi phí tối thiểu này sẽ là $|j - i|$. Từ đây, đối với mỗi ô $i$, ta sẽ cố tính chi phí tối thiểu để dồn hết các ô kia vào nó.
Khi này, xét các ô $j \lt i$, tổng chi phí tối thiểu để di chuyển các ô này về $i$ sẽ là $\sum_{j=1}^{i-1} (i - j)$. Dễ thấy biểu thức này tương đương với $(i - 1) + (i - 2) + \ldots + 1$ và có thể biến đổi thành $\dfrac{i \cdot (i - 1)}{2}$. Làm tương tự với các ô $j \gt i$: $1 + 2 + \ldots + (m - i) = \dfrac{(m - i + 1) \cdot (m - i)}{2}$. Ta sẽ ra được công thức thu gọn:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000005];
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
long long ans = 1e18;
for (int i = 1; i <= m; i++){
long long cost = i * (i - 1) / 2 + (m - i + 1) * (m - i) / 2;
ans = min(ans, cost);
}
cout << ans << endl;
}import sys, os
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
ans = 10**18
for i in range(1, m + 1):
cost = i * (i - 1) // 2 + (m - i + 1) * (m - i) // 2
ans = min(ans, cost)
print(ans)Subtask 6n = 1 – mảng cộng dồn O(m)
Vì $n = 1$ nên có thể coi đây là mảng một chiều độ dài $m$. Khi này, xét vị trí đặt lâu đài $i$ và các vị trí có gỗ $j$. Ta có hai trường hợp sau:
- Các vị trí $j \lt i$: tổng chi phí để chuyển các $a_j$ về lại vị trí $i$ sẽ là:
$\displaystyle\sum_{j \lt i} a_j \cdot (i - j) = i \cdot \sum_{j \lt i} a_j \;-\; \sum_{j \lt i} a_j \cdot j$Ta sẽ duy trì $sum$ đại diện cho $\sum_{j \lt i} a_j$ và $g$ đại diện cho $\sum_{j \lt i} a_j \cdot j$. Nếu duyệt tuyến tính từ $1$ đến $m$, ta sẽ dễ dàng cập nhật các biến $sum$ và $g$ trong $O(1)$: tính
cost[i] += sum * i - gtrước, rồi mới cộng $a_i$ vào $sum$ và $a_i \cdot i$ vào $g$. - Các vị trí $j \gt i$: tổng chi phí $\sum_{j \gt i} a_j \cdot (j - i) = g - sum \cdot i$, làm tương tự như trên nhưng duyệt ngược từ $m$ về $1$.
Các bạn nhập thử một mảng nhỏ và bấm Tiếp để xem 2 lượt quét: lượt đi tính phần "gỗ bên trái", lượt về cộng thêm phần "gỗ bên phải":
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[1000005];
long long cost[1000005];
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
long long ans = 1e18;
long long sum = 0;
long long g = 0;
for (int i = 1; i <= m; i++){
cost[i] += sum * i - g;
sum += a[i];
g += a[i] * i;
}
sum = 0;
g = 0;
for (int i = m; i >= 1; i--){
cost[i] += g - sum * i;
ans = min(ans, cost[i]);
sum += a[i];
g += a[i] * i;
}
cout << ans << endl;
}import sys, os
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + m]]
cost = [0] * (m + 2)
ans = 10**18
s = 0
g = 0
for i in range(1, m + 1):
cost[i] += s * i - g
s += a[i]
g += a[i] * i
s = 0
g = 0
for i in range(m, 0, -1):
cost[i] += g - s * i
ans = min(ans, cost[i])
s += a[i]
g += a[i] * i
print(ans)Subtask 7Mọi a = 1 – công thức O(n · m)
Vì mọi số trên bảng đều là $1$ nên bài toán chuyển sang: ta cần tìm vị trí $(i, j)$ trên bảng sao cho tổng đường đi từ các ô khác tới nó là nhỏ nhất có thể.
Khi này để di chuyển từ $(u, v)$ đến $(i, j)$ thì đường đi nhỏ nhất sẽ là $|u - i| + |v - j|$. Để tính chi phí cần để dồn hết lại vào $(i, j)$, ta chia bảng làm các vùng và xét lần lượt từng trường hợp:
- $u \le i$ và $v \le j$ (vùng trên – trái): vì $|u - i|$ và $|v - j|$ không có mối liên hệ gì với nhau nên ta sẽ tách riêng ra để tính tổng chi phí dễ dàng hơn. Vì $u \le i$ nên $|u - i| = i - u$. Khi này, đối với mỗi $u$ từ $1$ đến $i - 1$, dễ dàng thấy được sẽ có $j$ vị trí nằm trên hàng $u$ trong phạm vi đang xét. Tới đây, ta nhận thấy rằng chi phí theo chiều dọc sẽ là $j \cdot \big((i - 1) + (i - 2) + \ldots + 1\big) = j \cdot f(i - 1)$ với $f(x) = \dfrac{x(x + 1)}{2}$. Làm tương tự với chiều ngang ($i$ hàng, mỗi hàng đóng góp $f(j - 1)$) ta sẽ ra được tổng chi phí cần tìm của vùng này: $f(i - 1) \cdot j + f(j - 1) \cdot i$.
- Các trường hợp còn lại ($u \le i$, $v \gt j$), ($u \gt i$, $v \gt j$), ($u \gt i$, $v \le j$): xử lý tương tự trường hợp đầu tiên.
| Vùng | Chi phí theo chiều dọc | Chi phí theo chiều ngang |
|---|---|---|
| Trên – trái ($u \le i$, $v \le j$) | $f(i - 1) \cdot j$ | $f(j - 1) \cdot i$ |
| Trên – phải ($u \le i$, $v \gt j$) | $f(i - 1) \cdot (m - j)$ | $f(m - j) \cdot i$ |
| Dưới – phải ($u \gt i$, $v \gt j$) | $f(n - i) \cdot (m - j)$ | $f(m - j) \cdot (n - i)$ |
| Dưới – trái ($u \gt i$, $v \le j$) | $f(n - i) \cdot j$ | $f(j - 1) \cdot (n - i)$ |
Cộng 8 số hạng này lại là ra $cost(i, j)$ – chính là 8 dòng cost += ... trong code.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> a[1000005];
long long f(long long x){
return x * (x + 1) / 2;
}
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
cin >> n >> m;
for (int i = 0; i <= n; i++){
a[i].resize(m + 1);
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
long long ans = 1e18;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
long long cost = 0;
cost += f(i - 1) * j;
cost += f(j - 1) * i;
cost += f(i - 1) * (m - j);
cost += f(m - j) * i;
cost += f(n - i) * (m - j);
cost += f(m - j) * (n - i);
cost += f(n - i) * j;
cost += f(j - 1) * (n - i);
ans = min(ans, cost);
}
}
cout << ans << endl;
}import sys, os
def f(x):
return x * (x + 1) // 2
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
ans = 10**18
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = 0
cost += f(i - 1) * j
cost += f(j - 1) * i
cost += f(i - 1) * (m - j)
cost += f(m - j) * i
cost += f(n - i) * (m - j)
cost += f(m - j) * (n - i)
cost += f(n - i) * j
cost += f(j - 1) * (n - i)
ans = min(ans, cost)
print(ans)Subtask 8 + 9Mảng cộng dồn 2 chiều + lật bảng – O(n · m)
Bây giờ các $a_{ij}$ là bất kỳ. Khi này để di chuyển từ $(u, v)$ đến $(i, j)$ thì chi phí nhỏ nhất sẽ là $a_{uv} \cdot (|u - i| + |v - j|)$. Để tính chi phí cần để dồn hết lại vào $(i, j)$, ta lại chia 4 vùng như subtask 7 và xét lần lượt từng trường hợp:
- $u \le i$ và $v \le j$: khi đó $|u - i| + |v - j| = (i + j) - (u + v)$, nên ta có:
$\displaystyle\sum_{u \le i,\ v \le j} a_{uv} \cdot \big((i + j) - (u + v)\big) = (i + j) \cdot \underbrace{\sum_{u \le i,\ v \le j} a_{uv}}_{sum[i][j]} \;-\; \underbrace{\sum_{u \le i,\ v \le j} a_{uv} \cdot (u + v)}_{g[i][j]}$Đến đây, ta có thể sử dụng hai mảng tổng dồn hai chiều để quản lý tổng $a_{uv}$ (mảng $sum$) và tổng $a_{uv} \cdot (u + v)$ (mảng $g$), vì phạm vi quản lý là một bảng con nằm ở góc trên – trái của bảng chính. Vậy phần đóng góp của vùng này là
sum[i][j] * (i + j) - g[i][j]. - Các trường hợp còn lại ($u \le i$, $v \gt j$), ($u \gt i$, $v \gt j$), ($u \gt i$, $v \le j$): xử lý tương tự trường hợp đầu tiên. Mẹo của mình là lật bảng để biến vùng cần tính thành vùng "trên – trái" rồi dùng lại y nguyên hàm
cal().
$g[i][j] = g[i-1][j] + g[i][j-1] - g[i-1][j-1] + a[i][j] \cdot (i + j)$
Cụ thể 4 lần gọi cal() trong code như sau (toạ độ $(i, j)$ là toạ độ trên bảng đã lật):
| Lần | Bảng hiện tại | Ô (i, j) ứng với ô gốc | Vùng lấy | Vùng gốc tương ứng |
|---|---|---|---|---|
| 1 | Bảng gốc | $(i, j)$ | sum[i][j]: $u \le i$, $v \le j$ | Trên – trái (gồm cả hàng $i$, cột $j$) |
| 2 | Lật ngang | $(i, m - j + 1)$ | sum[i][j - 1]: $u \le i$, $v \lt j$ | Trên – phải (gồm hàng $i$, không gồm cột $j$) |
| 3 | Lật ngang + dọc | $(n - i + 1, m - j + 1)$ | sum[i - 1][j - 1]: $u \lt i$, $v \lt j$ | Dưới – phải |
| 4 | Lật dọc (lật ngang lần 2 là trả lại cột) | $(n - i + 1, j)$ | sum[i - 1][j]: $u \lt i$, $v \le j$ | Dưới – trái (gồm cột $j$) |
Để ý chỗ j - 1, i - 1: 4 vùng phải chia đôi bảng không chồng lên nhau, mỗi ô $(u, v)$ chỉ được tính đúng 1 lần. Khi lật, khoảng cách trên bảng mới vẫn bằng khoảng cách trên bảng gốc (lật gương không làm thay đổi khoảng cách), nên công thức sum * (i + j) - g vẫn đúng.
Các bạn thử khung minh hoạ dưới đây: chọn ô lâu đài nào thì bảng sẽ tô 4 vùng với 4 màu, kèm chi phí của từng vùng (số nhỏ dưới mỗi ô là chi phí chở gỗ của ô đó). Bấm Tiếp để đi qua mọi ô:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> a[1000005];
vector<int> nw[1000005];
vector<long long> cost[1000005];
vector<long long> sum[1000005];
vector<long long> g[1000005];
void cal(){
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + a[i][j] * (i + j);
}
}
void flip_ngang(){
for (int i = 1; i <= n; i++) reverse(a[i].begin() + 1, a[i].end());
}
void flip_doc(){
for (int j = 1; j <= m; j++){
for (int i = 1; i <= n; i++){
nw[n - i + 1][j] = a[i][j];
}
for (int i = 1; i <= n; i++) a[i][j] = nw[i][j];
}
}
signed main(){
if(fopen("WTRANS.inp", "r")){
freopen("WTRANS.inp", "r", stdin);
freopen("WTRANS.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i <= n; i++){
a[i].resize(m + 1);
nw[i].resize(m + 1);
cost[i].resize(m + 1);
sum[i].resize(m + 1);
g[i].resize(m + 1);
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
cal();
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cost[i][j] += sum[i][j] * (i + j) - g[i][j];
flip_ngang();
cal();
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cost[i][m - j + 1] += sum[i][j - 1] * (i + j) - g[i][j - 1];
flip_doc();
cal();
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cost[n - i + 1][m - j + 1] += sum[i - 1][j - 1] * (i + j) - g[i - 1][j - 1];
flip_ngang();
cal();
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cost[n - i + 1][j] += sum[i - 1][j] * (i + j) - g[i - 1][j];
long long ans = 1e18;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++) ans = min(ans, cost[i][j]);
}
cout << ans << endl;
}import sys, os
def cal(a, n, m):
# sum, g: mảng tổng dồn 2 chiều của a[u][v] và a[u][v] * (u + v)
s = [[0] * (m + 1) for _ in range(n + 1)]
g = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
ai, s0, s1, g0, g1 = a[i], s[i - 1], s[i], g[i - 1], g[i]
for j in range(1, m + 1):
s1[j] = s0[j] + s1[j - 1] - s0[j - 1] + ai[j]
g1[j] = g0[j] + g1[j - 1] - g0[j - 1] + ai[j] * (i + j)
return s, g
def flip_ngang(a, n):
for i in range(1, n + 1):
a[i][1:] = a[i][1:][::-1]
def flip_doc(a, n):
a[1:] = a[1:][::-1]
def main():
if os.path.exists('WTRANS.inp'):
sys.stdin = open('WTRANS.inp')
sys.stdout = open('WTRANS.out', 'w')
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [[0] * (m + 1)]
pos = 2
for i in range(n):
a.append([0] + [int(x) for x in data[pos:pos + m]])
pos += m
if n > m:
# Python chậm khi có quá nhiều hàng ngắn: xoay bảng (chuyển vị), đáp án không đổi
a = [[0] * (n + 1)] + [[0] + [a[i][j] for i in range(1, n + 1)] for j in range(1, m + 1)]
n, m = m, n
cost = [[0] * (m + 1) for _ in range(n + 1)]
s, g = cal(a, n, m)
for i in range(1, n + 1):
for j in range(1, m + 1):
cost[i][j] += s[i][j] * (i + j) - g[i][j]
flip_ngang(a, n)
s, g = cal(a, n, m)
for i in range(1, n + 1):
for j in range(1, m + 1):
cost[i][m - j + 1] += s[i][j - 1] * (i + j) - g[i][j - 1]
flip_doc(a, n)
s, g = cal(a, n, m)
for i in range(1, n + 1):
for j in range(1, m + 1):
cost[n - i + 1][m - j + 1] += s[i - 1][j - 1] * (i + j) - g[i - 1][j - 1]
flip_ngang(a, n)
s, g = cal(a, n, m)
for i in range(1, n + 1):
for j in range(1, m + 1):
cost[n - i + 1][j] += s[i - 1][j] * (i + j) - g[i - 1][j]
ans = min(min(row[1:]) for row in cost[1:])
print(ans)
main()Giải thích 1 số chỗ trong code ở trên:
flip_ngang()đảo ngược từng hàng (bỏ phần tử số 0),flip_doc()đảo thứ tự các hàng thông qua mảng phụnw. Lần gọiflip_ngang()thứ hai làm các cột về lại như cũ, nên lúc đó bảng chỉ còn bị lật dọc.- Mỗi lần gọi
cal()tính lạisumvàgtrên bảng hiện tại. Hàng 0 và cột 0 củasum,gluôn bằng 0 nên các chỉ sối - 1,j - 1không bị ra ngoài mảng. - Bản Python làm y hệt nhưng có thêm một bước: nếu $n \gt m$ thì xoay (chuyển vị) bảng trước. Đáp án không đổi vì khoảng cách Manhattan không phụ thuộc việc ta gọi chiều nào là hàng. Lý do là Python xử lý rất chậm khi có hàng triệu hàng ngắn (ví dụ $n = 10^6$, $m = 1$): mình đo thì mất gần 11 giây, xoay bảng xong chỉ còn khoảng 3.4 giây.
Code này dài nên trong khung chạy tay mình gom vài bước nhỏ (ví dụ cả vòng nw[...] = a[...] của một cột) thành một bước. Phần "Dữ liệu" vẽ bảng $a$ hiện tại (sau khi lật), bảng $sum$, $g$ và bảng $cost$ được cộng dần qua 4 lượt:
Đánh giá độ phức tạp của cách làm này:
- Không gian: 5 bảng $a$, $nw$, $cost$, $sum$, $g$ cỡ $n \times m$: $O(n \cdot m)$.
- Thời gian: 4 lần lật bảng, 4 lần
cal()và 4 lần cộng vàocost, mỗi lần $O(n \cdot m)$: tổng $O(n \cdot m)$ với hằng số khoảng 12.
long long (code đã #define int long long). Một điểm nữa: với $n = 10^6$, $m = 1$, mỗi hàng là một vector riêng nên tốn thêm bộ nhớ quản lý; mình đo thì chương trình dùng khoảng 270 MB. Đề không ghi giới hạn bộ nhớ, nếu hệ thống cho ít hơn thì các bạn có thể dồn bảng thành mảng 1 chiều a[(i - 1) * m + j] để tiết kiệm nha.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét