Contest đầu tiên giải được full hết các problem.
Nhưng do đề dễ.
---
CHDNT1 - Collect the Bomb.
Bài này yêu cầu đếm số lượng ký tự # trong xâu $S$. Duyệt xâu là ra.
---
CDHNT2 - Smallest difference.
Đề yêu cầu tìm một cặp $a_i, a_j\ (i \neq j)$ sao cho $|a_i - a_j|$ nhỏ nhất. Bài này có hướng giải là sort tăng dần trước, nhưng luôn nhớ là $a_0$ và $a_1$ tuy là 2 phần tử nhỏ nhất nhưng chưa chắc $|a_0 - a_1|$ đạt min. Do vậy phải duyệt theo cặp, như thế mới tìm được $i$ và $j$ phù hợp. Mình hiểu sai nên mất 1 sub câu này.
---
CDHNT3 - Cut the Tree.
Tóm tắt: có $N$ cái cây được sắp xếp giảm dần. Trong một lượt, cái cây nhỏ nhất bị chặt đi, sau đó chiều cao của các cây còn lại bị tỉa bớt một khoảng bằng với chiều cao cái cây vừa bị chặt. Sau mỗi lượt, output ra số lượng cây còn lại (có chiều cao > 0).
Hướng giải bài này thật ra không cần các thao tác cộng trừ. Giả sử ta có cây thấp nhất bị remove khỏi nhóm cây, khi đó cây đứng trước nó sẽ trở thành cây nhỏ nhất (2 cây có chiều cao khác nhau) hoặc cây đứng trước nó cũng bị remove luôn (2 cây có chiều cao bằng nhau).
Vậy nên, đến đây ta chỉ cần dựng một min heap. Trong mỗi lượt, ta output số lượng node còn lại của heap, sau đó tiến hành loại các node có giá trị bằng với node đỉnh. Ta dừng lại khi heap rỗng.
---
CDHNT4 - Find F.
Bài này yêu cầu tính $N!\ (1 \leq N \leq 20)$. Ta có thể tính $x!$ với $1 \leq x \leq 20$ lưu vào một mảng trước, sau đó chỉ cần gọi mảng đã tính.
---
CDHNT5 - Tumanji Animals.
Bài này yêu cầu tìm con vật có ID xuất hiện nhiều nhất. Nghe đến đấy là nhận ra cấu trúc dữ liệu std::map rồi.
Cái gì quan trọng phải nhắc lại:
- với std::map<int, int>::iterator it, it->first là key và it->second là value.
- Mặc định map sẽ sort theo key.
---
Happy coding!
No comments:
Post a Comment