Thành phố Cuồng loạn

1. Điều khiển vị trí hiển thị văn bản ngẫu nhiên Trong lập trình console, việc giả lập vị trí hiển thị có thể thực hiện thông qua việc in các dòng trống và khoảng trắng. Ví dụ dưới đây minh họa cách sử dụng hàm rand() để hiển thị một chuỗi ký tự tại các tọa độ ngẫu nhiên trên màn hình sau mỗi khoảng thời gian nhất định. #include <stdio.h&gt ...

Mục tiêu là tính số lượng các rừng cây cơ bản không đánh số có kích thước n và giới hạn độ vào không vượt quá k. Đặt N=n, K=k. Độ phức tạp của thuật toán là O(n^3 log n). Tính dp_n biểu diễn số cách tạo cây không đánh số với n đỉnh thỏa mãn giới hạn độ số. Sau đó, liệt kê kích thước của chu trình, sử dụng nguyên lý Burnside để tính số cây cơ bả ...

Bài A — Kiểm tra khả năng xây dựng chuỗi đích từ hai nguồn Bài toán yêu cầu xác định xem có thể tạo chuỗi c độ dài n sao cho mỗi ký tự c[i] phải trùng khớp với ít nhất một trong hai ký tự a[i] hoặc b[i]. Nếu mọi vị trí đều thỏa mãn, kết quả là "NO" (tức là không tồn tại ký tự nào ở c mà không xuất hiện tại cùng chỉ số ở a hoặc b); ngược lại, in ...

A. Đếm số lượng "khoảng tốt" tối tiểu Một khoảng [x, x+1] luôn là "khoảng tốt" vì hai số liên tiếp luôn nguyên tố cùng nhau. Hơn nữa, đây cũng là khoảng tốt tối tiểu, do các khoảng đơn phần tử như [x,x] không thể là khoảng tốt (vì gcd(x,x) = x ≠ 1 nếu x > 1). Với mọi khoảng có độ dài lớn hơn 2, nó sẽ chứa ít nhất một khoảng con độ dài 2 — do đó ...

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 1001: Nướng Thịt Bài toán yêu cầu tính tổng giá trị lớn nhất từ các phần tử được chọn, với điều kiện không nhất thiết phải chọn tất cả. Đặc biệt cần xử lý trường hợp không chọn phần tử nào. const int MAX_VAL = 1e9; const int SIZE = 200010; void solve() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i ...

Bài A: Xử Lý Số Nguyên Yêu cầu: Với số nguyên n và số lần thao tác tối đa max_ops, mỗi lần có thể bình phương hoặc lấy căn bậc hai làm tròn xuống. Đếm số lượng giá trị khác nhau có thể tạo ra. Phương pháp: Phép bình phương luôn sinh ra giá trị mới. Khi thực hiện căn bậc hai, nếu kết quả không phải số nguyên thì mỗi lần thao tác tiếp theo có thể ...

Phân tích bài toán hệ số Binomial biến thể Trong bài toán này, chúng ta được cung cấp một đoạn mã giả lập cách tính một bảng tương tự như tam giác Pascal nhưng có quy luật thay đổi. Đề bài yêu cầu tính giá trị tại các vị trí $(n_i, k_i)$ dựa trên quy tắc tính toán đó. Bằng cách thực hiện chạy thử (dry run) hoặc lập bảng giá trị nhỏ, ta có thể ...

A. Level K Terms Một chuỗi được coi là hợp lệ nếu thỏa mãn hai điều kiện: Đầu tiên, với giới hạn \(z_i = \max(i, k \cdot z_{i-k+1})\), ta cần \(a_i < z_i\). Thứ hai, tồn tại một vị trí \(i\) sao cho tổng của \(k\) phần tử bắt đầu từ \(i\) nhỏ hơn \(i \cdot k\). Giải thuật bao việc chuẩn hóa các phần tử \(a_i\) bằng cách lấy \(\min(a_i, z_i - ...