Ha Hoang's Blog

Luyện tập trên NTU Coder . Tham khảo lý thuyết: cuốn Kỹ thuật thiết kế thuật toán của Lê Minh Hoàng . Bài tập: Hiệu số Dãy con tăng dài nhất

QBTICKET - Mua vé tàu hoả Tuyến đường sắt từ thành phố A đến thành phố B đi qua một số nhà ga. Tuyến đường có thể biểu diễn bởi một đoạn thẳng, các nhà ga là các điểm trên đó. Tuyến đường bắt đầu từ A và kết thúc ở B, vì thế các nhà ga sẽ được đánh số bắt đầu từ A (có số hiệu là 1) và B là nhà ga cuối cùng. Giá vé đi lại giữa hai nhà ga chỉ phụ thuộc vào khoảng cách giữa chúng. Cách tính giá vé như sau: Khoảng cách giữa hai nhà ga (X) Khoảng cách 0 < X <= L1 -> Giá vé C1 Khoảng cách 0 < X <= L2 -> Giá vé C2 Khoảng cách 0 < X <= L3 -> Giá vé C3 Nghĩa là với các giá vé C1, C2, C3 tương ứng bạn sẽ đi quảng đường tối đa là L1, L2, L3. Vé để đi thẳng từ nhà ga này đến nhà ga khác chỉ có thể đặt mua nếu khoảng cách giữa chúng không vượt quá L3. Vì thế nhiều khi để đi từ nhà ga này đến nhà ga khác ta phải đặt mua một số vé. Hơn thế nữa, nhân viên đường sắt yêu cầu hành khách chỉ được giữ đúng một vé khi đi trên tàu và vé đó sẽ bị huỷ khi hành k...

PNUMBERS HSPC14J MPRIME

Bài tập áp dụng kỹ thuật tham lam, mức độ dễ. ATM Tìm số Vắt sữa bò Cắm điện Khiêu vũ Giao đấu (OLP 2014) Đổ xăng Thu hoạch táo Nối chuỗi xích Lì xì Phân nhóm (Jakarta 2014 - A) Thang máy (Codeforces) Tặng hoa 20/11

Đây là một trong những kĩ thuật cơ bản, tương đối đơn giản và dễ hiểu. Tài liệu ở đây: Kĩ thuật quay lui Kĩ thuật quay lui Danh sách bài tập luyện tập: Liệt kê chuỗi nhị phân Liệt kê chuỗi hoán vị Liệt kê chuỗi k-phân Trò chơi Line Dãy ngoặc đúng Cái túi Ốc sên ăn rau Tám hậu Hái nấm

DANH SÁCH BÀI TẬP THỨ 7 (16/01/2015) S ố hoàn hảo 2 Chồng gạch Tổng nguyên tố Nguyên tố - nguyên tố cùng nhau

Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...