[Quy hoạch động] [NTUCoder] PSU01

Đề bài
Hướng làm
Gọi d[i,j] là số dãy chia hết có số cuối là i và có độ dài là j, ta có:
d[i,j]=d[i,j]+d[i',j-1] với i' là ước của i.
Để tăng tốc ta lưu sẵn các bước của i vào một mảng u để dùng lại khi cần
Đáp án là sum{d[i,m]} với i chạy từ 1 đến n.
Nhớ mod cho 10^9+7 sau mỗi lần tính toán.
Code

[DFS và BFS] [Tìm kiếm nhị phân] [Quy hoạch động] [NTUCoder] TREASURE

Đề bài
Hướng làm của mình
Chặt nhị phân số ngày, mỗi lần chặt DFS thử xem có đến được đảo kho báu không.
Cái chính là ta phải tìm số ngày để băng một vùng nào đó tan ra :)
Để tính được, ta dùng thuật sau của AresGod:
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
Hướng làm của BTC
Code