Hướng dẫn NTUCoder Round #13

admin - 04/10/2015

Bài A: VIETCHU - Viết bằng chữ

      Bài này chỉ dùng if cho đúng.

Bài B: TIMSO2 - Tìm số

    - Phân tích M thành tích các thừa số nguyên tố. Nếu có thừa số nguyên tố từ 11 trở lên, in ra -1. Còn lại các thừa số 2, 3, 5, 7. Ta có thể nhân một số thừa số lại như sau (theo đúng thứ tự):

    1) 2*2*2 = 8
    2) 3*3 = 9
    3) 2*3 = 6
    4) 2*2 = 4

Sau đó in ra các thừa số 2, 3, 4, 5, 6, 7, 8, 9 theo thứ tự từ bé đến lớn. Độ phức tạp O(logM) để phân tích thừa số của số M.

Cách giải của bạn ndkhaivn hay hơn:

Chia M lần lượt cho các số 9, 8, 7, 6, 5, 4, 3, 2 (không chia hết tiếp được nữa mới chuyển sang số tiếp theo). Cuối cùng nếu M > 1 nghĩa là không có kết quả (-1). Nếu M=1, in các thừa số 2, 3, 4, 5, 6, 7, 8, 9 theo thứ tự từ bé đến lớn. Độ phức tạp cũng O(logM).

Bài C: POWER - Số mũ

    - Gọi X là tích các thừa số nguyên tố của A , vậy N cần tìm có dạng q*X. Lúc này chỉ cần duyệt q trong khoảng 1 đến A/X và dùng hàm mũ log để xem (q*X)^(q*X) có chia hết cho A hay không.

Bài D: HARA - Dán hàng rào

      Chọn 1 trong hai cách dán như sau (cách nào ít miếng dán hơn thì lấy):

      - Dán theo từng cột (chú ý 2 cột gần nhau cao bằng nhau dùng chung 1 miếng dán)

      - Dán 1 hình chữ nhật dài nhất bên dưới. Phần còn lại phía trên có thể xem là các hàng rào con. Áp dụng đệ quy để tính. Độ phức tạp worst case O(N2)

Bài E: STUDY - Kế hoạch học tập

      - Gọi f[i][j] là số điểm tối đa khi ôn i môn đầu tiên trong tổng cộng j ngày. CTTH: f[i][j]=f[i-1][k] + a[i][j-k] với k<=j , xử lý thêm phần truy vết. Độ phức tạp O(N*M^2)

 Bài F: TREASURE - Đảo châu báu

Cách 1:

      - Dùng quy hoạch động để tính số ngày mà băng tại từng ô sẽ tan ra. Độ phức tạp O(M*N)

      - Ít nhất là 0 ngày và nhiều nhất là max(M, N) ngày thì sẽ có đường đi. Chặt nhị phân để tìm, ứng với mỗi lần tìm áp dụng BFS để tìm xem có đường đi hay không. Độ phức tạp O(M*N*log(max(M,N)))

Cách 2:

      - Dùng quy hoạch động để tính số ngày mà băng tại từng ô sẽ tan ra. Độ phức tạp O(M*N)

      - Dùng BFS tìm tất cả, để tính số ngày ít nhất. Mỗi ô có thể đi qua 2-3 lần gì đó (???). Độ phức tạp khoảng O(3*M*N).

Bài G: TRUTIN - Truyền tin

     - Nếu xem mỗi chuỗi là 1 đỉnh của đồ thị thì ta có một đồ thị đầy đủ với trọng số mỗi cạnh là số ký tự khác nhau giữa 2 đỉnh. Áp dụng thuật toán Prim để tìm cây khung nhỏ nhất (độ phức tạp O(N2)). Sau đó xét từng cạnh trong cây khung. Nếu trọng số một cạnh > K/2 , truyền đầy đủ. Nếu trọng số một cạnh <= K/2, truyền đỉnh sau theo đỉnh trước. Độ phức tạp là quá trình tính các cạnh của đồ thị: O(K*N2).

CÁC PHẢN HỒI

  • ndkhaivn - 05/10/15 08:35
    độ phức tạp O(sqrtM) a ơi @@
  • truongvit274 - 05/10/15 09:25
    Bài E QHĐ sao nhỉ?
  • only_love97 - 05/10/15 10:02
    Bài E: f[i][j] là dành j ngày cho môn thứ j
    ->f[i][j]=max(f[i][j],f[i-1][j-k]), k=0->j
  • only_love97 - 05/10/15 10:03
    Bài E: f[i][j] là dành j ngày cho môn thứ i
    ->f[i][j]=max(f[i][j],f[i-1][j-k]), k=0->j
  • ngocjr7 - 05/10/15 10:41
    bài B độ phức tập là xích ma i(2 đến 9) ( log(i,n) ) chứ sao lại là sqrt(n) được
  • AresGod - 05/10/15 18:26
    @only_love97: xúi bậy hả cu :v em bỏ a[i][k] đâu rồi :v
  • AresGod - 05/10/15 22:57
    @Thầy admin: Thầy ơi chỗ f[i][j]=f[i-1][k] + a[i][j-k] sửa lại thành f[i][j]=max(f[i-1][k] + a[i][j-k]) mới đúng chớ, em bị thiếu
  • only_love97 - 06/10/15 10:05
    AresGod: à chết e viết thiếu =)))), sr a yêu
  • angelo - 06/10/15 21:40
    em không hiểu bài Bài F: TREASURE - Đảo châu báu lắm. không hiểu làm sao hết
    ai chỉ em với ạ!!
  • mrtan_lovelife - 06/10/15 22:56
    @angelo bạn không hiểu phần nào vậy?
  • angelo - 07/10/15 07:54
    "Mỗi ô có thể đi qua 2-3 lần gì đó" câu này là sao ạ?? mà bfs thế nào??
  • nxphuc - 07/10/15 10:22
    chắc không ai chơi sol bựa bài Đảo kho báu như mình =))))
    nghĩ lại cũng rảnh thật, có thuật kia ngắn gọn k làm, đi quất cái source gần 200 lines
  • mrtan_lovelife - 07/10/15 11:56
    @angelo Là BFS đến khi nào hết phần tử để xét thì thôi, mỗi lần xét đến đỉnh (x,y) nào đó thì cập nhật thời gian các ô xung quanh, ô nào mất nhiều ngày hơn ô đang xét thì cập nhật lại ngày của ô đó và cho vào hàng đợi. Kết quả là số ngày của ô (u2,v2).
  • mrtan_lovelife - 07/10/15 11:59
    @nxphuc sol của anh thế nào vậy, em đọc C++ ko quen
  • AresGod - 07/10/15 13:01
    disjoint set )))
  • trunghai95 - 07/10/15 13:18
    Bài hàng rào chỉ cần dán theo chiều ngang thôi là luôn tối ưu rồi, không cần thử dán theo chiều dọc.
  • nxphuc - 07/10/15 20:20
    @mrtan: xây dựng đồ thị sau đó dùng DSU tìm 1 phần cây khung nối giữa 2 điểm đầu cuối :3
  • phamhuuthien - 07/10/15 22:39
    Trời đất, mình ghi trong lịch là chủ nhật tuần này o.O
  • nguyentamdat - 08/10/15 14:39
    giúp e cái qhd bài F với
  • AresGod - 08/10/15 15:10
    @nguyentamdat: em push những ô không là băng ban đầu vào queue , gọi a[u][v] là số ngày ít nhất để ô (u,v) tan (khởi tạo = inf) -> BFS từ những ô trong queue đến 4 ô liền kề, ô nào có a[u][v] hiện tại lớn hơn thì cập nhật lại rồi push ô vào đó vào queue tiếp , khi nào xong sẽ xây được mảng a.
Back to Top