# OLP ngày 10/3
Đề 2016

## Bài 1 (khối 10): quân mã
BFS, tuy nhiên ở trên bảng 2 chiều chứ ko phải đồ thị thường.
Coi mỗi ô như một "đỉnh", còn cách di chuyển của quân mã là "cạnh".

## Bài 2 (k10): tải trọng
Đề yêu cầu tìm đường đi "sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể"
Nói cách khác, để $\min$ trọng số cạnh đạt $\max$.
Những bài có đề như thế này có thể TKNP trên đáp án.
TKNP được vì có tính chất tăng dần. Nếu chỉ dùng các cạnh $\ge d+1$ mà đi được thì đương nhiên dùng các cạnh $\ge d$ cũng đi được.
Giả sử $\min$ cạnh $\ge d$, cần xem thử $s$ có tới được $t$ không? Làm bằng BFS/ DFS/ DSU.
ĐPT $O(n \cdot \log)$

### Trâu:
Thay vì TKNP thì ta chạy for trọng số giảm dần và thêm từng cạnh vào, sau đó lại DFS/ BFS để xem thử $s$ đã đi tới được $t$ chưa. ĐPT sẽ là $O(z \times (m+n))$
Nếu dùng DSU theo cách này, ĐPT sẽ là $O(z + m + n)$ (vì $z \le 10^4$ nên có thể đếm phân phối thay vì sort, tuy nhiên không cần thiết lắm)

## Bài 3 (k10): chú tiểu
Yêu cầu đếm số cách đi, vậy nghĩ tới quy hoạch động (QHĐ).
Nhảy bước 2 hay bước 3 thì công thức tương tự nhau, như dãy Fibonacci.
Để xử lý yêu cầu "nhảy bước 3 tối đa một lần", thêm một chiều 0/1 vào mảng QHĐ.
Đặt $\texttt{dp[i][b]}$ là đếm số cách đi quãng đường độ dài $i$, $b = 0/1$ tương ứng với đã dùng lần nhảy 3 hay chưa?
Công thức:
$\texttt{dp[i][b] += dp[i-1][b]}$
$\texttt{dp[i][b] += dp[i-2][b]}$
$\texttt{dp[i][1] += dp[i-3][0]}$

## Bài 3 (k11): UAV
Nhìn thấy từ khóa: tìm giá trị nhỏ nhất, giá trị lớn nhất, ta biết bài này có khả năng giải được bằng QHĐ.
Công thức đi theo chiều thuận khá đơn giản: Đặt $f(i)$ là chi phí $\min$ để tới được $i$. ĐPT tính $f$ là $O(n \times L)$
Khi đi theo chiều ngược, ta phải xét toàn bộ những điểm nằm sau đó. Để ý rằng có thể thể làm giống `prefix-sum`, nhưng phải loại đi **một** vị trí, đó là $i + L$.
Đặt $g(i)$ là điểm cao nhất có được khi đi về $i$.
Ta có
$g(i) \leftarrow g(j) - x_i$ nếu $j \neq i + L$
$g(i) \leftarrow g(j) + x_i$ nếu $j = i + L$
Hướng giải quyết:
- Dùng `multiset`, erase đi và thêm lại sau
- Thay vì lưu phần tử lớn nhất, ta lưu hai phần tử lớn nhất, và so sánh với $g(i+L)$ để loại đi nếu cần

## Bài 2 (k11): BEAR
Bài toán tư duy khá hay. Cần nhận ra các điều sau:
- Biết rằng "đảo" là đỉnh và "phà" là cạnh.
- Chọn ra $n-1$ cạnh mà từ đỉnh $1$ thăm được mọi đỉnh. Vậy các cạnh được chọn ra phải tạo thành cây (khung).
- "Hành trình có thể phải lặp lại nhiều hơn 1 lần đối với một số đảo cũng như tuyến phà". Nếu hiểu ý, câu này có nghĩa là ta có thể đi qua một đỉnh hoặc một cạnh nhiều lần. Vậy hành trình đi tối ưu trông như thế nào?
Giả sử ta đã chọn ra được "cây khung" nào đó, cần biết chi phí của cây khung này là bao nhiêu?
Cách đi tối ưu nhất chính là phỏng theo quá trình DFS. Sau khi thăm tất cả đỉnh trong một cây con gốc $u$ nào đó, ta quay trở ngược lên nút cha của $u$.
- Nháp ra và thấy được chi phí là $2\times$ (tổng trọng số cạnh)
Nhớ cộng cả chi phí tại đỉnh (vì có trọng số). Chi phí sẽ là tổng $S_u \times deg(u)$ ($deg$ là bậc của đỉnh $u$)
Hiện tại, ta thấy vẫn còn khá "lấn cấn" với chi phí đỉnh.
- $(*)$ Để ý rằng với mỗi cạnh $(u,v)$, ta đi qua nó đúng hai lần: Một lần từ $u$, một lần từ $v$. Vậy ta có thể gán $T = 2T + S_u + S_v$. Bài toán quy về tìm cây khung nhỏ nhất (MST).

ĐPT: $O(m\log + n)$ (nếu sắp xếp bằng đếm p/p thì được $O(m+n)$ nhưng ko cần thiết)

## Bài 1 (k11): APROBOT
Kể cả muốn làm được subtask 1, cũng cần nhận xét khá trí tuệ.
Có thể đọc sol trên VNOJ.
### Hướng trâu
Đệ quy quay lui để lấy ra tất cả hoán vị.