Bài 41: Kỹ thuật tìm kiếm nâng cao trong C++ và Python: chặt nhị phân đáp án, chặt tam phân, meet in the middle, nhánh cận
Lời mở đầu
Rất nhiều bài khó trong đề HSG không có thuật toán “đặc trị”. Ta chỉ biết đáp án nằm trong một không gian rất lớn, và nhiệm vụ là tìm kiếm trong không gian ấy một cách thông minh. Em đã có những viên gạch đầu tiên: quay lui ở bài 15 duyệt mọi cấu hình, tìm kiếm nhị phân ở bài 16 (có cả chặt nhị phân đáp án bài cắt gỗ), hai con trỏ ở bài 17 để ghép cặp trên hai dãy đã sắp xếp. Bài này nâng cấp cả ba lên mức đề thi HSG quốc gia.
Cụ thể, ta học cách nhận ra và viết hàm kiểm tra cho dạng “cực tiểu hoá giá trị lớn nhất”, chặt nhị phân trên số thực kết hợp với tham lam và quy hoạch động, chặt tam phân tìm đáy của hàm lồi, meet in the middle giải bài tổng tập con với $n = 40$, và nhánh cận để quay lui chạy nhanh hơn hàng nghìn lần nhờ một cận ước lượng tốt.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Chặt nhị phân đáp án: cực tiểu hoá giá trị lớn nhất
Đề bài kiểu “chia … sao cho giá trị lớn nhất là nhỏ nhất” hay “đặt … sao cho khoảng cách nhỏ nhất là lớn nhất” gần như luôn là tín hiệu của chặt nhị phân đáp án. Ví dụ kinh điển:
Bài toán. Cho dãy $n$ số nguyên dương $a_1, \ldots, a_n$ ($n \le 2 \cdot 10^5$, $a_i \le 10^9$) và số $k$. Chia dãy thành không quá $k$ đoạn liên tiếp sao cho tổng của đoạn có tổng lớn nhất là nhỏ nhất. In ra tổng đó.
Thử trực tiếp mọi cách chia là bất khả thi. Ta lật ngược câu hỏi: thay vì hỏi “đáp án là bao nhiêu?”, hỏi “đáp án có thể ≤ X không?”. Tức là: có chia được dãy thành không quá $k$ đoạn mà mọi đoạn có tổng $\le X$ không? Câu hỏi này dễ hơn hẳn, trả lời bằng tham lam: đi từ trái sang phải, nhét số vào đoạn hiện tại cho tới khi nhét thêm sẽ vượt $X$ thì mở đoạn mới. Số đoạn tham lam tạo ra là ít nhất có thể, nên chỉ cần so nó với $k$.
Điều quan trọng nhất: hàm check(X) đơn điệu. Nếu chia được với giới hạn $X$ thì chắc chắn chia được với mọi giới hạn lớn hơn. Dãy kết quả check theo X luôn có dạng sai sai … sai đúng đúng … đúng, và đáp án là X đầu tiên làm check đúng: đúng khuôn mẫu “vị trí đầu tiên thoả điều kiện” ở bài 16.
Hình 1. Với a = [7, 2, 5, 10, 8] và k = 2: check(X) sai với mọi X ≤ 17 và đúng với mọi X ≥ 18. Ta không cần tính check ở mọi X, chỉ cần chặt nhị phân tìm chỗ đổi màu.
| lo | hi | mid | chia tham lam với X = mid | số đoạn | kết luận |
|---|---|---|---|---|---|
| 10 | 32 | 21 | [7 2 5] [10 8] | 2 ≤ k | đúng, hi = 21 |
| 10 | 21 | 15 | [7 2 5] [10] [8] | 3 > k | sai, lo = 16 |
| 16 | 21 | 18 | [7 2 5] [10 8] | 2 ≤ k | đúng, hi = 18 |
| 16 | 18 | 17 | [7 2 5] [10] [8] | 3 > k | sai, lo = 18 |
| 18 | 18 | dừng, đáp án 18 |
Bảng 1. Chặt nhị phân đáp án với a = [7, 2, 5, 10, 8], k = 2. Khởi đầu lo = max = 10 (đoạn chứa số 10 có tổng ít nhất 10), hi = tổng = 32.
Độ phức tạp: mỗi lần check tốn $O(n)$, chặt nhị phân trên đoạn $[\max a, \sum a]$ dài tới $2 \cdot 10^{14}$ cần khoảng 48 lần, tổng $O(n \log \sum a)$. Em bấm Tự chạy để xem từng lần thử X và cách tham lam cắt đoạn:
Xem code C++ / Python: chia dãy thành k đoạn, tổng lớn nhất nhỏ nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[200005];
bool check(long long X){ // chia được thành <= k đoạn, mỗi đoạn tổng <= X?
int cnt = 1;
long long s = 0;
for(int i = 0; i < n; i++){
if(s + a[i] > X){ // nhét thêm a[i] sẽ vượt X: mở đoạn mới
cnt++;
s = 0;
}
s += a[i];
}
return cnt <= k;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
long long lo = 0, hi = 0;
for(int i = 0; i < n; i++){
cin >> a[i];
lo = max(lo, a[i]); // đoạn nào cũng phải chứa nổi số lớn nhất
hi += a[i]; // một đoạn chứa cả dãy: chắc chắn được
}
while(lo < hi){ // tìm X nhỏ nhất mà check(X) đúng
long long mid = (lo + hi) / 2;
if(check(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo;
return 0;
}import sys
def check(a, k, X): # chia được thành <= k đoạn, mỗi đoạn tổng <= X?
cnt, s = 1, 0
for v in a:
if s + v > X: # nhét thêm v sẽ vượt X: mở đoạn mới
cnt += 1
s = 0
s += v
return cnt <= k
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
lo, hi = max(a), sum(a)
while lo < hi: # tìm X nhỏ nhất mà check(X) đúng
mid = (lo + hi) // 2
if check(a, k, mid):
hi = mid
else:
lo = mid + 1
print(lo)2. Kiểm tra tính đơn điệu bằng lời: nới lỏng X thì từ “được” không thể thành “không được”.
3. Khi X đã cố định, bài toán thường trở nên tham lam được: cứ dồn càng nhiều càng tốt cho tới khi chạm giới hạn X.
4. Chọn lo, hi sao cho chắc chắn đáp án nằm trong $[lo, hi]$, rồi dùng đúng một khuôn:
// X nhỏ nhất làm check đúng // X lớn nhất làm check đúng
while(lo < hi){ while(lo < hi){
mid = (lo + hi) / 2; mid = (lo + hi + 1) / 2; // làm tròn lên
if(check(mid)) hi = mid; if(check(mid)) lo = mid;
else lo = mid + 1; else hi = mid - 1;
} }Dạng đối xứng: cực đại hoá giá trị nhỏ nhất. “Có $n$ vị trí trên một con đường, đặt $k$ trạm phát sóng sao cho khoảng cách nhỏ nhất giữa hai trạm là lớn nhất.” Câu hỏi Có/Không: “đặt được $k$ trạm mà hai trạm bất kỳ cách nhau ≥ D không?”. Tham lam: sắp xếp vị trí, đặt trạm đầu ở vị trí nhỏ nhất, rồi cứ gặp vị trí cách trạm vừa đặt ≥ D là đặt. D càng lớn càng khó đặt, nên check có dạng đúng … đúng sai … sai và ta tìm D lớn nhất làm check đúng (khuôn bên phải). Đây là bài tập 1.
lo = mid mà lại tính mid = (lo + hi) / 2; khi hi = lo + 1 thì mid = lo mãi mãi. Tìm X lớn nhất thì phải làm tròn lên.Tràn số: hi là tổng cả dãy, tới $2 \cdot 10^{14}$, nên lo, hi, mid và tổng trong check đều phải
long long.Quên điều kiện biên trong check: nếu lo khởi đầu nhỏ hơn số lớn nhất thì phải xử lý “một số đã lớn hơn X” (return false), nếu không tham lam sẽ đếm sai.
Phần 2Chặt nhị phân trên số thực, kết hợp tham lam và QHĐ
Bài toán. Cho dãy $n$ số nguyên $a_1, \ldots, a_n$ ($n \le 10^5$, $|a_i| \le 10^4$) và số $L$. Tìm đoạn con liên tiếp có độ dài ít nhất $L$ mà trung bình cộng lớn nhất. In ra trung bình cộng đó với 6 chữ số sau dấu phẩy.
Nếu không có điều kiện độ dài, đáp án chỉ là số lớn nhất. Điều kiện “dài ít nhất $L$” khiến bài khó hẳn: không có công thức, duyệt mọi đoạn tốn $O(n^2)$. Lại lật câu hỏi: “có đoạn nào dài ≥ L mà trung bình ≥ x không?” Mẹo then chốt là phép biến đổi:
$\dfrac{a_l + \cdots + a_r}{r - l + 1} \ge x \iff (a_l - x) + (a_{l+1} - x) + \cdots + (a_r - x) \ge 0.$
Vậy chỉ cần trừ $x$ vào mọi phần tử rồi hỏi: có đoạn dài ≥ L với tổng ≥ 0 không? Với mảng cộng dồn $P$, tổng đoạn $(l, r]$ là $P_r - P_l$, và ta cần $l \le r - L$. Duyệt $r$ từ $L$ tới $n$, giữ $\min(P_0, \ldots, P_{r-L})$: một vòng $O(n)$. Trung bình càng đòi cao càng khó đạt, nên check đơn điệu và ta chặt nhị phân trên $x$ thực.
| $x$ thử | dãy $a_i - x$ | đoạn dài ≥ 4 có tổng lớn nhất | check |
|---|---|---|---|
| 10 | −9 2 −15 −16 40 −7 | 2 − 15 − 16 + 40 = 11 | đúng |
| 12.75 | −11.75 −0.75 −17.75 −18.75 37.25 −9.75 | −0.75 − 17.75 − 18.75 + 37.25 = 0 | đúng (vừa khít) |
| 13 | −12 −1 −18 −19 37 −10 | lớn nhất là −1 − 18 − 19 + 37 = −1 | sai |
Bảng 2. Dãy a = [1, 12, −5, −6, 50, 3], L = 4. Đoạn tốt nhất là 12, −5, −6, 50 với trung bình 51 / 4 = 12,75; mọi x ≤ 12,75 làm check đúng.
Xem code C++ / Python: trung bình cộng lớn nhất của đoạn dài ít nhất L (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, L;
double a[100005], P[100005];
bool check(double x){ // có đoạn dài >= L với trung bình >= x?
P[0] = 0;
for(int i = 1; i <= n; i++) P[i] = P[i - 1] + (a[i] - x); // trừ x vào mọi phần tử
double mn = 1e18;
for(int r = L; r <= n; r++){
mn = min(mn, P[r - L]); // P[l] nhỏ nhất với l <= r - L
if(P[r] - mn >= 0) return true;
}
return false;
}
int main(){
scanf("%d %d", &n, &L);
double lo = 1e9, hi = -1e9;
for(int i = 1; i <= n; i++){
scanf("%lf", &a[i]);
lo = min(lo, a[i]); hi = max(hi, a[i]);
}
for(int it = 0; it < 100; it++){ // lặp số lần cố định
double mid = (lo + hi) / 2;
if(check(mid)) lo = mid;
else hi = mid;
}
printf("%.6f", lo);
return 0;
}import sys
from itertools import accumulate
from operator import sub
def check(a, L, x): # có đoạn dài >= L với trung bình >= x?
P = list(accumulate((v - x for v in a), initial=0))
M = list(accumulate(P[:len(a) - L + 1], min)) # M[t] = min(P[0..t])
return max(map(sub, P[L:], M)) >= 0 # P[r] - min P[l] với l <= r - L
data = sys.stdin.buffer.read().split()
n, L = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
lo, hi = min(a), max(a)
for _ in range(60): # lặp số lần cố định
mid = (lo + hi) / 2
if check(a, L, mid):
lo = mid
else:
hi = mid
print('%.6f' % lo)while(hi - lo > 1e-9): khi lo, hi lớn (cỡ $10^9$), sai số của double có thể lớn hơn $10^{-9}$ và vòng lặp không bao giờ dừng. Hãy lặp cố định 60 đến 100 lần: mỗi lần đoạn còn một nửa, 100 lần thu nhỏ $2^{100} \approx 10^{30}$ lần, dư sức cho mọi đề. Khi so sánh trong check, >= 0 hay > 0 không quan trọng vì sai khác cỡ $10^{-15}$. Nhiều khi còn tránh được số thực hẳn: nếu đề cho phép, nhân cả hai vế lên để chặt nhị phân trên số nguyên (bài tập 7).Tỉ số tối ưu. Phép biến đổi trên áp dụng cho cả một họ bài: “chọn một nhóm đồ vật sao cho $\frac{\sum a_i}{\sum b_i}$ lớn nhất”. Tỉ số ≥ x tương đương $\sum (a_i - x \cdot b_i) \ge 0$, nên mỗi lần thử x, ta gán cho đồ vật $i$ “điểm” $c_i = a_i - x b_i$ và hỏi: có cách chọn hợp lệ với tổng điểm ≥ 0 không? Tuỳ ràng buộc chọn mà hàm kiểm tra dùng kỹ thuật khác nhau:
| Đề bài hỏi | Câu hỏi Có/Không với X | Bên trong hàm check |
|---|---|---|
| Chia dãy k đoạn, tổng lớn nhất nhỏ nhất | mọi đoạn tổng ≤ X, số đoạn ≤ k? | tham lam, $O(n)$ |
| Đặt k trạm, khoảng cách nhỏ nhất lớn nhất | đặt được k trạm cách nhau ≥ X? | tham lam sau khi sắp xếp |
| Trung bình cộng lớn nhất, đoạn dài ≥ L | có đoạn tổng $(a_i - X)$ ≥ 0? | cộng dồn + min tiền tố |
| Chọn đúng k vật, tỉ số $\sum a / \sum b$ lớn nhất | k số $a_i - X b_i$ lớn nhất có tổng ≥ 0? | sắp xếp, lấy k số đầu |
| Chọn vật, tổng khối lượng ≥ W, tỉ số lớn nhất | có nhóm khối lượng ≥ W, tổng $(a_i - X b_i)$ ≥ 0? | QHĐ cái túi |
| Đường đi có cạnh lớn nhất nhỏ nhất | đi tới đích chỉ bằng cạnh ≤ X? | BFS / DFS |
Bảng 3. Chặt nhị phân đáp án là “vỏ”, còn “ruột” (hàm check) có thể là tham lam, cộng dồn, sắp xếp, QHĐ hay duyệt đồ thị.
Chặt nhị phân + QHĐ. Ở dòng thứ năm của bảng, ràng buộc “tổng khối lượng ≥ W” không tham lam được: lấy vật điểm cao chưa chắc đủ khối lượng. Ta dùng QHĐ cái túi: $f[j]$ = tổng điểm lớn nhất khi tổng khối lượng (chặn trên ở W) bằng $j$. Mỗi lần check tốn $O(nW)$, nhân với số lần chặt nhị phân. Dấu hiệu nhận biết: bài QHĐ quen thuộc nhưng mục tiêu là một tỉ số hay một max/min thay vì một tổng, thì cố định đáp án X để mục tiêu trở lại thành tổng. Bài tập 7 luyện đúng dạng này.
Phần 3Chặt tam phân: tìm đáy của hàm lồi
Chặt nhị phân cần một điều kiện đơn điệu (sai… sai đúng… đúng). Nhưng có những bài mà đại lượng cần tối ưu giảm rồi tăng theo biến số: đặt trạm ở quá xa bên trái thì tốn, quá xa bên phải cũng tốn, đâu đó ở giữa là tốt nhất. Hàm như vậy gọi là đơn đỉnh (unimodal); trường hợp hay gặp nhất là hàm lồi. Để tìm đáy, ta dùng chặt tam phân (ternary search).
Ý tưởng. Trên đoạn $[l, r]$ lấy hai điểm chia $m_1 < m_2$ (thường chia ba đều). So sánh $f(m_1)$ với $f(m_2)$:
- Nếu $f(m_1) < f(m_2)$: từ $m_1$ sang $m_2$ hàm đi lên, nên $m_2$ đã ở sườn phải; đáy nằm trong $[l, m_2]$. Bỏ phần $(m_2, r]$.
- Ngược lại: $m_1$ còn ở sườn trái (hoặc hai điểm nằm hai bên đáy); đáy nằm trong $[m_1, r]$. Bỏ phần $[l, m_1)$.
Mỗi lượt bỏ đi 1/3 đoạn, tốn 2 lần tính $f$. Sau 100 lượt, đoạn ban đầu dài $10^9$ còn $10^9 \cdot (2/3)^{100} \approx 2{,}5 \cdot 10^{-9}$.
Em nhập giá trị của hàm tại các điểm nguyên và xem chặt tam phân bỏ dần từng phần ra sao. Sau đó thử dãy 6 0 6 6 6 6 6 6 2 9 (không đơn đỉnh) để thấy nó trả lời sai:
Bài toán ví dụ: đặt trạm bơm. Có $n$ ngôi nhà ở các điểm $(x_i, y_i)$ ($n \le 10^4$, toạ độ nguyên, $|x_i|, |y_i| \le 10^4$). Con sông chạy dọc trục $Ox$. Cần đặt một trạm bơm tại điểm $(x, 0)$ và nối ống thẳng tới từng nhà. Tìm tổng độ dài ống nhỏ nhất. Hàm $f(x) = \sum \sqrt{(x - x_i)^2 + y_i^2}$ là tổng của các hàm lồi nên cũng lồi, và đáy chắc chắn nằm giữa $\min x_i$ và $\max x_i$. Không có công thức cho điểm đáy, nhưng chặt tam phân thì dễ:
Xem code C++ / Python: chặt tam phân trên số thực: đặt trạm bơm (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<double> X, Y;
double f(double x){ // tổng độ dài ống khi đặt trạm tại (x, 0)
double s = 0;
for(int i = 0; i < n; i++) s += sqrt((x - X[i]) * (x - X[i]) + Y[i] * Y[i]);
return s;
}
int main(){
scanf("%d", &n);
X.resize(n); Y.resize(n);
for(int i = 0; i < n; i++) scanf("%lf %lf", &X[i], &Y[i]);
double lo = *min_element(X.begin(), X.end());
double hi = *max_element(X.begin(), X.end());
for(int it = 0; it < 100; it++){
double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
if(f(m1) < f(m2)) hi = m2; // đáy không nằm bên phải m2
else lo = m1; // đáy không nằm bên trái m1
}
printf("%.6f", f(lo));
return 0;
}import sys
from math import hypot
data = sys.stdin.buffer.read().split()
n = int(data[0])
X = [int(v) for v in data[1:2 * n + 1:2]]
Y = [int(v) for v in data[2:2 * n + 2:2]]
def f(x): # tổng độ dài ống khi đặt trạm tại (x, 0)
return sum(hypot(x - a, b) for a, b in zip(X, Y))
lo, hi = min(X), max(X)
for _ in range(100):
m1, m2 = lo + (hi - lo) / 3, hi - (hi - lo) / 3
if f(m1) < f(m2):
hi = m2 # đáy không nằm bên phải m2
else:
lo = m1 # đáy không nằm bên trái m1
print('%.6f' % f(lo))Chặt tam phân trên số nguyên. Khi biến số là số nguyên (chọn số lượng, chọn ngày…), cách gọn và an toàn nhất là chặt nhị phân trên “độ dốc”: với hàm lồi, dãy $f(x+1) - f(x)$ không giảm, nên điều kiện “$f(x) \le f(x+1)$” có dạng sai… sai đúng… đúng. Điểm $x$ đầu tiên thoả điều kiện chính là đáy, dùng nguyên khuôn mẫu bài 16:
long long lo = L, hi = R; // f lồi trên các số nguyên [L, R]
while(lo < hi){
long long m = (lo + hi) / 2;
if(f(m) <= f(m + 1)) hi = m; // đã tới đáy hoặc đang đi lên: đáy ở m hoặc bên trái
else lo = m + 1; // còn đi xuống: đáy ở bên phải m
}
// đáp án: f(lo)Hình 2. Chặt tam phân đúng với hàm đơn đỉnh và hàm lồi (kể cả đáy phẳng). Với hàm có đoạn nằm ngang ở giữa sườn hoặc nhiều đáy, phép so sánh f(m1), f(m2) không cho biết đáy ở phía nào.
| Chặt nhị phân | Chặt tam phân | |
|---|---|---|
| Điều kiện | check đơn điệu: sai… sai đúng… đúng | f giảm rồi tăng (đơn đỉnh, lồi) |
| Mỗi lượt | bỏ 1/2 đoạn, tính check 1 lần | bỏ 1/3 đoạn, tính f 2 lần |
| Số lần tính trên đoạn dài $10^9$ (số nguyên) | khoảng 30 | khoảng 100 |
| Tìm | X đầu tiên / cuối cùng thoả điều kiện | điểm cực tiểu (hoặc cực đại) của f |
Bảng 4. So sánh hai kỹ thuật. Trên số nguyên, chặt nhị phân trên độ dốc thường được ưu tiên vì nhanh hơn và ít lỗi biên hơn.
2. Hàm có nhiều cực tiểu địa phương (lên xuống nhiều lần): chặt tam phân chỉ tìm được một đáy nào đó, chưa chắc là đáy thấp nhất.
3. Chưa chứng minh được hàm lồi. Một số cách kiểm: tổng của các hàm lồi là lồi; max của các hàm lồi là lồi; $|x - a|$, $(x - a)^2$, $\sqrt{(x-a)^2 + b^2}$ đều lồi. Nếu không chứng minh được, hãy viết chương trình trâu in ra $f$ trên một đoạn nhỏ để quan sát trước khi dám dùng.
Phần 4Meet in the middle: chia đôi tập để 2⁴⁰ còn 2²⁰
Bài toán. Cho $n$ số nguyên $a_1, \ldots, a_n$ ($n \le 40$, $|a_i| \le 10^9$) và số $S$. Đếm số tập con (kể cả tập rỗng) có tổng đúng bằng $S$.
Giá trị $a_i$ lớn nên không QHĐ theo tổng được. Quay lui ở bài 15 phải duyệt $2^{40} \approx 1{,}1 \cdot 10^{12}$ tập con, quá chậm. Meet in the middle (gặp nhau ở giữa): chia dãy làm hai nửa, mỗi nửa 20 số. Mỗi tập con của cả dãy là hợp của một tập con nửa trái và một tập con nửa phải, nên:
- Liệt kê tổng của mọi tập con nửa trái, được danh sách $A$ gồm $2^{20} \approx 10^6$ số. Tương tự với nửa phải, được $B$.
- Đếm số cặp $(x, y)$ với $x \in A$, $y \in B$ và $x + y = S$. Sắp xếp $B$, với mỗi $x$ tìm nhị phân số lượng $y = S - x$ trong $B$ (
equal_range), hoặc sắp xếp cả hai rồi dùng hai con trỏ ngược chiều như bài 17.
Tổng thời gian $O(2^{n/2} \cdot n)$: khoảng $2 \cdot 10^7$ phép tính thay vì $10^{12}$.
Hình 3. Meet in the middle: hai nửa được liệt kê độc lập, rồi “gặp nhau” ở bước ghép.
| $n$ | Duyệt hết: $2^n$ | Meet in the middle: $2 \cdot 2^{n/2}$ | Bộ nhớ |
|---|---|---|---|
| 20 | $\approx 10^6$ | $\approx 2 \cdot 10^3$ | không đáng kể |
| 30 | $\approx 10^9$ | $\approx 6 \cdot 10^4$ | không đáng kể |
| 40 | $\approx 1{,}1 \cdot 10^{12}$ (không kịp) | $\approx 2 \cdot 10^6$ | 2 mảng $2^{20}$ số, khoảng 16 MB |
| 50 | $\approx 10^{15}$ | $\approx 6{,}7 \cdot 10^7$ | 2 mảng $2^{25}$ số, khoảng 512 MB (quá giới hạn!) |
Bảng 5. Meet in the middle đổi thời gian lấy bộ nhớ. Với $n \le 40$ là vừa đẹp; $n = 50$ thì thời gian ổn nhưng bộ nhớ thường vượt giới hạn.
Cách liệt kê tổng các tập con gọn nhất: bắt đầu từ $[0]$ (tập rỗng); thêm từng số $x$, mỗi tổng cũ sinh thêm một tổng mới cộng $x$, nên danh sách gấp đôi sau mỗi số. Em xem mô phỏng dưới đây: hai nửa được liệt kê thế nào, rồi sau khi sắp xếp, hai con trỏ ghép cặp ra sao (để ý cách đếm khi có nhiều tổng bằng nhau):
Code dưới đây dùng cách thứ nhất (tìm nhị phân trên $B$). Em chạy tay với $n \le 8$ để thấy rõ A, B được sinh ra và mỗi $x$ tìm “nửa còn lại” $S - x$ của mình:
Xem code C++ / Python: meet in the middle: đếm tập con có tổng bằng S (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
vector<long long> allSums(const vector<long long> &v){ // tổng của mọi tập con của v
vector<long long> s = {0};
for(long long x : v){
int sz = s.size();
for(int t = 0; t < sz; t++) s.push_back(s[t] + x); // mỗi tổng cũ: thêm x hoặc không
}
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long S;
cin >> n >> S;
vector<long long> a(n);
for(auto &x : a) cin >> x;
vector<long long> A = allSums(vector<long long>(a.begin(), a.begin() + n / 2));
vector<long long> B = allSums(vector<long long>(a.begin() + n / 2, a.end()));
sort(B.begin(), B.end());
long long cnt = 0;
for(long long x : A){
auto r = equal_range(B.begin(), B.end(), S - x); // các y trong B bằng S - x
cnt += r.second - r.first;
}
cout << cnt;
return 0;
}import sys
from collections import Counter
def all_sums(v): # tổng của mọi tập con của v
s = [0]
for x in v:
s += [y + x for y in s] # mỗi tổng cũ: thêm x hoặc không
return s
data = sys.stdin.buffer.read().split()
n, S = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
A = all_sums(a[:n // 2])
B = Counter(all_sums(a[n // 2:])) # B[y] = số tập con nửa phải có tổng y
print(sum(B.get(S - x, 0) for x in A))2. Giá trị lớn (tới $10^9$, $10^{18}$) nên không QHĐ theo giá trị được.
3. Đáp án của cả tập tách được thành phần của nửa trái và phần của nửa phải rồi ghép lại (tổng, xor, tích modulo…). Khi ghép, mục tiêu “x + y = S” dùng tìm nhị phân / hai con trỏ / bảng băm; mục tiêu “x + y ≤ S, lớn nhất” dùng sắp xếp + tìm nhị phân (bài tập 4, 5, 8).
vector truyền theo giá trị, sẽ chậm gấp nhiều lần. Đừng dùng map cho $10^6$ phần tử khi sort + equal_range đủ dùng. Trong Python, sinh bằng list comprehension như code trên và đếm bằng Counter; tránh vòng lặp lồng tay trên $10^6$ phần tử.Phần 5Nhánh cận: cắt tỉa trong quay lui bằng cận ước lượng
Ở bài 15, khi đặt quân hậu, ta đã cắt nhánh mỗi khi phát hiện một ô bị khống chế: nhánh đó chắc chắn không dẫn tới cấu hình hợp lệ. Với bài tối ưu (tìm lớn nhất / nhỏ nhất), ta còn cắt được mạnh hơn nhiều: bỏ những nhánh chắc chắn không dẫn tới cấu hình tốt hơn kỷ lục đang có. Đó là kỹ thuật nhánh cận (branch and bound):
- Giữ biến
best: giá trị tốt nhất đã tìm được (kỷ lục). - Tại mỗi nút của cây quay lui, tính một cận: ước lượng lạc quan nhất cho mọi cấu hình trong nhánh này (cận trên với bài tìm max, cận dưới với bài tìm min).
- Nếu ngay cả ước lượng lạc quan nhất cũng không vượt
bestthì bỏ cả nhánh.
Cận phải đúng (không bao giờ bi quan hơn thực tế, nếu không sẽ cắt mất đáp án) và càng sát càng tốt (cắt được nhiều). Đồng thời phải tính nhanh, vì nó được tính ở mọi nút.
Ví dụ 1: cái túi với khối lượng lớn. $n \le 40$ đồ vật, khối lượng và giá trị tới $10^9$, sức chứa $W \le 10^{12}$. QHĐ theo khối lượng như bài 19 không được vì $W$ quá lớn. Quay lui lấy / bỏ từng món, với cận trên là lời giải của bài cái túi cho phép cắt lẻ: sắp xếp đồ vật theo giá trị trên 1 kg giảm dần, lấy tham lam các món còn lại, món cuối không vừa thì lấy một phần. Ở bài 18 ta đã biết tham lam này tối ưu cho cái túi cắt lẻ, mà cái túi cắt lẻ thì luôn ≥ cái túi 0/1, nên đây là một cận trên đúng.
| Món | Khối lượng | Giá trị | Giá trị / kg | Cận ở gốc (W = 10) |
|---|---|---|---|---|
| #4 | 3 | 50 | 16,7 | lấy cả: 50, còn 7 kg |
| #2 | 4 | 40 | 10 | lấy cả: 90, còn 3 kg |
| #3 | 6 | 30 | 5 | lấy 3/6 món: 90 + 15 = 105 |
| #1 | 5 | 10 | 2 | (không còn chỗ) |
Bảng 6. Bốn đồ vật đã sắp theo giá trị / kg. Cận trên ở gốc là 105: không cách chọn nào vượt quá 105. Đáp án thật là 90 (món #4 và #2).
Em chạy mô phỏng để xem cây quay lui: nhánh “lấy” đi trước nên kỷ lục 90 xuất hiện rất sớm. Sau đó, nhánh “bỏ món #2” có cận 82 và nhánh “bỏ món #4” có cận 70, cả hai đều ≤ 90 nên bị cắt ngay mà không cần đi xuống:
Xem code C++ / Python: nhánh cận cho cái túi 0/1 với khối lượng lớn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n;
long long W, best = 0;
vector<long long> w, v; // đã sắp theo v/w giảm dần
double bound(int i, long long cw, long long cv){ // cận trên: cho phép cắt lẻ đồ vật
double res = cv;
long long cap = W - cw;
for(; i < n; i++){
if(w[i] <= cap){ cap -= w[i]; res += v[i]; }
else { res += (double)v[i] * cap / w[i]; break; }
}
return res;
}
void Try(int i, long long cw, long long cv){
best = max(best, cv);
if(i == n) return;
if(bound(i, cw, cv) <= best) return; // CẮT NHÁNH
if(cw + w[i] <= W) Try(i + 1, cw + w[i], cv + v[i]); // lấy đồ vật i
Try(i + 1, cw, cv); // bỏ đồ vật i
}
int main(){
cin >> n >> W;
vector<pair<long long, long long>> it(n); // (w, v)
for(auto &p : it) cin >> p.first >> p.second;
sort(it.begin(), it.end(), [](const pair<long long, long long> &x, const pair<long long, long long> &y){
return x.second * y.first > y.second * x.first; // v/w giảm dần, so sánh bằng phép nhân
});
for(auto &p : it){ w.push_back(p.first); v.push_back(p.second); }
Try(0, 0, 0);
cout << best;
return 0;
}import sys
from fractions import Fraction
def main():
data = sys.stdin.buffer.read().split()
n, W = int(data[0]), int(data[1])
it = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)]
it.sort(key=lambda p: Fraction(p[1], p[0]), reverse=True) # v/w giảm dần
w = [p[0] for p in it]
v = [p[1] for p in it]
best = 0
def bound(i, cw, cv): # cận trên: cho phép cắt lẻ đồ vật
res, cap = cv, W - cw
while i < n:
if w[i] > cap:
return res + v[i] * cap / w[i]
cap -= w[i]
res += v[i]
i += 1
return res
def Try(i, cw, cv):
nonlocal best
if cv > best:
best = cv
if i == n or bound(i, cw, cv) <= best: # hết đồ vật hoặc CẮT NHÁNH
return
if cw + w[i] <= W:
Try(i + 1, cw + w[i], cv + v[i]) # lấy đồ vật i
Try(i + 1, cw, cv) # bỏ đồ vật i
Try(0, 0, 0)
print(best)
main()Ví dụ 2: người du lịch (TSP) với $n$ nhỏ. Xuất phát từ thành phố 1, đi qua mọi thành phố đúng một lần rồi quay về, chi phí $c_{ij}$, tìm hành trình rẻ nhất. Quay lui sinh hoán vị tốn $(n-1)!$. Cận dưới đơn giản: gọi $mn_i$ là cạnh rẻ nhất đi ra từ thành phố $i$. Đang ở $u$ với chi phí $cur$, phần đường còn lại phải đi ra từ $u$ một lần và từ mỗi thành phố chưa thăm một lần, nên
$\text{cận dưới} = cur + mn_u + \sum_{v \text{ chưa thăm}} mn_v.$
Nếu cận dưới ≥ kỷ lục thì quay lui ngay. Biến tổng $\sum mn_v$ được cập nhật khi đánh dấu / bỏ đánh dấu nên cận tính trong $O(1)$. Bài tập 6 cài đặt đúng ý này.
2. Sắp xếp dữ liệu để cận tính nhanh và sát (như sắp theo giá trị/kg).
3. Cận phải đúng: thử cận trên một bộ test nhỏ, so với chương trình duyệt hết. Cận sai (quá bi quan) sẽ cắt mất đáp án mà không báo lỗi gì.
Tổng kết: nhìn giới hạn để chọn kỹ thuật.
| Dấu hiệu trong đề | Kỹ thuật | Độ phức tạp thường gặp |
|---|---|---|
| “max nhỏ nhất”, “min lớn nhất”, check theo X đơn điệu | chặt nhị phân đáp án | $O(n \log V)$ |
| tỉ số, trung bình lớn nhất | chặt nhị phân số thực + biến đổi $a - x b$ | $O(n \cdot 100)$ |
| đại lượng giảm rồi tăng theo một biến | chặt tam phân / chặt nhị phân độ dốc | $O(\text{tính } f \cdot 100)$ |
| $n \le 40$, giá trị lớn, ghép được hai nửa | meet in the middle | $O(2^{n/2} \cdot n)$ |
| bài tối ưu tổ hợp, $n$ nhỏ, không có thuật toán đa thức | quay lui + nhánh cận | tuỳ cận, xấu nhất mũ |
Bảng 7. Năm kỹ thuật tìm kiếm của bài này và dấu hiệu nhận biết.
- Nuôi bò 1 (Dễ)
- Factory Machines (CSES 1620) (Trung bình)
- Chia Mảng (CSES Array Division) (Khá)
- Trung Bình Cộng Lớn Nhất (CSLOJ 1404) (Khá)
- Chia Ruộng (Khá)
- Ăn Buffet (Khó)
Bài tậpLuyện kỹ thuật tìm kiếm nâng cao
Trên một con đường thẳng có $n$ vị trí đôi một khác nhau $x_1, \ldots, x_n$ ($2 \le n \le 10^5$, $0 \le x_i \le 10^9$). Cần chọn $k$ vị trí ($2 \le k \le n$) để đặt trạm phát sóng sao cho khoảng cách nhỏ nhất giữa hai trạm là lớn nhất. In ra khoảng cách đó.
5 3
1 2 8 4 93📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
mid = (lo + hi + 1) / 2. Ví dụ: sắp xếp được 1 2 4 8 9, đặt ở 1, 4, 8 (hoặc 1, 4, 9) thì khoảng cách nhỏ nhất là 3; D = 4 thì chỉ đặt được 1, 8.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long x[100005];
bool check(long long D){ // đặt được k trạm, hai trạm liền nhau cách >= D?
int cnt = 1;
long long last = x[0]; // trạm đầu ở vị trí nhỏ nhất
for(int i = 1; i < n; i++)
if(x[i] - last >= D){ cnt++; last = x[i]; }
return cnt >= k;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> x[i];
sort(x, x + n);
long long lo = 1, hi = x[n - 1] - x[0]; // tìm D lớn nhất mà check(D) đúng
while(lo < hi){
long long mid = (lo + hi + 1) / 2; // làm tròn lên
if(check(mid)) lo = mid;
else hi = mid - 1;
}
cout << lo;
return 0;
}import sys
def check(x, k, D): # đặt được k trạm, hai trạm liền nhau cách >= D?
cnt, last = 1, x[0]
for p in x:
if p - last >= D:
cnt += 1
last = p
return cnt >= k
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
x = sorted(map(int, data[2:2 + n]))
lo, hi = 1, x[-1] - x[0] # tìm D lớn nhất mà check(D) đúng
while lo < hi:
mid = (lo + hi + 1) // 2 # làm tròn lên
if check(x, k, mid):
lo = mid
else:
hi = mid - 1
print(lo)Hàng rào gồm $n$ tấm ván xếp thẳng hàng, tấm thứ $i$ dài $a_i$ mét ($n \le 10^5$, $1 \le a_i \le 10^5$). Có $k$ thợ sơn ($1 \le k \le n$), mỗi thợ được giao một dãy tấm ván liên tiếp (mỗi tấm do đúng một thợ sơn), thợ sơn 1 mét hết $t$ giây ($1 \le t \le 10^4$). Các thợ làm cùng lúc. Hỏi sau ít nhất bao nhiêu giây thì sơn xong cả hàng rào?
5 2 3
7 2 5 10 854📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long t, a[100005];
bool check(long long X){ // chia được <= k đoạn, mỗi đoạn tổng <= X?
int cnt = 1;
long long s = 0;
for(int i = 0; i < n; i++){
if(s + a[i] > X){ cnt++; s = 0; }
s += a[i];
}
return cnt <= k;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k >> t;
long long lo = 0, hi = 0;
for(int i = 0; i < n; i++){ cin >> a[i]; lo = max(lo, a[i]); hi += a[i]; }
while(lo < hi){
long long mid = (lo + hi) / 2;
if(check(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo * t;
return 0;
}import sys
def check(a, k, X): # chia được <= k đoạn, mỗi đoạn tổng <= X?
cnt, s = 1, 0
for v in a:
if s + v > X:
cnt += 1
s = 0
s += v
return cnt <= k
data = sys.stdin.buffer.read().split()
n, k, t = int(data[0]), int(data[1]), int(data[2])
a = list(map(int, data[3:3 + n]))
lo, hi = max(a), sum(a)
while lo < hi:
mid = (lo + hi) // 2
if check(a, k, mid):
hi = mid
else:
lo = mid + 1
print(lo * t)Có $n$ bạn đứng trên một trục số ($1 \le n \le 10^4$), bạn thứ $i$ ở toạ độ $x_i$ ($|x_i| \le 10^9$) và chạy với vận tốc tối đa $v_i$ ($1 \le v_i \le 10^9$). Các bạn muốn gặp nhau tại cùng một điểm (số thực bất kỳ). Tìm thời gian $T$ nhỏ nhất để mọi người cùng có mặt. Dòng 2 là các $x_i$, dòng 3 là các $v_i$. In $T$ với 6 chữ số sau dấu phẩy (sai số tới $10^{-6}$ được chấp nhận).
3
7 1 3
1 2 12.000000📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<double> x, v;
double T(double p){ // thời gian để mọi người tới p
double r = 0;
for(int i = 0; i < n; i++) r = max(r, fabs(p - x[i]) / v[i]);
return r;
}
int main(){
scanf("%d", &n);
x.resize(n); v.resize(n);
for(int i = 0; i < n; i++) scanf("%lf", &x[i]);
for(int i = 0; i < n; i++) scanf("%lf", &v[i]);
double lo = *min_element(x.begin(), x.end()), hi = *max_element(x.begin(), x.end());
for(int it = 0; it < 100; it++){
double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
if(T(m1) < T(m2)) hi = m2;
else lo = m1;
}
printf("%.6f", T(lo));
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = list(map(int, data[1:1 + n]))
v = list(map(int, data[1 + n:1 + 2 * n]))
def T(p): # thời gian để mọi người tới p
return max(abs(p - a) / b for a, b in zip(x, v))
lo, hi = min(x), max(x)
for _ in range(100):
m1, m2 = lo + (hi - lo) / 3, hi - (hi - lo) / 3
if T(m1) < T(m2):
hi = m2
else:
lo = m1
print('%.6f' % T(lo))Cửa hàng có $n$ món đồ ($n \le 40$), món thứ $i$ giá $a_i$ ($0 \le a_i \le 10^9$). Em có $S$ đồng ($0 \le S \le 10^{18}$). Hỏi có bao nhiêu cách chọn một tập món đồ (kể cả không chọn gì) với tổng giá không vượt quá $S$?
3 5
1 2 37📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<long long> allSums(const vector<long long> &v){
vector<long long> s = {0};
for(long long x : v){
int sz = s.size();
for(int t = 0; t < sz; t++) s.push_back(s[t] + x);
}
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long S;
cin >> n >> S;
vector<long long> a(n);
for(auto &x : a) cin >> x;
vector<long long> A = allSums(vector<long long>(a.begin(), a.begin() + n / 2));
vector<long long> B = allSums(vector<long long>(a.begin() + n / 2, a.end()));
sort(A.begin(), A.end());
sort(B.begin(), B.end());
long long cnt = 0;
int j = (int)B.size() - 1;
for(long long x : A){ // x tăng dần
while(j >= 0 && x + B[j] > S) j--; // j chỉ lùi
cnt += j + 1; // B[0..j] đều ghép được với x
}
cout << cnt;
return 0;
}import sys
def all_sums(v):
s = [0]
for x in v:
s += [y + x for y in s]
return s
data = sys.stdin.buffer.read().split()
n, S = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
A = sorted(all_sums(a[:n // 2]))
B = sorted(all_sums(a[n // 2:]))
cnt, j = 0, len(B) - 1
for x in A: # x tăng dần
while j >= 0 and x + B[j] > S: # j chỉ lùi
j -= 1
cnt += j + 1 # B[0..j] đều ghép được với x
print(cnt)Có $n$ học sinh ($1 \le n \le 40$), học sinh thứ $i$ có sức mạnh $a_i$ ($1 \le a_i \le 10^9$). Chia tất cả thành hai đội (một đội có thể rỗng) sao cho chênh lệch tổng sức mạnh hai đội nhỏ nhất. In ra chênh lệch đó.
4
10 3 5 11📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<long long> allSums(const vector<long long> &v){
vector<long long> s = {0};
for(long long x : v){
int sz = s.size();
for(int t = 0; t < sz; t++) s.push_back(s[t] + x);
}
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long T = 0;
for(auto &x : a){ cin >> x; T += x; }
vector<long long> A = allSums(vector<long long>(a.begin(), a.begin() + n / 2));
vector<long long> B = allSums(vector<long long>(a.begin() + n / 2, a.end()));
sort(A.begin(), A.end());
sort(B.begin(), B.end());
long long best = T;
int j = (int)B.size() - 1;
for(long long x : A){
while(j >= 0 && 2 * (x + B[j]) > T) j--;
if(j >= 0) best = min(best, T - 2 * (x + B[j])); // tổng vừa <= T/2
if(j + 1 < (int)B.size()) best = min(best, 2 * (x + B[j + 1]) - T); // tổng vừa > T/2
}
cout << best;
return 0;
}import sys
def all_sums(v):
s = [0]
for x in v:
s += [y + x for y in s]
return s
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
T = sum(a)
A = sorted(all_sums(a[:n // 2]))
B = sorted(all_sums(a[n // 2:]))
best, j, m = T, len(B) - 1, len(B)
for x in A:
while j >= 0 and 2 * (x + B[j]) > T:
j -= 1
if j >= 0:
best = min(best, T - 2 * (x + B[j])) # tổng vừa <= T/2
if j + 1 < m:
best = min(best, 2 * (x + B[j + 1]) - T) # tổng vừa > T/2
print(best)Có $n$ thành phố ($2 \le n \le 10$), đi từ thành phố $i$ sang $j$ tốn $c_{ij}$ ($0 \le c_{ij} \le 10^6$, $c_{ii} = 0$, có thể $c_{ij} \ne c_{ji}$). Xuất phát từ thành phố 1, đi qua mỗi thành phố khác đúng một lần rồi quay về 1. Tìm tổng chi phí nhỏ nhất. Hãy cài bằng quay lui + nhánh cận.
4
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12 097📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n;
long long c[12][12], mn[12], best = LLONG_MAX, restMin = 0;
bool vis[12];
void Try(int u, int cnt, long long cur){ // đang ở u, đã thăm cnt thành phố
if(cnt == n){ best = min(best, cur + c[u][0]); return; }
if(cur + mn[u] + restMin >= best) return; // CẮT: cận dưới không tốt hơn kỷ lục
for(int v = 1; v < n; v++) if(!vis[v]){
vis[v] = true; restMin -= mn[v];
Try(v, cnt + 1, cur + c[u][v]);
vis[v] = false; restMin += mn[v];
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> c[i][j];
for(int i = 0; i < n; i++){
mn[i] = LLONG_MAX;
for(int j = 0; j < n; j++) if(j != i) mn[i] = min(mn[i], c[i][j]);
if(i > 0) restMin += mn[i];
}
vis[0] = true;
Try(0, 1, 0);
cout << best;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
c = [[int(data[1 + i * n + j]) for j in range(n)] for i in range(n)]
mn = [min(c[i][j] for j in range(n) if j != i) for i in range(n)]
vis = [False] * n
vis[0] = True
best = float('inf')
rest = sum(mn[1:]) # tổng mn của các thành phố chưa thăm
def Try(u, cnt, cur):
nonlocal best, rest
if cnt == n:
best = min(best, cur + c[u][0])
return
if cur + mn[u] + rest >= best: # CẮT: cận dưới không tốt hơn kỷ lục
return
for v in range(1, n):
if not vis[v]:
vis[v] = True; rest -= mn[v]
Try(v, cnt + 1, cur + c[u][v])
vis[v] = False; rest += mn[v]
Try(0, 1, 0)
print(best)
main()Có $n$ ứng viên ($1 \le n \le 100$), ứng viên $i$ có cân nặng $w_i$ ($1 \le w_i \le 10^6$) và điểm tài năng $t_i$ ($1 \le t_i \le 1000$). Cần chọn một nhóm có tổng cân nặng ít nhất $W$ ($1 \le W \le 1000$, đảm bảo tổng mọi cân nặng ≥ W) sao cho tỉ số $\frac{\sum t_i}{\sum w_i}$ lớn nhất. In ra phần nguyên của 1000 lần tỉ số đó.
3 15
20 21
10 11
30 311066📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, W;
long long w[105], t[105], f[1005];
const long long NEG = LLONG_MIN / 4;
bool check(long long y){ // có nhóm cân nặng >= W với sum(1000t - y w) >= 0?
fill(f, f + W + 1, NEG);
f[0] = 0;
for(int i = 0; i < n; i++){
long long val = 1000 * t[i] - y * w[i];
for(int j = W; j >= 0; j--) if(f[j] != NEG){
int nj = (int)min((long long)W, j + w[i]); // vượt W thì gộp về W
f[nj] = max(f[nj], f[j] + val);
}
}
return f[W] >= 0;
}
int main(){
cin >> n >> W;
for(int i = 0; i < n; i++) cin >> w[i] >> t[i];
long long lo = 0, hi = 1000000; // tìm y lớn nhất mà check(y) đúng
while(lo < hi){
long long mid = (lo + hi + 1) / 2;
if(check(mid)) lo = mid;
else hi = mid - 1;
}
cout << lo;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, W = int(data[0]), int(data[1])
w = [int(data[2 + 2 * i]) for i in range(n)]
t = [int(data[3 + 2 * i]) for i in range(n)]
NEG = float('-inf')
def check(y): # có nhóm cân nặng >= W với sum(1000t - y w) >= 0?
f = [NEG] * (W + 1)
f[0] = 0
for i in range(n):
val, wi = 1000 * t[i] - y * w[i], w[i]
for j in range(W, -1, -1):
if f[j] != NEG:
nj = j + wi if j + wi < W else W # vượt W thì gộp về W
if f[j] + val > f[nj]:
f[nj] = f[j] + val
return f[W] >= 0
lo, hi = 0, 10 ** 6 # tìm y lớn nhất mà check(y) đúng
while lo < hi:
mid = (lo + hi + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
print(lo)
main()Có $n$ đồ vật ($1 \le n \le 40$), đồ vật $i$ có khối lượng $w_i$ và giá trị $v_i$ ($1 \le w_i, v_i \le 10^9$). Túi chứa được tối đa $W$ ($1 \le W \le 10^{12}$). Chọn các đồ vật có tổng khối lượng không vượt $W$ sao cho tổng giá trị lớn nhất. Yêu cầu thuật toán chạy kịp với mọi bộ dữ liệu (không dựa vào may mắn của nhánh cận).
5 12
4 30
6 42
5 35
3 20
7 5085📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll, ll>> gen(const vector<pair<ll, ll>> &it){ // (tổng khối lượng, tổng giá trị)
vector<pair<ll, ll>> s = {{0, 0}};
for(auto [w, v] : it){
int sz = s.size();
for(int t = 0; t < sz; t++) s.push_back({s[t].first + w, s[t].second + v});
}
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; ll W;
cin >> n >> W;
vector<pair<ll, ll>> it(n);
for(auto &p : it) cin >> p.first >> p.second;
auto A = gen(vector<pair<ll, ll>>(it.begin(), it.begin() + n / 2));
auto B = gen(vector<pair<ll, ll>>(it.begin() + n / 2, it.end()));
sort(B.begin(), B.end());
vector<ll> Bw(B.size()), best(B.size());
for(size_t j = 0; j < B.size(); j++){
Bw[j] = B[j].first;
best[j] = max(j ? best[j - 1] : 0LL, B[j].second); // max tiền tố
}
ll ans = 0;
for(auto [wa, va] : A){
if(wa > W) continue;
int j = upper_bound(Bw.begin(), Bw.end(), W - wa) - Bw.begin() - 1;
ans = max(ans, va + best[j]); // j >= 0 vì B có (0, 0)
}
cout << ans;
return 0;
}import sys
from bisect import bisect_right
from itertools import accumulate
SH = 36 # gói (khối lượng, giá trị) thành một số: w << 36 | v
MASK = (1 << SH) - 1 # tổng giá trị <= 4.10^10 < 2^36
def gen(items): # tổng (khối lượng, giá trị) của mọi tập con, đã gói
s = [0]
for w, v in items:
p = w << SH | v
s += [x + p for x in s]
return s
data = sys.stdin.buffer.read().split()
n, W = int(data[0]), int(data[1])
it = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)]
A = gen(it[:n // 2])
B = sorted(gen(it[n // 2:])) # sắp số đã gói = sắp theo khối lượng
Bw = [x >> SH for x in B]
best = list(accumulate((x & MASK for x in B), max)) # max tiền tố của giá trị
ans = 0
for x in A:
wa = x >> SH
if wa <= W:
j = bisect_right(Bw, W - wa) - 1 # j >= 0 vì B có tập rỗng
ans = max(ans, (x & MASK) + best[j])
print(ans)
- 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