Ghe và xuồng (Đề tự luyện HSG Tin quốc gia – Bài 3)
Đề bài
Ghe và xuồng. Con sông là một trục số, tọa độ tăng theo chiều xuôi dòng. Thầy Sơn có ghe máy ở bến $s_1$ (xuôi mỗi đơn vị tốn $a_1$, ngược tốn $b_1$) và xuồng ở bến $s_2$ (xuôi $a_2$, ngược $b_2$). Có $N$ chuyến hàng giao lần lượt, chuyến $i$ ở bến $p_i$: mỗi chuyến cử đúng một phương tiện chạy từ chỗ nó đang đậu tới $p_i$ rồi đậu luôn ở đó. Tìm tổng chi phí nhỏ nhất.
Dữ liệu vào: dòng 1: $N$ $(1 \le N \le 10^5)$; dòng 2: $s_1\ a_1\ b_1$; dòng 3: $s_2\ a_2\ b_2$; dòng 4: $p_1 \ldots p_N$. Với $0 \le s, p \le 10^9$, $1 \le a, b \le 1000$.
Kết quả: tổng chi phí nhỏ nhất.
- Subtask 1 (15%): $N \le 15$.
- Subtask 2 (25%): $N \le 2000$.
- Subtask 3 (25%): mọi tọa độ $s_1, s_2, p_i \le 500$.
- Subtask 4 (35%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.
6
0 1 4
5 2 4
2 0 6 6 1 817Ghe máy: $0 \to 2$ (tốn 2), $2 \to 0$ (ngược, tốn 8). Xuồng: $5 \to 6$ (tốn 2), chuyến 4 đã ở sẵn bến 6 (tốn 0). Ghe máy: $0 \to 1$ (tốn 1). Xuồng: $6 \to 8$ (tốn 4). Tổng $17$, không có cách nào rẻ hơn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Ghe và xuồngLời mở đầu
Đọc đề, nhiều bạn sẽ nghĩ ngay tới tham lam: "chuyến nào thì cử phương tiện tới đó rẻ hơn". Rất tiếc là sai — cử chiếc xuồng đi xa một chút bây giờ có thể giúp nó đứng sẵn đúng chỗ cho cả chục chuyến sau. Ví dụ trong đề lại tình cờ cho tham lam ra đúng $17$, nên các bạn đừng vội tin nhé! Bài này cần quy hoạch động, và cái khó nằm ở chỗ làm cho QHĐ chạy đủ nhanh với $N = 10^5$, tọa độ tới $10^9$.
Nhận xét 1: trạng thái chỉ cần "ai vừa giao" và "chiếc kia đang ở đâu"
Ngay sau khi giao xong chuyến $i$, phương tiện vừa giao chắc chắn đang ở $p_i$. Vậy để mô tả tình hình chỉ cần biết hai điều: phương tiện nào vừa giao (ghe máy hay xuồng) và vị trí $q$ của phương tiện còn lại. Ta chia trạng thái làm hai họ:
- Họ A: ghe máy vừa giao chuyến $i$ (đang ở $p_i$), xuồng đang ở $q$. Gọi chi phí nhỏ nhất là $A_i[q]$.
- Họ B: xuồng vừa giao chuyến $i$, ghe máy đang ở $q$. Chi phí nhỏ nhất là $B_i[q]$.
Vị trí $q$ chỉ có thể là $s_1$, $s_2$ hoặc một $p_j$ nào đó với $j < i$, nên mỗi họ có không quá $i + 1$ trạng thái.
Hình 1. Từ một trạng thái họ A có đúng hai cách đi tiếp. Cách (1) giữ nguyên họ và vị trí $q$, chỉ cộng thêm chi phí ghe máy đi $p_i \to x$. Cách (2) đổi sang họ B với "chiếc kia" là ghe máy đứng ở $p_i$.
Cách 1Thử mọi cách phân công – O(2^N · N) · 15%
Mỗi chuyến chỉ có 2 lựa chọn: ghe máy hoặc xuồng. Với $N \le 15$ ta thử hết $2^N$ cách bằng đệ quy, mang theo vị trí hiện tại của hai phương tiện và tổng chi phí.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n; ll s[2], a[2], b[2], best = LLONG_MAX;
vector<ll> p;
ll cost(int t, ll u, ll v) { return v >= u ? a[t] * (v - u) : b[t] * (u - v); }
// Thu moi cach: chuyen i do ghe may (t = 0) hoac xuong (t = 1) giao
void dfs(int i, ll pos0, ll pos1, ll tot) {
if (i == n) { best = min(best, tot); return; }
dfs(i + 1, p[i], pos1, tot + cost(0, pos0, p[i]));
dfs(i + 1, pos0, p[i], tot + cost(1, pos1, p[i]));
}
int main() {
scanf("%d", &n);
for (int t = 0; t < 2; t++) scanf("%lld %lld %lld", &s[t], &a[t], &b[t]);
p.resize(n);
for (auto& x : p) scanf("%lld", &x);
dfs(0, s[0], s[1], 0);
printf("%lld\n", best);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s1, a1, b1 = int(data[1]), int(data[2]), int(data[3])
s2, a2, b2 = int(data[4]), int(data[5]), int(data[6])
p = [int(x) for x in data[7:7 + n]]
best = [-1]
def dfs(i, u, v, tot): # u: vi tri ghe may, v: vi tri xuong
if i == n:
if best[0] < 0 or tot < best[0]:
best[0] = tot
return
x = p[i]
dfs(i + 1, x, v, tot + (a1 * (x - u) if x >= u else b1 * (u - x)))
dfs(i + 1, u, x, tot + (a2 * (x - v) if x >= v else b2 * (v - x)))
dfs(0, s1, s2, 0)
print(best[0])
main()Cách 2QHĐ hai họ trạng thái – O(N²) · 40%
Dùng Nhận xét 1. Đánh số vị trí của "chiếc kia" theo chỉ số chuyến: $j = 0$ là bến xuất phát, $j \ge 1$ là bến $p_j$. Khởi tạo sau chuyến 1: $A[0] = $ chi phí ghe máy $s_1 \to p_1$ (xuồng còn ở $s_2$), $B[0] = $ chi phí xuồng $s_2 \to p_1$ (ghe máy còn ở $s_1$). Chuyển từ chuyến $i$ sang chuyến $i + 1$ (gọi $x = p_{i+1}$):
- Phương tiện vừa giao giao tiếp: mọi $A[j]$ cộng thêm $cost_{ghe}(p_i \to x)$, mọi $B[j]$ cộng thêm $cost_{xuồng}(p_i \to x)$.
- Phương tiện kia chạy tới $x$: tạo đúng một trạng thái mới cho mỗi họ, với "chiếc kia" ở $p_i$ (chỉ số $j = i$): $B[i] = \min_j \big(A[j] + cost_{xuồng}(q_j \to x)\big)$ và $A[i] = \min_j \big(B[j] + cost_{ghe}(q_j \to x)\big)$.
Chạy tay với ví dụ (giá trị $A$, $B$ ghi theo vị trí $q$ của "chiếc kia"):
| Sau chuyến | Họ A (ghe máy vừa giao), xuồng ở q | Họ B (xuồng vừa giao), ghe máy ở q |
|---|---|---|
| 1 (bến 2) | q=5: 2 | q=0: 12 |
| 2 (bến 0) | q=2: 12, q=5: 10 | q=0: 20, q=2: 22 |
| 3 (bến 6) | q=0: 26, q=2: 18, q=5: 16 | q=0: 12, q=2: 34 |
| 4 (bến 6) | q=0: 26, q=2: 18, q=5: 16, q=6: 18 | q=0: 12, q=2: 34, q=6: 18 |
| 5 (bến 1) | q=0: 46, q=2: 38, q=5: 36, q=6: 13 | q=0: 32, q=2: 54, q=6: 22 |
| 6 (bến 8) | q=0: 53, q=1: 24, q=2: 45, q=5: 43, q=6: 20 | q=0: 46, q=1: 17, q=2: 68, q=6: 36 |
Đáp án là giá trị nhỏ nhất ở dòng cuối: $17$. (Ở chuyến 4, hai trạng thái mới đều có $q = 6$; nếu trùng vị trí với trạng thái cũ thì giữ min.)
Mô phỏng dưới đây chạy đúng QHĐ này, mỗi bước là một chuyến:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n; ll s1, a1, b1, s2, a2, b2;
scanf("%d %lld %lld %lld %lld %lld %lld", &n, &s1, &a1, &b1, &s2, &a2, &b2);
vector<ll> p(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
auto cA = [&](ll u, ll v) { return v >= u ? a1 * (v - u) : b1 * (u - v); };
auto cB = [&](ll u, ll v) { return v >= u ? a2 * (v - u) : b2 * (u - v); };
// fA[j]: ghe may vua giao chuyen i, xuong dang o vi tri cua chuyen j (j = 0: ben s2)
// fB[j]: xuong vua giao chuyen i, ghe may dang o vi tri cua chuyen j (j = 0: ben s1)
vector<ll> fA(n + 1), fB(n + 1);
fA[0] = cA(s1, p[1]); fB[0] = cB(s2, p[1]);
for (int i = 1; i < n; i++) {
ll last = p[i], x = p[i + 1];
ll vB = LLONG_MAX, vA = LLONG_MAX;
for (int j = 0; j < i; j++) {
ll qB = j ? p[j] : s2, qA = j ? p[j] : s1;
vB = min(vB, fA[j] + cB(qB, x)); // xuong tu qB toi x, ghe may o lai last
vA = min(vA, fB[j] + cA(qA, x)); // ghe may tu qA toi x, xuong o lai last
}
ll dA = cA(last, x), dB = cB(last, x);
for (int j = 0; j < i; j++) { fA[j] += dA; fB[j] += dB; }
fA[i] = vA; fB[i] = vB;
}
ll ans = LLONG_MAX;
for (int j = 0; j < n; j++) ans = min({ans, fA[j], fB[j]});
printf("%lld\n", ans);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s1, a1, b1 = int(data[1]), int(data[2]), int(data[3])
s2, a2, b2 = int(data[4]), int(data[5]), int(data[6])
p = [0] + [int(x) for x in data[7:7 + n]]
# fA[j]: ghe may vua giao chuyen i, xuong o vi tri chuyen j (j = 0: ben s2)
# fB[j]: xuong vua giao chuyen i, ghe may o vi tri chuyen j (j = 0: ben s1)
fA = [0] * (n + 1); fB = [0] * (n + 1)
x = p[1]
fA[0] = a1 * (x - s1) if x >= s1 else b1 * (s1 - x)
fB[0] = a2 * (x - s2) if x >= s2 else b2 * (s2 - x)
for i in range(1, n):
last = p[i]; x = p[i + 1]
vB = -1; vA = -1
for j in range(i):
qB = p[j] if j else s2
c = fA[j] + (a2 * (x - qB) if x >= qB else b2 * (qB - x))
if vB < 0 or c < vB: vB = c
qA = p[j] if j else s1
c = fB[j] + (a1 * (x - qA) if x >= qA else b1 * (qA - x))
if vA < 0 or c < vA: vA = c
if x >= last:
dA = a1 * (x - last); dB = a2 * (x - last)
else:
dA = b1 * (last - x); dB = b2 * (last - x)
for j in range(i):
fA[j] += dA; fB[j] += dB
fA[i] = vA; fB[i] = vB
print(min(min(fA[:n]), min(fB[:n])))
main()Cách 3Gộp theo vị trí + "cộng lười" cả họ – O(N·V) · 65%
Nhìn lại Cách 2, có hai chỗ tốn thời gian: cộng một số vào cả mảng, và lấy min trên cả mảng. Ta xử lý chỗ thứ nhất trước.
Thêm nữa, hai trạng thái cùng họ có cùng vị trí $q$ thì chỉ cần giữ cái nhỏ hơn, nên đánh chỉ số theo tọa độ thay vì theo chuyến. Khi mọi tọa độ $\le V = 500$, mỗi họ là một mảng $V + 1$ ô; mỗi chuyến duyệt $V + 1$ ô để lấy min, tổng cộng $O(N \cdot V) \approx 5 \cdot 10^7$ — chạy tốt. Phần còn lại (tọa độ lớn) vẫn dùng Cách 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
int n; ll s1, a1, b1, s2, a2, b2;
vector<ll> p;
ll cA(ll u, ll v) { return v >= u ? a1 * (v - u) : b1 * (u - v); }
ll cB(ll u, ll v) { return v >= u ? a2 * (v - u) : b2 * (u - v); }
ll solveN2() { // Cach 2: QHD O(N^2)
vector<ll> fA(n + 1), fB(n + 1);
fA[0] = cA(s1, p[1]); fB[0] = cB(s2, p[1]);
for (int i = 1; i < n; i++) {
ll last = p[i], x = p[i + 1], vB = LLONG_MAX, vA = LLONG_MAX;
for (int j = 0; j < i; j++) {
vB = min(vB, fA[j] + cB(j ? p[j] : s2, x));
vA = min(vA, fB[j] + cA(j ? p[j] : s1, x));
}
ll dA = cA(last, x), dB = cB(last, x);
for (int j = 0; j < i; j++) { fA[j] += dA; fB[j] += dB; }
fA[i] = vA; fB[i] = vB;
}
ll ans = LLONG_MAX;
for (int j = 0; j < n; j++) ans = min({ans, fA[j], fB[j]});
return ans;
}
ll solveSmall(int V) { // Cach 3: QHD theo vi tri + cong luoi toan cuc
// DA[v]: ghe may vua giao chuyen cuoi, xuong o v; DB[v]: xuong vua giao, ghe may o v
// gia tri that = DA[v] + offA (hoac DB[v] + offB)
vector<ll> DA(V + 1, INF), DB(V + 1, INF);
ll offA = 0, offB = 0;
DA[s2] = cA(s1, p[1]); DB[s1] = cB(s2, p[1]);
for (int i = 2; i <= n; i++) {
ll last = p[i - 1], x = p[i], vA = INF, vB = INF;
for (int v = 0; v <= V; v++) {
if (DA[v] < INF) vB = min(vB, DA[v] + cB(v, x));
if (DB[v] < INF) vA = min(vA, DB[v] + cA(v, x));
}
vB += offA; vA += offB;
offA += cA(last, x); offB += cB(last, x); // cong cho moi trang thai cung luc
DA[last] = min(DA[last], vA - offA);
DB[last] = min(DB[last], vB - offB);
}
ll ans = INF;
for (int v = 0; v <= V; v++) ans = min({ans, DA[v] + offA, DB[v] + offB});
return ans;
}
int main() {
scanf("%d %lld %lld %lld %lld %lld %lld", &n, &s1, &a1, &b1, &s2, &a2, &b2);
p.assign(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
ll V = max(s1, s2);
for (int i = 1; i <= n; i++) V = max(V, p[i]);
printf("%lld\n", V <= 500 ? solveSmall(V) : solveN2());
}import sys
def solve_n2(n, s1, a1, b1, s2, a2, b2, p): # Cach 2: QHD O(N^2)
fA = [0] * (n + 1); fB = [0] * (n + 1)
x = p[1]
fA[0] = a1 * (x - s1) if x >= s1 else b1 * (s1 - x)
fB[0] = a2 * (x - s2) if x >= s2 else b2 * (s2 - x)
for i in range(1, n):
last = p[i]; x = p[i + 1]
vB = -1; vA = -1
for j in range(i):
qB = p[j] if j else s2
c = fA[j] + (a2 * (x - qB) if x >= qB else b2 * (qB - x))
if vB < 0 or c < vB: vB = c
qA = p[j] if j else s1
c = fB[j] + (a1 * (x - qA) if x >= qA else b1 * (qA - x))
if vA < 0 or c < vA: vA = c
if x >= last:
dA = a1 * (x - last); dB = a2 * (x - last)
else:
dA = b1 * (last - x); dB = b2 * (last - x)
for j in range(i):
fA[j] += dA; fB[j] += dB
fA[i] = vA; fB[i] = vB
return min(min(fA[:n]), min(fB[:n]))
def solve_small(n, s1, a1, b1, s2, a2, b2, p, V): # Cach 3: QHD theo vi tri + cong luoi
INF = 4 * 10 ** 18
DA = [INF] * (V + 1); DB = [INF] * (V + 1)
x = p[1]
DA[s2] = a1 * (x - s1) if x >= s1 else b1 * (s1 - x)
DB[s1] = a2 * (x - s2) if x >= s2 else b2 * (s2 - x)
offA = 0; offB = 0
for i in range(2, n + 1):
last = p[i - 1]; x = p[i]
vA = INF; vB = INF
for v in range(V + 1):
d = DA[v]
if d < INF:
c = d + (a2 * (x - v) if x >= v else b2 * (v - x))
if c < vB: vB = c
d = DB[v]
if d < INF:
c = d + (a1 * (x - v) if x >= v else b1 * (v - x))
if c < vA: vA = c
vB += offA; vA += offB
if x >= last:
offA += a1 * (x - last); offB += a2 * (x - last)
else:
offA += b1 * (last - x); offB += b2 * (last - x)
if vA - offA < DA[last]: DA[last] = vA - offA
if vB - offB < DB[last]: DB[last] = vB - offB
return min(min(DA) + offA, min(DB) + offB)
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s1, a1, b1 = int(data[1]), int(data[2]), int(data[3])
s2, a2, b2 = int(data[4]), int(data[5]), int(data[6])
p = [0] + [int(x) for x in data[7:7 + n]]
V = max(max(p), s1, s2)
if V <= 500:
print(solve_small(n, s1, a1, b1, s2, a2, b2, p, V))
else:
print(solve_n2(n, s1, a1, b1, s2, a2, b2, p))
main()Cách 4Tách xuôi/ngược, lấy min bằng cây Fenwick – O(N log N) · 100%
Còn lại phép lấy min: $\min_q \big(A[q] + cost_{xuồng}(q \to x)\big)$. Hàm chi phí có hai nhánh, nhưng mỗi nhánh lại tách biến rất đẹp:
- Nếu $q \le x$ (xuồng đi xuôi): $A[q] + a_2 (x - q) = \big(A[q] - a_2 q\big) + a_2 x$.
- Nếu $q \ge x$ (xuồng đi ngược): $A[q] + b_2 (q - x) = \big(A[q] + b_2 q\big) - b_2 x$.
Phần trong ngoặc chỉ phụ thuộc $q$! Vậy cần một cấu trúc trả lời "min của $A[q] - a_2 q$ với mọi $q \le x$" (min tiền tố theo tọa độ) và "min của $A[q] + b_2 q$ với mọi $q \ge x$" (min hậu tố). Nén các tọa độ $s_1, s_2, p_1..p_N$ thành chỉ số $1..m$ rồi dùng cây Fenwick lấy min — vì giá trị lưu ở mỗi vị trí chỉ có thể giảm (ta luôn lấy min khi thêm), Fenwick min hoạt động đúng. Với "cộng lười", Fenwick lưu theo giá trị lưu; kết quả truy vấn cộng thêm $off_A$ là ra giá trị thật.
Tổng cộng 4 cây: PA, SA (họ A, xuồng đi xuôi/ngược) và PB, SB (họ B, ghe máy đi xuôi/ngược). Mỗi chuyến: 4 truy vấn + 4 cập nhật, mỗi cái $O(\log N)$.
Code đầy đủ (bản Python gộp các vòng lặp Fenwick của hai họ vào chung một vòng vì chúng luôn cập nhật/truy vấn cùng một chỉ số):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
int m; // so toa do khac nhau
vector<ll> PA, SA, PB, SB; // 4 cay Fenwick lay min
void updP(vector<ll>& f, int i, ll v) { for (; i <= m; i += i & -i) f[i] = min(f[i], v); }
ll qryP(vector<ll>& f, int i) { ll r = INF; for (; i > 0; i -= i & -i) r = min(r, f[i]); return r; }
void updS(vector<ll>& f, int i, ll v) { for (; i > 0; i -= i & -i) f[i] = min(f[i], v); }
ll qryS(vector<ll>& f, int i) { ll r = INF; for (; i <= m; i += i & -i) r = min(r, f[i]); return r; }
int main() {
int n;
ll s1, a1, b1, s2, a2, b2;
scanf("%d %lld %lld %lld %lld %lld %lld", &n, &s1, &a1, &b1, &s2, &a2, &b2);
vector<ll> p(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
vector<ll> xs(p.begin() + 1, p.end());
xs.push_back(s1); xs.push_back(s2);
sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
m = xs.size();
auto id = [&](ll x) { return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1; };
auto cA = [&](ll u, ll v) { return v >= u ? a1 * (v - u) : b1 * (u - v); }; // ghe may di tu u den v
auto cB = [&](ll u, ll v) { return v >= u ? a2 * (v - u) : b2 * (u - v); }; // xuong di tu u den v
PA.assign(m + 1, INF); SA.assign(m + 1, INF); PB.assign(m + 1, INF); SB.assign(m + 1, INF);
// Ho A: ghe may vua giao chuyen cuoi, xuong dang o q; gia tri that = luu + offA
// Ho B: xuong vua giao chuyen cuoi, ghe may dang o q; gia tri that = luu + offB
ll offA = 0, offB = 0, minA = INF, minB = INF;
auto insA = [&](ll q, ll val) { // trang thai ho A, xuong o q, chi phi val
ll st = val - offA; minA = min(minA, st); int k = id(q);
updP(PA, k, st - a2 * q); updS(SA, k, st + b2 * q);
};
auto insB = [&](ll q, ll val) { // trang thai ho B, ghe may o q
ll st = val - offB; minB = min(minB, st); int k = id(q);
updP(PB, k, st - a1 * q); updS(SB, k, st + b1 * q);
};
insA(s2, cA(s1, p[1])); // chuyen 1 do ghe may giao
insB(s1, cB(s2, p[1])); // chuyen 1 do xuong giao
for (int i = 2; i <= n; i++) {
ll last = p[i - 1], x = p[i]; int k = id(x);
// xuong (dang o q) di toi x, ghe may dung yen o last
ll vB = min(qryP(PA, k) + a2 * x, qryS(SA, k) - b2 * x) + offA;
// ghe may (dang o q) di toi x, xuong dung yen o last
ll vA = min(qryP(PB, k) + a1 * x, qryS(SB, k) - b1 * x) + offB;
offA += cA(last, x); // phuong tien vua giao chuyen i-1 giao tiep chuyen i
offB += cB(last, x);
insB(last, vB);
insA(last, vA);
}
printf("%lld\n", min(minA + offA, minB + offB));
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s1, a1, b1 = int(data[1]), int(data[2]), int(data[3]) # ghe may
s2, a2, b2 = int(data[4]), int(data[5]), int(data[6]) # xuong
p = [int(x) for x in data[7:7 + n]]
xs = sorted(set(p + [s1, s2]))
m = len(xs)
pos = {}
for i in range(m):
pos[xs[i]] = i + 1
INF = 4 * 10 ** 18
PA = [INF] * (m + 1); SA = [INF] * (m + 1) # ho A: ghe may vua giao, xuong o q
PB = [INF] * (m + 1); SB = [INF] * (m + 1) # ho B: xuong vua giao, ghe may o q
def ins(stA, qA, stB, qB):
# chen trang thai ho A (xuong o qA) va ho B (ghe may o qB) - dung cho buoc dau
k = pos[qA]; v1 = stA - a2 * qA; v2 = stA + b2 * qA
i = k
while i <= m:
if v1 < PA[i]: PA[i] = v1
i += i & -i
i = k
while i > 0:
if v2 < SA[i]: SA[i] = v2
i -= i & -i
k = pos[qB]; v1 = stB - a1 * qB; v2 = stB + b1 * qB
i = k
while i <= m:
if v1 < PB[i]: PB[i] = v1
i += i & -i
i = k
while i > 0:
if v2 < SB[i]: SB[i] = v2
i -= i & -i
x = p[0]
stA = a1 * (x - s1) if x >= s1 else b1 * (s1 - x) # chuyen 1 do ghe may giao
stB = a2 * (x - s2) if x >= s2 else b2 * (s2 - x) # chuyen 1 do xuong giao
minA = stA; minB = stB
ins(stA, s2, stB, s1)
offA = 0; offB = 0
last = x
for t in range(1, n):
x = p[t]; k = pos[x]
# min tien to (q <= x) cua ca hai ho
r1 = INF; r2 = INF; i = k
while i > 0:
if PA[i] < r1: r1 = PA[i]
if PB[i] < r2: r2 = PB[i]
i -= i & -i
# min hau to (q >= x) cua ca hai ho
u1 = INF; u2 = INF; i = k
while i <= m:
if SA[i] < u1: u1 = SA[i]
if SB[i] < u2: u2 = SB[i]
i += i & -i
vB = r1 + a2 * x; w = u1 - b2 * x
if w < vB: vB = w
vB += offA # xuong di toi x, ghe may o last
vA = r2 + a1 * x; w = u2 - b1 * x
if w < vA: vA = w
vA += offB # ghe may di toi x, xuong o last
if x >= last:
offA += a1 * (x - last); offB += a2 * (x - last)
else:
offA += b1 * (last - x); offB += b2 * (last - x)
stA = vA - offA; stB = vB - offB
if stA < minA: minA = stA
if stB < minB: minB = stB
# ca hai trang thai moi deu co "phuong tien kia" o vi tri last
k = pos[last]
v1 = stA - a2 * last; v2 = stB - a1 * last
i = k
while i <= m:
if v1 < PA[i]: PA[i] = v1
if v2 < PB[i]: PB[i] = v2
i += i & -i
v1 = stA + b2 * last; v2 = stB + b1 * last
i = k
while i > 0:
if v1 < SA[i]: SA[i] = v1
if v2 < SB[i]: SB[i] = v2
i -= i & -i
last = x
ans = minA + offA
if minB + offB < ans: ans = minB + offB
print(ans)
main()int rồi nhân $a \cdot (v - u)$ thì tràn số ngay — lỗi này "sống sót" qua mọi test tọa độ nhỏ nhưng chết ở test lớn.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 32 test (8 – 8 – 7 – 9 theo subtask). Các test lớn có $N = 10^5$, tọa độ tới $10^9$, đáp án tới cỡ $2{,}5 \cdot 10^{15}$. Vị trí các chuyến được sinh theo nhiều kiểu: ngẫu nhiên, vài cụm ở xa nhau (mỗi phương tiện nên "trực" một cụm), zigzag xa–gần, đi ngẫu nhiên, hai "mũi" hàng cùng trôi xuôi xen kẽ, rất nhiều bến trùng nhau; giá xuôi/ngược cũng có nhiều kiểu (xuôi rẻ – ngược đắt, hai phương tiện giống hệt nhau, toàn 1000...).
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – thử 2^N cách | 8/8 | TLE | TLE | TLE | 15 |
| Cách 2 – QHĐ O(N²) | 8/8 | 8/8 | TLE | TLE | 40 |
| Cách 3 – theo vị trí + cộng lười, O(N·V) | 8/8 | 8/8 | 7/7 | TLE | 65 |
| Cách 4 – Fenwick (lời giải đầy đủ) | 8/8 | 8/8 | 7/7 | 9/9 | 100 |
| Sai: tọa độ, giá kiểu int (tràn khi nhân) | 6/8 | 1/8 | 7/7 | 1/9 | 43,26 |
| Sai: tham lam "cử phương tiện tới rẻ hơn" | 3/8 | 0/8 | 0/7 | 0/9 | 5,62 |
| Sai: quên trường hợp phương tiện kia đi ngược dòng | 2/8 | 0/8 | 0/7 | 0/9 | 3,75 |
| Sai: cộng off trước khi tính trạng thái mới | 1/8 | 0/8 | 0/7 | 0/9 | 1,88 |
Để ý: ví dụ trong đề được chọn sao cho tham lam, bản "quên đi ngược dòng" và bản tràn int đều in đúng 17 — lượt đi ngược dòng duy nhất trong phương án tối ưu là của chính phương tiện vừa giao chuyến trước, còn số nhỏ thì không tràn. Bản tràn int vẫn ăn trọn subtask 3 vì tọa độ $\le 500$ không đủ để tràn.
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: lời giải chuẩn chạy tối đa khoảng 0,4 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3 giây. Lời giải chuẩn được đối chiếu với chương trình vét cạn trên 600 test nhỏ và với QHĐ Cách 2, Cách 3 trên 300 test vừa, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và chỉ tốn khoảng 1,3 giây CPU ngay cả trên CPython.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- 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