Bài J. Tam giác vuông cân
* Nhận xét
- Nếu ta đem ghép 2 tam giác vuông cân có 1 cạnh góc vuông độ dài a dấu chấm thì ta sẽ được một hình chữ nhật chiều dài là a + 1 và chiều rộng là a. Ví dụ hình sau là ghép 2 tam giác vuông cân có độ dài 2 dấu chấm
.png)
- Lúc đó, số dấu chấm trong hình chữ nhật sẽ bằng diện tích hình chữ nhật, tức là bằng a(a + 1)
- Để tính số dấu chấm trong tam giác vuông cân độ dài a chấm ta chỉ cần đem kết quả trên chia cho 2 là xong.
- Như vậy, để kiểm tra xem với n dấu chấm cho trước có thể tạo thành tam giác vuông cân không ta chỉ cần kiểm tra phương trình x(x + 1) = 2n có nghiệm nguyên dương hay không, dễ thấy x <= sqrt(2n), từ đó ta có duyệt x từ 1 đến 2n để kiểm tra. ĐPT O(sqrt(n))
Bài C. Xâu chung
- Với mỗi kí tự của s1 và s2 tương ứng, ta "giải nén" nó, sau đó đếm số xâu chung của 2 tập đã giải nén được rồi nhân với kết quả
* Ví dụ với s1 = ???, s2 = abc
- Kí tự ? sau khi giải nén là tập {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- Kí tự a sau khi giải nén là tập {0, 1, 2, 3}
- Kí tự b sau khi giải nén là tập {1, 2, 3, 4}
- Kí tự c sau khi giải nén là tập {2, 3, 4, 5}
- Kí tự a và ? sau khi giải nén có 4 xâu chung, kí tự b và ? sau khi giải nén có 4 xâu chung, kí tự c cũng vậy, nên kết quả là 4 x 4 x 4 = 64
Bài D. Người nổi tiếng
- Coi mỗi người nổi tiếng là đỉnh của một đồ thị vô hướng, nếu người x quen với người y thì đỉnh x và y có cạnh nối.
- Dùng Stack chứa những người nổi tiếng mà quen ít hơn K người, xét các đỉnh trong đồ thị, nếu đỉnh nào có bậc bé hơn k thì đẩy vào Stack
- Lần lượt lấy các đỉnh trong Stack ra, với mỗi đỉnh u trong Stack, tìm đỉnh v sao cho u có cạnh nối với v và v không có trong Stack, giảm bậc của v, nếu bậc của v bé hơn K thì đẩy vào Stack.
- Loại những người có trong Stack ra ta sẽ tính được kết quả.
Trên đây là lời giải 1 số bài tập, các bạn có thể trao đổi với nhau bên dưới về lời giải các bài còn lại.
