Thành phố Cuồng loạn

Thiết Lập Ký Hiệu Để đảm bảo tính thống nhất trong các phần phân tích dưới đây, chúng ta định nghĩa các biến như sau: n: Tổng số nhóm hoặc loại vật phẩm. C: Giới hạn dung tích của túi (sức chứa). weight[i]: Khối lượng tiêu hao của vật phẩm loại i. value[i]: Giá trị thu được khi lấy vật phẩm loại i. quantity[i]: Số lượng vật phẩm loại i có thể ...

Bài 1 Chỉ giải thành công bài này. Qua việc mô phỏng các ví dụ và lập bảng cho tất cả các cặp [i,j], có thể dễ dàng nhận ra quy luật. Việc hiện thực hóa khá phức tạp, xem mã nguồn để hiểu rõ hơn. Mã nguồn bài 1 #include<bits/stdc++.h> using namespace std; #define ll long long const ll MAX_SIZE = 5 * 1145140, MOD = 998244353; int length ...

Bài A: Chọn số may mắn Áp dụng thuật toán tìm kiếm theo chiều sâu (DFS) để sinh các tổ hợp số thỏa mãn điều kiện. Điểm chú ý là cần thêm lệnh return khi kết thúc quá trình đệ quy: #include <bits/stdc++.h> using namespace std; int numbers[100], selected[10], visited[100]; int total; void generate(int depth) { if (depth > 6) { ...

A. [QOJ5099] Đường hành hương (1) Giải bài toán bằng cách sử dụng định lý tổ hợp và thuật toán Ex-Lucas để tính toán hiệu quả. Công thức tổ hợp được biểu diễn dưới dạng tổng các tổ hợp chập i của 2n phần tử, với điều kiện i > n. Độ phức tạp thời gian là O(ω(p)log p), trong đó ω(p) là số lượng số nguyên tố nhỏ hơn p. #include<bits/stdc++.h&g ...

Bài A: Đếm số phần tử có thể chèn giữa hai số Nếu hai số A và B khác nhau, kiểm tra xem hiệu của chúng có chẵn hay không. Nếu chẵn, có thể chèn một số ở giữa → tổng cộng 3 số. Nếu lẻ, chỉ có thể giữ nguyên hai đầu mút → 2 số. Trường hợp A == B, chỉ có duy nhất một giá trị. #include <bits/stdc++.h> using namespace std; int main() { in ...

Bài toán: 688. Xác suất tồn tại của mã tế trên bàn cờ Cách tiếp cận: Có tối đa k * n * n trạng thái, đáp ứng yêu cầu về thời gian. Phương pháp 1: Đệ quy + Tìm kiếm theo chiều sâu (DFS). Độ phức tạp thời gian là O(k * n²), chi tiết xem trong chú thích. Phiên bản C++: class Solution { public: // tám hướng di chuyển int huongDiChuyenX[8]={ ...

A. Diverse Game Bài toán yêu cầu hoán đổi các phần tử trong ma trận sao cho không có phần tử nào giữ nguyên vị trí cũ. Một cách tiếp cận đơn giản là dịch chuyển các giá trị theo một vòng tuần hoàn. Với mỗi phần tử tại vị trí (i, j) trong ma trận n x m, ta gán giá trị mới bằng (a[i][j] % (n * m)) + 1. Phép toán này đảm bảo mọi giá trị đều đư ...

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

Mô tả bài toán Cho một mảng số nguyên, tìm độ dài của dãy con tăng nghiêm ngặt dài nhất. Dãy con được hình thành bằng cách xóa phần tử nhưng giữ nguyên thứ tự các phần tử còn lại. Ví dụ Nhập: [10,9,2,5,3,7,101,18] Kết quả: 4 (dãy con [2,3,7,101]) Nhập: [0,1,0,3,2,3] Kết quả: 4 Nhập: [7,7,7,7,7,7,7] Kết quả: 1 Ràng buộc 1 ≤ độ dài mảng ≤ 25 ...