Từ điển/Tính toán trước
Tiền đề: phân khối.
“Đánh bảng” kiểu nguồn sơ khai là: trong thi, tính trước đáp án cho mọi input có thể, lưu lại, rồi dùng mảng trong code để tra và in ra.
Kỹ thuật này chỉ phù hợp với miền giá trị nhỏ (ví dụ input chỉ có một số và phạm vi rất nhỏ), nếu không thì có thể khiến code quá dài, MLE, hoặc thời gian tiền xử lý quá lâu.
Ví dụ
Đặt \(f(x)\) là số bit \(1\) trong biểu diễn nhị phân của số nguyên \(x\). Cho \(n\) nguyên dương (\(n\leq 10^9\)), tính \(\sum_{i=1}^n f^2(i)\).
Nếu với mỗi \(n\) đều output \(f(n)\), ngoài nguy cơ MLE còn có thể vượt giới hạn độ dài code khiến không biên dịch được.
Ta tối ưu bảng này. Dùng ý tưởng phân khối, chọn bước \(m\) (phụ thuộc độ dài code), với khối thứ \(i\) tính:
Sau đó khi trả lời dùng phân khối: khối đầy đủ dùng giá trị tiền xử lý, phần còn lại vét cạn.
Nhìn chung, dạng bài này tính một giá trị \(f(x)\) rất nhanh, nhưng cần cộng (hoặc nhân/ghép nhanh) nhiều giá trị nên enumerate sẽ TLE; khi không có cách standard, “đánh bảng phân đoạn” là lựa chọn tốt.
Lưu ý
Nếu số mũ không cố định nhưng phạm vi nhỏ, cũng có thể đánh bảng.
Ví dụ
「BZOJ 3798」特殊的质数：đếm số nguyên tố trong \([l,r]\) biểu diễn được dưới dạng tổng bình phương hai số nguyên.
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply