Thành phố Cuồng loạn

1. Phân tích bài toán và những điểm mấu chốt Bài toán yêu cầu tìm tổng giá trị lớn nhất của một đường đi trong cây nhị phân. Theo định nghĩa, một đường đi là một chuỗi các nút trong đó mỗi cặp nút liên tiếp đều có cạnh nối và mỗi nút chỉ xuất hiện tối đa một lần. Điều này dẫn đến hai đặc điểm quan trọng: Điểm bắt đầu và kết thúc tự do: Đ ...

Bài T1: Phép XOR Để giải quyết bài toán này, chúng ta sử dụng phương pháp chênh lệch. Mỗi lần thay đổi sẽ được chuyển đổi thành dạng chênh lệch như sau: 1 1 x 1 x x x -1 -1 -1 Sau đó, chúng ta thực hiện tổng tiền tố theo đường chéo để tính kết quả cuối cùng. Dưới đây là mã nguồn C++ minh họa: #include <bits/stdc++.h> using namespace ...

Nghiên cứu và thực hành Dynamic Programming trên cấu trúc cây Cấu trúc cây là nền tảng quan trọng trong nhiều bài toán tối ưu hóa và xử lý đồ thị. Khi kết hợp với Dynamic Programming (DP), chúng ta có thể giải quyết hiệu quả các bài toán liên quan đến đường đi, phân bố trọng lượng, lựa chọn nút độc lập, và quy hoạch có ràng buộc. Bài viết này t ...

A. Định dạng văn bản Orange Để xử lý đầu vào đa dòng, chúng ta dùng vòng lặp while kết hợp hàm getline. Biến đếm dòng và tìm độ dài tối đa của các dòng: #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string line; int soDong = 0, maxDai = 0; while (getline(cin, line)) { ...

Kỹ thuật số位 DP giải quyết bài toán đếm số thỏa mãn điều kiện trong khoảng [L, R] thông qua việc xử lý từng chữ số. Mô hình trạng thái thường có dạng dp[length][firstDigit][target], với length là độ dài số, firstDigit là chữ số đầu tiên, target là giá trị cần đếm. Bài toán minh họa: Đếm tần suất chữ số (P2602) Xây dựng mảng digitCount với dig ...

Bài 1: Tổng số cặp số tốt I Đối với bài toán này, chúng ta cần đếm số lượng cặp chỉ số (i, j) sao cho nums1[i] chia hết cho nums2[j] * k. Do giới hạn kích thước của mảng là nhỏ (n, m <= 50), chúng ta có thể sử dụng phương pháp mô phỏng trực tiếp (brute-force) bằng cách duyệt qua tất cả các cặp có thể. class Solution { public: int numberO ...

Nhân ma trận Một phép toán cơ bản nhưng quan trọng trong nhiều bài toán lập trình là phép nhân ma trận. Để thực hiện phép nhân giữa hai ma trận \( A \) và \( B \), điều kiện cần là số cột của \( A \) phải bằng số hàng của \( B \). Cụ thể, nếu \( A \) có kích thước \( n \times m \) và \( B \) có kích thước \( m \times k \), thì kết quả \( C = A ...

A - Mã Trạng Thái Trong bài toán này, chúng ta cần kiểm tra một mã trạng thái HTTP đã cho. Nếu mã trạng thái nằm trong khoảng từ 200 đến 299 (bao gồm cả hai giá trị biên), điều đó biểu thị một phản hồi thành công. Ngược lại, nó được coi là một lỗi hoặc trạng thái không thành công. Cách tiếp cận Bài toán yêu cầu mô phỏng trực tiếp điề ...

A. Lost Luggage - Tối ưu hóa Lưu lượng và Quy hoạch động Bài toán yêu cầu tính toán dòng chảy cực đại qua một cấu trúc phân tầng. Thay vì giải trực tiếp bài toán dòng chảy极大 (Max-flow), ta chuyển đổi sang bài toán tìm cắt nhỏ nhất (Min-cut) vì đối với đồ thị này, giá trị cắt nhỏ nhất tương đương với kết quả cần tìm. Sử dụng quy hoạch động có ...

C - Quả Cam Mandarina Đề xuất một phương pháp khác với độ phức tạp \(\mathcal{O}(n \log n)\). Đặt cho vị trí thứ \(i\), vị trí đầu tiên bên trái lớn hơn nó là \(L_i\), và vị trí đầu tiên bên phải lớn hơn nó là \(R_i\). Ta nhận thấy rằng giá trị tối ưu cho vị trí \(i\) khi làm \(x\) chính là \((R_i-L_i-1)\times val_i\). Có thể sử dụng danh sách ...