Hướng dẫn giải của huế_ LÁT NỀN NHÀ
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính số Fibonacci thứ n (với n từ 1 đến 100) và trả lời cho nhiều truy vấn. Tuy nhiên, số Fibonacci tăng rất nhanh, vượt quá kiểu dữ liệu nguyên chuẩn (64-bit) nên cần phải xử lý số lớn (Big Integer). Input gồm số lượng truy vấn T và T số nguyên n, output là số Fibonacci tương ứng với mỗi n. Dựa trên các solution, số Fibonacci được tính theo quy luật: F(1)=1, F(2)=2, F(n)=F(n-1)+F(n-2) (hoặc F(0)=1, F(1)=1, F(2)=2).
Các cách tiếp cận
Cách Quy hoạch động với BigInt thủ công (String)
#include <bits/stdc++.h>
using namespace std;
string cong(string a, string b) {
string kq = "";
int nho = 0;
while (a.size() > b.size()) b = '0' + b;
while (a.size() < b.size()) a = '0' + a;
for (int i = a.size() - 1; i >= 0; --i) {
int t = (a[i] - '0') + (b[i] - '0') + nho;
nho = t / 10;
t %= 10;
kq = char(t + '0') + kq;
}
if (nho > 0) kq = '1' + kq;
return kq;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("build.inp", "r", stdin);
freopen("build.out", "w", stdout);
int t;
cin >> t;
vector<string> f(205);
f[1] = "1"; f[2] = "2";
for (int i = 3; i <= 100; ++i) {
f[i] = cong(f[i-1], f[i-2]);
}
while (t--) {
int n;
cin >> n;
cout << f[n] << '\n';
}
return 0;
}
- Time Complexity: O(T * N * L) ~ O(10^5) (với N=100, L~21)
- Space Complexity: O(1) (mảng 100 phần tử)
Approach này sử dụng mảng các chuỗi ký tự để lưu trữ kết quả Fibonacci. Hàm cong thực hiện cộng hai chuỗi số học thủ công bằng cách duyệt từ phải sang trái, xử lý số nhớ. Vì N chỉ lên tới 100, số Fibonacci F(100) chỉ có khoảng 21 chữ số, nên việc cộng chuỗi rất nhanh. Ta precompute (tính trước) toàn bộ dãy từ 1 đến 100 và trả lời truy vấn trong O(1).
Cách Quy hoạch động với BigInt tích hợp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
class BigInt {
private:
vector<int> digits;
public:
BigInt() {}
BigInt(int num) {
if (num == 0) digits.push_back(0);
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
BigInt operator+(const BigInt& other) const {
BigInt result;
int carry = 0;
int max_len = max(digits.size(), other.digits.size());
for (int i = 0; i < max_len || carry; ++i) {
int sum = carry;
if (i < digits.size()) sum += digits[i];
if (i < other.digits.size()) sum += other.digits[i];
result.digits.push_back(sum % 10);
carry = sum / 10;
}
return result;
}
void print() {
if (digits.empty()) { cout << 0; return; }
for (int i = digits.size() - 1; i >= 0; --i) cout << digits[i];
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("build.inp", "r")) {
freopen("build.inp", "r", stdin);
freopen("build.out", "w", stdout);
}
int t; cin >> t;
vector<BigInt> f(105);
f[1] = BigInt(1);
f[2] = BigInt(2);
for (int i = 3; i <= 100; ++i) f[i] = f[i-1] + f[i-2];
while (t--) {
int n; cin >> n;
f[n].print();
cout << '\n';
}
return 0;
}
- Time Complexity: O(T * N * L)
- Space Complexity: O(N * L)
Đây là cách tiếp cận cấu trúc dữ liệu/Object-Oriented hơn. Tạo một lớp BigInt lưu trữ các chữ số trong vector. Toán tử cộng được overload để thực hiện phép cộng số lớn. Code này cleaner và dễ bảo trì hơn so với việc viết hàm cộng chuỗi rải rác. Logic tính toán vẫn là quy hoạch động.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(T * N * L) ~ O(10^5) (với N=100, L~21) | O(1) (mảng 100 phần tử) | Quy hoạch động với BigInt thủ công (String) |
| 2 | O(T * N * L) | O(N * L) | Quy hoạch động với BigInt tích hợp |
Bài học kinh nghiệm
- Vì N nhỏ (<= 100), ta có thể precompute (tính trước) toàn bộ kết quả và trả lời truy vấn ngay lập tức thay vì tính lại mỗi lần.
- Số Fibonacci tăng rất nhanh (F(100) ~ 3.54x10^20), vượt quá khả năng lưu trữ của
long long(10^18), buộc phải sử dụng BigInt hoặc chuỗi. - Bài toán này là một dạng kinh điển của quy hoạch động kết hợp xử lý số lớn.
Lỗi thường gặp
- Lỗi quy luật dãy Fibonacci: Đôi khi F(1)=1, F(2)=1 hoặc F(1)=1, F(2)=2. Cần kiểm tra kỹ đề bài hoặc code mẫu để xác định quy luật đúng (Solution 2 & 3 dùng F(1)=1, F(2)=2).
- Lỗi tràn số khi dùng biến nguyên (int/long long) cho các số lớn.
- Quên iosbase::syncwith_stdio(0); cin.tie(0); có thể khiến việc đọc ghi chuỗi lớn bị chậm.
- Nếu dùng string, thứ tự ký tự trong string (độn số 0 ở đầu) cần được chuẩn hóa trước khi cộng.
Bình luận