Thành phố Cuồng loạn

Có N (2 ≤ N ≤ 8.000) con bò có mã số riêng biệt trong khoảng từ 1 đến N. Trong một hành động thiếu suy nghĩ, chúng đã ghé thăm cái "bể nước" gần nhà và uống hơi quá nhiều bia trước bữa tối. Khi đến lúc xếp hàng để ăn tối, chúng không xếp theo thứ tự tăng dần của mã số. Thật tiếc là FJ không có cách nào để sắp xếp chúng. Hơn nữa, ông ấy cũng kh ...

Bài A: Xoay vòng dãy số Bài toán yêu cầu chúng ta thực hiện một phép biến đổi trên dãy số nguyên. Cụ thể, cần đưa k phần tử cuối cùng của dãy lên đầu tiên, giữ nguyên thứ tự tương đối, sau đó nối tiếp bởi các phần tử còn lại. Hướng tiếp cận Đây là một bài toán thao tác cơ bản trên mảng. Chúng ta không cần thực hiện việc xoay vòng thực sự trên b ...

Cây đoạn (Segment Tree) là một cấu trúc dữ liệu phổ biến trong lập trình thi đấu, đặc biệt hiệu quả cho các bài toán yêu cầu thực hiện xen kẽ các thao tác cập nhật đoạn và truy vấn đoạn trên dãy số. Cấu trúc này có thể xử lý hiệu quả các phép toán trên đoạn với độ phức tạp O(log n) cho mỗi thao tác cập nhật hoặc truy vấn. Nguyên lý hoạt động ...

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 ...