Hướng dẫn NTUCoder Happy Lunar New Year 2016

middlest - 04/02/2016

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

- 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.

CÁC PHẢN HỒI

  • mrtan_lovelife - 04/02/16 23:06
    Bài J chặt nhị phân theo cạnh, tính diện tích tam giác vuông cân thực tế cộng với sai số là ra, đpt O(log(n))
  • phuleethanh - 04/02/16 23:07
    Con nhung bai khac sao Middlest
  • phuleethanh - 04/02/16 23:10
    Bài J O(1): Điều kiện để pt x2+x-2n=0 có nghiệm nguyên: delta=8n+1 là một số chính phương
  • waterfall2311 - 04/02/16 23:13
    bài D mình dùng mảng đánh dấu số bậc của các đỉnh xong cout ra các đỉnh có bạc >=k sao sai nhỉ mn ?
  • Nguyenthaihoc - 05/02/16 13:07
    nhìn bài J, cần chi chặt nhị phân dữ vậy :v
  • hanhlv270597 - 05/02/16 17:10
    waterfall2311: mình cũng chả hiểu s sai nữa.
  • mrtan_lovelife - 05/02/16 20:25
    @Nguyenthaihoc cũng chỉ là 1 nhận xét khác của bài toán thôi
  • phuleethanh - 06/02/16 14:11
    @hanhlv270597: Sai la dung roi. Vi du n=4,k=2: 1 quen 2, 1 quen 3, 1 quen 4. Khi do chi dua vao so bac thi ta chi co moi 1. Nhung ma 2,3,4 ko duoc moi thi 1 di du tiec chi co mot minh ko quen ai ca --> ko dap ung yeu cau bai toan
  • phuleethanh - 06/02/16 14:12
    Hom qua sau khi contest ket thuc minh moi hieu cai nay
  • hanhlv270597 - 06/02/16 15:02
    ừa. mình cảm ơn. mình cũng nhận ra cái sai r.
  • tuancanhktpm - 18/04/16 12:19
    Bài đầu tớ giải sao có chưa tới 10 bước nhỉ? Lấy temp = inp*2. x = sqrt(temp) if(x*(x+1) == temp return true else return fail.
    Giải như vậy có sai k?
  • tuancanhktpm - 18/04/16 12:25
    Mà 2 tam giác vuông cân ghép lại thì bằng 1 hình vuông chứ k phải hình chữ nhật. phương trình x(x+1) = 2n là kết quả của 1 số 2n nào đó có thể ghép thành 1 hình vuông cạnh x đơn vị
  • tuancanhktpm - 18/04/16 12:33
    Lúc đầu bị sai ở chỗ này về sau cộng thêm 2 dấu chấm vào 2 đầu cho thành hình vuông, temp = n*2+2, x = sqrt(n). if(x*(x-1) == n) return true
Back to Top