Solution Sơ loại OLP MTTN 2023 (Chuyên Tin)
B1: TEAMBUILDING
Tóm tắt: Đếm số cách chia mảng
Sub 1: \(n \le 20\)
Có \(n\) người thì sẽ có \(n-1\) "khoảng trống" để ta đặt/ không đặt "vách ngăn" vào. Mỗi cách đặt như vậy là một cách chia nhóm.
Ví dụ:
[Hình vẽ] (soon^TM)
Quay lui \(O(2^n)\)
Sub 2: \(n \le 500\)
Cài chưa chuẩn ?
Sub 3: \(n \le 5000\)
Đặt \(f(i)\) là số cách để chia \(i\) người đầu.
Từ \(f(i)\) ta cập nhật \(f(j)\) với \(j > i\). Thêm một nhóm \(i+1, i+2, i+3, ..., j\). Nếu được thì \(\texttt{f(j) += f(i)}\)
(Nguyễn Minh Huy, A5 K37 LQĐ)
B2: FRUITMARKET
Tóm tắt: Hoa sẽ đi mua quả theo vòng tròn: mỗi tiệm mua \(\le 1\) quả xong rồi qua tiệm tiếp theo. Dừng lại khi không đủ tiền mua quả rẻ nhất.
Bước 1: Tính xem thử Hoa đã đi được bao nhiêu vòng trước khi \(m<\) tổng?
Đặt \(S\) là tổng dãy \(a\). Số vòng \(= [m / S]\).
Giả sử sau khi mua các vòng thì còn dư \(m'\) tiền.
Thuật trâu:
Mô phỏng lại toàn bộ quá trình mua hàng của Hoa.
for (int i = 1; m >= Min; i++) {
if (i > n) i = 1;
if (m >= a[i]) {
m -= a[i];
ans++;
}
}
Sub 1: \(n = 2\)
Có các giai đoạn:
- Còn đủ tiền mua \(2\) quả
- Chỉ đủ tiền mua quả rẻ nhất
- Thiếu tiền
Dùng phép chia để xem mỗi giai đoạn xảy ra trong bao lâu (bao nhiêu vòng?)
Sub 2: \(a_1 \le a_2 \le ... \le a_n\)
Tính mảng tiền tố (prefix-sum).
Mô phỏng lại các vòng đi chợ của Hoa.
Do \(a\) tăng dần nên những loại quả được mua sẽ là những quả ở các quầy đầu tiên.
Do đó chỉ cần TKNP để xác định là mua tới quả nào thì hết tiền, xong lại bắt đầu vòng mới.
// Credit: OLP4CT587
void sub2()
{
int res = 0;
//prefix-sum
for (int i = 1; i <= n; i++)
a[i] += a[i - 1]; //trở thành tổng i số đầu tiên
while (m >= a[1])
{
int k = upper_bound(a + 1, a + 1 + n, m) - a - 1;
//upper_bound: tìm vị trí đầu tiên > hẳn m
// lại -1 đi để ra vị trí cuối cùng <=
res += (m / a[k]) * k;
m = m % a[k];
}
cout << res;
}
Sub 3: \(m \le \min a\cdot 10^6\)
Đáp án chắc chắn \(\le 10^6\). Tuy nhiên nếu cày trâu như trên thì sẽ TLE (theo lí thuyết) vì có trường hợp quả rẻ nhất nằm ở một vị trí duy nhất, và ta phải chạy for hết \(n\) phần tử mới tìm được quầy rẻ đó để mua.
VD:
n = 1e5, m = 1e18
a[i] = 10^9 với mọi i, ngoại trừ tại vị trí i = ? thì a[i] = 1
Ý tưởng:
http://online.vku.udn.vn/src/88371
Dùng DSU, tính mảng \(nxt(i)\) là vị trí tiếp theo trên vòng tròn mà \(\le m\) (số tiền còn hiện tại)
Sub 4:
Đơn giản
Thuật toán sau mô phỏng lại thuật trâu:
Code trên của: baoduong23042007
Giải thích: Vòng lặp while bên ngoài thực hiện rất ít lần, vì câu lệnh m %= sum sẽ giảm \(m\) đi ít nhất \(2\) lần (nếu m > sum).
Nếu m < sum thì phần "cày trâu" sẽ giảm \(m\) đi xuống rất bé ?
Phức tạp
(Chưa kiểm chứng được đúng sai nhưng thấy có một số thí sinh code BIT)
Xét \(O(n)\) thời điểm đặc biệt: ngay khi \(m\) giảm xuống bé hơn giá trị lớn thứ \(i\) trong dãy \(a\).
Quầy hàng nào đắt hơn \(m\) thì ta "xóa" nó đi.
Về ý tưởng thì vẫn dùng phép chia (đi thành nhiều vòng) giống subtask 1, cho tới khi \(m\) bé hơn mốc tiếp theo.
Vậy việc cần quan tâm là xét trong một đoạn liên tiếp sẽ có bao nhiêu số chưa bị "xóa"
Có cần BIT hay không?
B3: DISTANCE
Tóm tắt: Cho cây \(n\) đỉnh. Có \(k\) đỉnh đặc biệt. Hỏi khoảng cách từ \(u\) tới đỉnh đặc biệt gần nhất (\(\neq u\)) là bao nhiêu?
Sub 1: \(n \le 200\)
Thuật \(O(n^2):\) Tính trước k/cách giữa mọi cặp đỉnh trên cây (BFS/DFS), lưu vào mảng.
Sau đó chạy for \(n^2\) để tìm cà phê gần nhất.
Sub 2: \(n \le 10^5, k \le 50\)
Với mỗi \(u\), ta duyệt qua \(k\) đỉnh đặc biệt, cần lấy k/cách từ \(u\) tới đỉnh đó.
Vậy lúc đầu cần tính trước bằng cách BFS/DFS từ mỗi một trong \(k\) đỉnh.
Hoặc: dùng LCA để tính (phức tạp).
ĐPT: \(O(nk)\)
Sub 3 + 4:
Làm chưa tối ưu la
http://online.vku.udn.vn/src/89811
QHĐ trên cây. DFS 2 lần để tính hai loại khoảng cách:
- từ nút con cháu cập nhật lên \(u\)
- từ nút tổ tiên (nằm ngoài cây gốc \(u\)) cập nhật cho \(u\).
Đặt dp_down[u], dp_up[u] lần lượt là k/c loại 1,2 ở trên.
Khoảng cách loại 1 tính được bằng dfs thông thường. Gọi dfs để tính dp_down của những nút con cháu trước, sau đó gán dp_down[u] = max(dp_down[v] + w).
https://viblo.asia/p/quy-hoach-dong-tren-cay-LzD5d9B4KjY
Khoảng cách loại 2 phải tính ngược lại một chút. Tận dụng khoảng cách loại 1, và kết quả từ các nút cha & tổ tiên ta cập nhật cho các nút con cháu.
Có hai trường hợp:
dp_up[v] = dp_up[u] + w(từ nút tổ tiên của \(u\) cập nhật cho \(v\))- Từ một nhánh khác trong cây con gốc \(u\), gọi là \(v_2\), cập nhật cho \(v\). Ta có
dp_up[v] = dp_down[v2] + w2 + w1(từ nút \(v_2\), đi theo hai cạnh để tới \(u\), rồi tới \(v\))
Nếu nhóm biểu thức trên lại, ta thấy cần lấy \(\max\) của tất cả dp_down[.] + w[.] của những nhánh khác \(v\).
Sub 3:
Ta lưu hết vào một multiset, khi duyệt tới nhánh hiện tại thì xóa nó đi để tính, xong lại thêm vào. ĐPT \(O(n\log)\)
Sub 4:
Cần tìm \(\max\) mọi nhánh còn lại nhanh hơn. Có thể:
- Hướng 1: Làm giống prefix-sum
- Hướng 2: Lưu lại hai giá trị bé nhất.
B4: CARDGAME
\(O(n^2)\)
Thử hết mọi đoạn con (chạy for \(l,r\)), lấy tổng đoạn trừ max
Full (idea)
Giả sử \(a_i\) lớn hơn mọi số trong đoạn \([l,r]\) (dùng stack/ gì đó để tìm l min, r max).
Tính prefix-sum thôi: Lấy max của S từ i tới r, trừ cho min của S từ l-1 tới i-1.
Segment Tree