Thành phố Cuồng loạn

This article explores three distinct algorithmic challenges centered around number theory, combinatorial state compression, and randomized geometric inversion. Smooth Number Generation via Multi-Queue Merging To generate the k-th b-smooth number (i.e., a positive integer whose prime factors are all among the first b primes), a greedy multi-que ...

Bài toán này yêu cầu chúng ta tìm số lượng hoán vị của các số từ 1 đến n sao cho có chính xác K số i (1 < i < n) thỏa mãn điều kiện a_{i-1} < a_i và a_i > a_{i+1}. Một số a_i thỏa mãn điều kiện này được gọi là một "điểm cực đại cục bộ" hay "đỉnh" của hoán vị. Kết quả cần được tính theo modulo 998244353. Để giải quyết bài toán này, ...

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