Thành phố Cuồng loạn

Mô tả bài toán Cho một dãy số, tìm độ dài của dãy con giảm dài nhất (Longest Decreasing Subsequence - LDS). Sau đó, đếm số lượng các dãy con giảm có độ dài bằng độ dài này. Phân tích Câu hỏi thứ nhất - Tìm độ dài LDS Chúng ta sử dụng mảng dp[i] để lưu độ dài của dãy giảm dài nhất kết thúc tại vị trí i. Mảng pos[k] lưu vị trí của phần tử cuố ...

Liên kết cuộc thi \(\text{By DaiRuiChen007}\) A. [P11648] 2236 A.D. (4.5) Liên kết bài toán Ta thực hiện phân tách từng bit của \(k\), duy trì tập hợp \(S\) động. Mỗi thao tác cập nhật hoặc truy vấn \(w_x=\sum_{y\in S}a_{x\lor y}\). Sử dụng DSU để quản lý, mỗi nút chỉ có \(k\) tổ tiên thay đổi trọng số đường đi. Với \(\log n\) cạnh nhẹ, số lần ...

A. Xác định Ngày Đặc Biệt Bài toán yêu cầu kiểm tra xem cặp số nguyên (a, b) có trùng với một trong các ngày cố định: (1,7), (3,3), (5,5), (7,7), hay (9,9). Nếu khớp, in ra "Yes", ngược lại in "No". #include <iostream> #include <vector> using namespace std; int main() { int day, month; cin >> day >> month; ...

Problem A - Tìm phần tử khác biệt Cho ba số nguyên a, b, c. Trong đó có hai số bằng nhau, cần tìm số còn lại. Giải thuật: Kiểm tra các cặp bằng nhau, nếu a == b thì đáp án là c, tương tự cho các trường hợp khác. #include<bits/stdc++.h> using namespace std; int main() { long long test; cin >> test; while(test--) { ...

Bài A: Thống kê bài tập hoàn thành Đây là bài kiểm tra cơ bản, yêu cầu đếm số lượng chữ cái trong chuỗi đầu vào thỏa mãn điều kiện: số lần xuất hiện của chữ cái phải lớn hơn hoặc bằng vị trí tương ứng trong bảng chữ cái (A=1, B=2,...). Sử dụng mảng đếm để lưu tần suất xuất hiện, sau đó kiểm tra điều kiện cho từng chữ cái. #include <iostream& ...

Bài A: Lọc Ký Tự 2 Yêu cầu: Cho chuỗi ký tự đầu vào, in ra chuỗi chỉ chứa các ký tự số 2 Giải pháp: Xem mã nguồn #include <iostream> #include <string> using namespace std; int main() { string str; cin >> str; string result; for(char c : str) { if(c == '2') result += c; } cout << result; ...

Tôi ghét các cấu trúc dữ liệu khó hiểu! Huhu. Giới thiệu vấn đề Cho một dãy số nguyên dương có độ dài \(n\), thực hiện \(q\) truy vấn, mỗi truy vấn yêu cầu tìm giá trị của phần tử nhỏ thứ \(k\) trong đoạn \([l,r]\) của dãy. Nếu \(n,q \le 10^3\), đây chỉ là bài toán đơn giản cần duyệt toàn bộ; nhưng khi \(n,q \le 10^5\), phương pháp duyệt sẽ khô ...

Tổng quan bài toán Bài toán yêu cầu quản lý một cấu trúc cây, trong đó các đỉnh có thể được kích hoạt hoặc vô hiệu hóa theo thời gian thực. Với mỗi trạng thái, cần tính toán tổng trọng số cạnh nhỏ nhất để nối tất cả các đỉnh đang được kích hoạt lại với nhau thành một thành phần liên thông. Phân tích thuật toán Giả sử các đỉnh đang hoạt động đư ...

### CF1879F *2800 ★ Giá trị của một điểm được tính bằng h_i * ceil(a_i / x). Bước đầu tiên là sử dụng phương pháp phân đoạn trực tiếp, chia thành sqrt(n) khoảng và duyệt qua từng khoảng sẽ có độ phức tạp là O(Tn * sqrt(a_i)). Tuy nhiên không có bảo đảm về tổng n, nên ta cần tìm cách sử dụng log. Nhớ lại chuỗi điều hòa, khi liệt kê x, các phần t ...