XÂU DUY NHẤT
- Thuật toán duyệt đơn thuần: ta dùng một con trỏ i để duyệt từ đầu đến cuối xâu
+ Nếu s[i] chưa xuất hiện thì ta đánh dấu s[i] đã xuất hiện và tăng ans
+ Nếu s[i] đã xuất hiện rồi: Lúc này ta cập nhật giá trị lớn nhất. Đồng thời cập nhật lại mảng đánh dấu. Đoạn mới sẽ bắt đầu từ vị trí xuất hiện a[i] trước đó + 1.
KHIÊU VŨ 3
- Dùng kỹ thuật chặt nhị phân để tìm ra những cặp đôi phù hợp.
- Với Ai thì ta chặt nhị phân, tìm Ai-k và Ai+k trong đoạn từ i+1 đến n.
VESUSGAME
- Dùng QHĐ
CHÊNH LỆCH
- Đầu tiên vét cạn: xét lần lượt từng truy vấn, mỗi truy vấn [u,v] ta xét lần lượt các cách chia từ u đến v
For i:=1 to q do
For j:=u to v do {xem xét cách chia tại vị trí j này}
Với cách vét này ta sẽ ăn được 12 test đầu, các test sau thì TLE. Ta phải tìm cách cải tiến vòng for thứ 2.
- Cách 2: Với mỗi cặp [u,v] ta sẽ chặt nhị phân để tìm ra vị trí có độ chênh lệch nhỏ nhất. Tuy nhiên cách chặt nhị phân bài này có khác đôi chút so với các bài bình thường. giả sử ta có vị trí vtres là vị trí thuộc đoạn [u,v] mà tại đây độ chênh lệch nhỏ nhất. Ta nhận thấy trên đoạn [u,vtres] độ chênh lệch sẽ giảm dần, còn trên đoạn [vtres,v] độ chênh lệch tăng dần --> độ chênh lệch trên đoạn [u,v] là một hàm vừa giảm vừa tăng. Các bạn cải tiến cách chặt phù hợp là được.
CẶP ĐÔI HOÀN HẢO
- DFS kết hợp với BIT để đếm.
- |a-b|<=K --> -K <= a-b <= K --> b-K <= a <= b+K : Nên khi dfs đến nút b, ta tìm tất cả các nút a là tổ tiên của b (các nút đã được thăm) thỏa mãn điệu kiện trên. Việc đếm này ta có thể dùng BIT: (getbit(b+k) – getbit(b-k-1).
CẶP XÁCH
- Bài này dùng QHĐ, cải tiến từ bài toán cái túi.
- f[i,j] là số cách chọn thỏa mãn nếu chọn từ các loại vật C1..Ci và trọng lượng đúng bằng j.
- Vẽ bảng như trong bài toán cái túi, thử điền đầy đủ bảng này bạn sẽ tìm ra được công thức QHĐ.
ĂN BUFFET
- Ta thấy cách chọn sơ khai nhất ta nghĩ đến là O(2^n) nhưng N<=32 là khá lớn nên ta nghĩ đến duyệt phân tập.
- Chia ra hai tập A và B (tối đa 16 phần tử mỗi tập).
- Tập A: Duyệt quay lui và lưu lại tất cả cách chọn. Với mỗi cách chọn ta lưu lại tổng trọng lượng và tổng giá trị.
- Tập B: Duyệt quay lui tất cả cách chọn trên tập B. Với mỗi cách chọn có tổng trọng lượng là sumw, tổng giá trị là sumv: ta sẽ tìm ra những j tập tương ứng trong A thỏa mãn U <= sumw+Asum[j] <= V. Để tìm nhanh ta sắp xếp tập A và chặt nhị phân. Giả sử ta tìm được các tập trong A thỏa mãn yêu cầu đó là các tập nằm từ vị trí vtdau đến vtcuoi. Ta sẽ tìm tập nào có giá trị lớn nhất trong đoạn các tập thỏa mãn này (Dùng IT, RMQ ... để tìm).
