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
  • giangcoder - 18/12/21 17:05
    tam giác vuông cân độ phức tạp = 1 mấy bác ơi

    #include <iostream>
    #include <cmath>

    using namespace std;

    int main ()
    {
    long long n, a, b, c;
    cin >> n;

    c = n * 2;
    a = sqrt(c);
    b = a + 1;

    if (c == a * b)
    cout << "YES";
    else
    cout << "NO";
    return 0;
    }
  • giangcoder - 18/12/21 17:10
    cách chứng minh thì tui có chứng minh trên paint với con chuột của tui nha
    tui gửi lên drive rồi mấy ông có thể lên đọc nha, có nhiều chỗ làm hơi tắt mong mọi người hiểu đc nha!!!

    https://drive.google.com/file/d/15YSR52PveLVthEPoPAJc95fTKXutUnvE/view?usp=sharing
Back to Top