# Sơ lược lời giải PVHOI 3.0

## Day 1, bài 1: Gắp thú bông
Bài này đòi hỏi bạn phải có kĩ năng đọc đề tốt. Bắt đầu đọc từ đoạn chợ Helio (Oileh).
### Tóm tắt
Gắp thú bông:
Càng nhiều thì càng rẻ (mô tả bởi dãy $s,p$)
Những con gấu (thú bông) có trong máy là các đoạn $[l,r]$
Ta biết chính xác thứ tự gắp: bé $\rightarrow$ lớn
Cần tìm số lần gáp ít nhất để được $\ge t$ tiền

### Sub 1
### Sub 2
### Sub 3
### Sub 4
### Thuật chuẩn
Nhận xét: giá trị gấu tăng dần mà giá tiền gắp giảm dần. Vậy nếu đặt $a_i$ là tiền lời của riêng lần gắp thứ $i$, ta có $a_i$ giảm dần.
Xét những phần tử âm, nằm đầu mảng $a$. Rõ ràng nếu chỉ gắp trong những lượt đầu tiên này thì không thể ra tiền lời dương được. Vậy phải bắt đầu TKNP từ vị trí dương đầu tiên.
Cần thêm prefix-sum và phần cài đặt khoai, nên nhắm tới sub.

Ý tưởng hay của GS.PVH: giá trị trung bình tăng dần

## Day 1, bài 2: Trang trí ngày xuân
Bắt đầu đọc từ "Khu vườn nhà Nhật Quang".

Nhận thấy $c$ nhỏ nên nghĩ ngay tới QHĐ bitmask.
Có một cách đặt trạng thái như sau:
$f(i,m_1,m_2)$ là xét tới dòng thứ $i$, trạng thái của 2 dòng gần nhất ($r,r-1$) lưu trong $m_1,m_2$ (trạng thái 0/1: đã có quân mã ở vị trí .. hay chưa).
Cách này thì chuyển trạng thái vẫn là $O(2^c)$ nên ĐPT $O(r \times 2^{3c})$

Thực tế, ta thấy dòng tiếp theo chỉ duyệt qua các tập con của những ô chưa bị "chiếu" thôi. Vậy ĐPT là $O(r \times 2^c \cdot 3^c)$

## Day 1, bài 3:
Đề bài này rõ sẵn.
Quan sát: tuy hàm `gspvhcute` trông giống xử lý online nhưng tất cả $e,u,v$ đều tính trước được từ những biến `seed,add,mul,q` ban đầu mà không phụ thuộc vào kết quả `res` trước đó $\rightarrow$ xử lý offline?

### Sub 1:
Tổng số cạnh không đổi, luôn là $n-1$. Vậy với mỗi truy vấn hoàn toàn có thể duyệt qua các cách chọn cạnh & check chu trình.
ĐPT $O(q \cdot 2^n)$, (có thể $\times n$ nhưng dễ TLE)
### Sub 2 (khó):
Ta quan tâm tới $C$ là số chu trình đi qua cạnh $u,v$. Mỗi khi thêm hoặc xóa cạnh $u,v$, ta chỉ việc thêm bớt lượng $C$ này.
Cây có dạng đường thẳng. Xét hai đỉnh $u,v$ liên tiếp nhau trên cây lúc đầu, tại một thời điểm nào đó:
- Nếu $u$ không nối $v$ thì hiển nhiên không có chu trình nào chứa $u,v$.
- Nếu có $d$ cạnh nối giữa $u,v$:
+ Nếu $d = 1$ thì $C=$ số đường đi đơn từ $u$ tới $v$.
+ Nếu $d > 1$ thì $C=d\cdot (d-1)/2$

### Sub 3:
Nếu đã hiểu như trên thì thao tác đếm có thể làm trong $O(n^2)$ để đạt ĐPT $O(q\cdot n^2)$
Dựng một cây DFS có gốc là $u$. Thêm cả những cạnh "thừa" và định hướng chúng lại, ta có được một DAG (đương nhiên DAG này không chứa $(u,v)$ vừa bị xóa đi).
Tính $f(x)$ là số đường đi khác nhau từ $u$ tới $x$ qua các cung của DAG. Thì $C = f(v)$

### Vì trình độ có hạn nên chỉ đoán được ĐPT các subtask ở sau
### Sub 4: $O((n+q)q)$
### Sub 5: $O((n+q)\log)$
### Sub 6: $O(n+q)$