Code tìm thành phần liên thông mạnh C++ - RR; cách sử dụng; Code tìm thành phần song liên thông C++ - RR; cách sử dụng; Bài tập trên VNOI; Bài H - ACM ICPC Vietnam Regional 2017; Lời giải; Tìm đường đ
Một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh. Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có h
Thuật toán: Đầu tiên, ta dựng cây khung nhỏ nhất S của đồ thị ban đầu: Sau đó, ta lần lượt đi tìm cây khung nhỏ nhất chứa mỗi cạnh của đồ thị. Với 1 cạnh i nối 2 đỉnh u, v với trọng số w, có 2 trường
Đây là một thuật toán mở rộng của thuật toán Euclid ở trên. GCD (A,B) có một tính chất rất đặc biệt: Nó luôn có thể được biểu diễn dưới dạng phương trình Ax+By=GCD (A,B). Thuật toán sẽ cho ta biết một
Theo thuật toán Euclide mở rộng ra cũng rút ra được: abs (x) < abs (b / d) và abs (y) < abs (a / d) Áp dụng: Đây có thể xem là thuật toán dùng để thay thế định lí nhỏ Fermat mà các bạn thường dùng cho
Thuật toán Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi (queue) để chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng. Bước 1: Khởi tạo Các đỉnh đều ở trạng thái chưa được đánh dấu. Ngoại
QBCAKE - Cắt bánh Giới hạn. Thời gian: 0.143s Bộ nhớ: 1536MB Mã nguồn: 50000 bytes Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo).Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa.
Công đoạn 2: Xếp R*L quân domino thành một dãy độ dài L (L ≤ 10 6 ), mỗi hàng có đúng R (R ≤ 8) quân (có thể được hiểu như xếp vào hình chữ nhật kích thước R * L). Điểm độc đáo trong công trình này là
Hiện nay bài toán chu trình Hamilton hình như vẫn chưa có thuật toán tốt hoàn toàn. Quay lui vét cạn với cận tốt thì sẽ qua được khá nhanh, bởi trong khi làm bài thì rất khó để make được test chết.
phi (n): số số nguyên tố cùng nhau với n và nhỏ hơn hoặc bằng n (Phi hàm Euler) mobius (n): Hàm mobius thường được dùng trong các bài toán đếm sử dụng nguyên lý bù trừ: Nếu n có ước là số chính phương
Phi hàm Euler (Euler's totient function) Định nghĩa: \phi (N) là số số nguyên tố cùng nhau với N trong đoạn từ 1 đến N. Cách tính: Ta đã biết phân tích một số ra thừa số nguyên tố (factorization) là b
Hãy tìm cây khung nhỏ nhất của đồ thị G Input Dòng 1: Chứa hai số n, m (1
Đường đi Euler (Eulerian path/trail) trên một đồ thị (bất kể là vô hướng hay có hướng, đơn hay đa đồ thị) là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần. Chu trình Euler (Eulerian cycle/circui
Thư viện mẫu chuẩn STL trong C++ chia làm 4 thành phần là: Containers Library : chứa các cấu trúc dữ liệu mẫu (template) Sequence containers. Vector; Deque; List; ... push_back : thêm vào ở cuối vecto
Machine Learning là một chủ đề rộng lớn với rất nhiều chủ đề con. Thay vì cố gắng đưa ra những định nghĩa chung chung, bài viết sẽ chỉ tập trung vào một chủ đề duy nhất: Phân loại (Classification). Bà
Kiểu chuỗi string trong thư viện STL của C++. Thư viện chuẩn STL (Standard Template Library) cung cấp kiểu string (xâu ký tự), giúp các bạn tránh khỏi hoàn toàn các phiền phức nêu trên.Các chỉ thị #in
Do đó, ta cần phải cải tiến thuật toán bằng lũy thừa ma trận với số trạng thái cho $1$ lớp $\mathrm{dp}$ là $6 \times 6 \times 6 \space / \space 2 = 108$.
Bài toán này khá giống bài toán xếp balô ("khối lượng" là mệnh giá, "giá trị" là 1), chỉ có một thay đổi nhỏ: tổng giá trị yêu cầu là nhỏ nhất. Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi L
Bài toán dãy con tăng dài nhất được áp dụng rộng rãi ở nhiều lĩnh vực: Toán học (thuật toán, lý thuyết ma trận, lý thuyết đại diện) hay Vật Lý. Thuật toán LIS giải trong độ phức tạp O (n*logn) với "n"
Chiến thuật tiếp cận này gọi là vét cạn (brute force) - xét qua tất cả các trường hợp có thể xảy ra để tìm kết quả. Mỗi khi bạn gặp một bài toán, đầu tiên phải xét đến là test xấu nhất có thể có là gì
Độ dài mảng. Đối với mảng cộng dồn, do ta cần thêm một hằng số c ở đầu mảng, độ dài của mảng S (c, A) là n + 1, nhiều hơn 1 phần tử so với mảng A gốc. Ngược lại, mảng hiệu được dựng dựa trên hiệu của