Thành phố Cuồng loạn

Nội Dung Về Thuật Toán Tham Lam Thuật toán tham lam (Greedy) là phương pháp tìm lời giải bằng cách lựa chọn phương án tốt nhất tại mỗi thời điểm cụ thể với mong muốn đạt được kết quả tối ưu toàn cục. Để đảm bảo một chiến lược tham lam có thể áp dụng thành công cho một bài toán, ta cần chứng minh rằng nó không bỏ sót những trường hợp có lợi hơn ...

Tìm kiếm theo chiều rộng (BFS) là kỹ thuật duyệt đồ thị hoặc lưới bắt đầu từ một điểm, mở rộng đều các nút ở cùng một cấp độ trước khi đi sâu hơn. Thực hiện bằng cấu trúc hàng đợi, mỗi đỉnh chỉ được thêm vào một lần nên không cần hoàn tác trạng thái đã duyệt như trong DFS. Cài đặt BFS tìm đường đi ngắn nhất Đoạn mã sau minh họa cách tìm đường ...

Chào buổi sáng! (00:50:13) Đây là lần thi khá thuận lợi: giải được tổng cộng 6 bài toán. A. Tạo Dữ Liệu Thử Sử dụng cấu trúc ánh xạ để đếm tần suất ký tự. #include<bits/stdc++.h> using namespace std; const int MAX_SIZE = 2e5+10; int test_cases, n, m; char input_array[MAX_SIZE]; unordered_map<char, int> frequency; int main() { ci ...

Bài viết này giới thiệu các kỹ năng sử dụng GDB hiệu quả trong môi trường lập trình thi đấu. Nội dung tập trung vào các lệnh ít phổ biến nhưng cực kỳ hữu ích khi debug chương trình C++. Mọi ví dụ đều giả định bạn đã biết cơ bản về GDB và đã biên dịch với cờ -g. Mã nguồn mẫu #include <iostream> #include <vector> int tinhFibonacci(i ...

Mô tả bài toán Cho một khoảng thời gian tổng thể bắt đầu từ 1 đến $T$. Có $N$ nhân sự có thể được điều phối, trong đó mỗi nhân sự $i$ chỉ sẵn sàng làm việc trong một khoảng thời gian cố định $[S_i, E_i]$. Yêu cầu đặt ra là cần chọn ra số lượng nhân sự ít nhất sao cho tại mọi thời điểm $t \in [1, T]$, luôn có ít nhất một người đang làm việc. Kết ...

Khái niệm cơ sở tuyến tính Cơ sở tuyến tính là một tập hợp các số được xây dựng từ một dãy cho trước, sao cho bất kỳ phần tử nào trong dãy gốc đều có thể được biểu diễn dưới dạng XOR của một số phần tử thuộc cơ sở. Kỹ thuật này thường được sử dụng để giải quyết các bài toán liên quan đến XOR của tập con. Các tính chất quan trọng Mọi phần tử t ...

Phân Tích Yêu Cầu Đầu Vào Bài toán yêu cầu xác định số lượng đơn vị tàu chiến trên một ma trận lưới kích thước R x C, trong đó ký tự # đại diện cho thân tàu và . là mặt biển. Điều kiện tiên quyết là cần kiểm chứng tính hợp lệ của cấu hình bàn cờ. Một trạng thái bị coi là sai lệch nếu xuất hiện nhóm ba ký tự # xếp cạnh nhau tạo thành hình chữ T ...

Phân tích mô hình và ràng buộc Hệ thống quản lý một hàng đợi gồm n đối tượng, mỗi đối tượng i mang một hệ số chờ đợi Di. Khi một đối tượng là người thứ k được xử lý, chi phí không hài lòng sinh ra là (k - 1) * Di. Để điều chỉnh thứ tự xử lý, hệ thống hỗ trợ một bộ nhớ đệm hoạt động theo cơ chế ngăn xếp (LIFO). Nhiệm vụ là tìm cách luân chuyển c ...

Khái niệm cơ bản Mảng hậu tố (Suffix Array) là một cấu trúc dữ liệu quan trọng trong xử lý xâu ký tự, dùng để sắp xếp tất cả các hậu tố của một xâu theo thứ tự từ điển. Cùng với mảng height, nó hỗ trợ hiệu quả cho các bài toán như tìm chuỗi con chung dài nhất, đếm số lượng xâu con phân biệt, v.v. Ký hiệu sử dụng Xâu ký tự s có độ dài n, đán ...

Tổng quan về thuật toán tìm kiếm nhị phân Tìm kiếm nhị phân (Binary Search) là một kỹ thuật tối ưu dựa trên chiến lược chia để trị. Khác với lầm tưởng phổ biến rằng thuật toán này chỉ áp dụng được trên các dãy số có tính đơn điệu (tăng dần hoặc giảm dần), bản chất cốt lõi của tìm kiếm nhị phân nằm ở việc xác định điểm biên của một tính chất cụ ...