Hướng dẫn giải của Lucky Luke
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 đếm số cách Lucky Luke leo lên một cầu thang có n bậc. Các bậc thang bị hỏng không thể bước lên. Lucky có thể đi lên 1 bậc hoặc nhảy lên 2 bậc (từ bậc i lên i+1 hoặc i+2). Xuất phát từ bậc 1 (luôn hợp lệ), cần tìm số cách để đến được bậc n. Kết quả cần in ra phần dư khi chia cho 15122011.
Các cách tiếp cận
Cách Quy hoạch động cơ bản (DP)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 15122011;
const int N = 100005;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<bool> is_broken(n + 1, false);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
is_broken[x] = true;
}
// dp[i] là số cách đến được bậc i
vector<int> dp(n + 1, 0);
// Khởi tạo
if (!is_broken[1]) dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (is_broken[i]) {
dp[i] = 0;
} else {
dp[i] = (dp[i-1] + dp[i-2]) % MOD;
}
}
cout << dp[n] << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận trực quan nhất. Ta sử dụng mảng dp với dp[i] là số cách để đến được bậc thứ i. Công thức quy hoạch động: dp[i] = dp[i-1] + dp[i-2] nếu bậc i không bị hỏng, ngược lại dp[i] = 0. Điều kiện dừng: dp[1] = 1. Ta tính tuần tự từ bậc 2 đến bậc n.
Cách Quy hoạch động tối ưu (Không gian O(1))
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 15122011;
int main() {
int n, k;
cin >> n >> k;
vector<bool> broken(n + 1, false);
for (int i = 0; i < k; ++i) {
int x;
cin >> x;
broken[x] = true;
}
long long prev2 = 0; // dp[i-2]
long long prev1 = 0; // dp[i-1]
// Khởi tạo cho bậc 1
if (!broken[1]) {
prev1 = 1;
}
for (int i = 2; i <= n; ++i) {
if (broken[i]) {
prev2 = prev1;
prev1 = 0;
} else {
long long current = (prev1 + prev2) % MOD;
prev2 = prev1;
prev1 = current;
}
}
cout << prev1 << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n) (chỉ lưu mảng broken)
Thay vì lưu toàn bộ mảng dp, ta chỉ cần 2 biến để lưu số cách đến 2 bậc liên tiếp trước đó (prev1 và prev2). Điều này giảm đáng kể bộ nhớ sử dụng. Logic tính toán tương tự như cách 1 nhưng thay vì truy cập mảng dp, ta cập nhật các biến.
Cách Xử lý đặc biệt cho các đoạn liên tiếp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 15122011;
const int N = 100005;
int main() {
int n, k;
cin >> n >> k;
vector<bool> broken(n + 1, false);
vector<int> breaks;
breaks.push_back(0);
for (int i = 0; i < k; i++) {
int x;
cin >> x;
broken[x] = true;
breaks.push_back(x);
}
breaks.push_back(n + 1);
// Nếu bậc 1 hoặc n bị hỏng
if (broken[1] || broken[n]) {
cout << 0 << endl;
return 0;
}
vector<int> fib(n + 2);
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = (fib[i-1] + fib[i-2]) % MOD;
}
long long ans = 1;
for (int i = 1; i < breaks.size(); i++) {
int gap = breaks[i] - breaks[i-1] - 1;
if (gap < 0) {
cout << 0 << endl;
return 0;
}
// Nếu có 2 bậc hỏng liên tiếp, không thể đi qua
if (i > 1 && breaks[i] - breaks[i-1] == 1) {
cout << 0 << endl;
return 0;
}
// Nếu có 3 bậc hỏng liên tiếp, không thể đi qua
if (i > 1 && breaks[i] - breaks[i-1] == 2) {
cout << 0 << endl;
return 0;
}
if (gap > 0) {
ans = (ans * fib[gap]) % MOD;
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Cách tiếp cận này tối ưu hơn cho các trường hợp đặc biệt. Nó kiểm tra các trường hợp không thể đi qua được ngay lập tức (hai hoặc ba bậc hỏng liên tiếp, hỏng bậc 1 hoặc n). Nó sử dụng dãy Fibonacci để tính số cách đi qua các đoạn không bị hỏng. Tuy nhiên, cách này phức tạp hơn và dễ sai sót so với DP trực tiếp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Quy hoạch động cơ bản (DP) |
| 2 | O(n) | O(n) (chỉ lưu mảng broken) | Quy hoạch động tối ưu (Không gian O(1)) |
| 3 | O(n) | O(n) | Xử lý đặc biệt cho các đoạn liên tiếp |
Bài học kinh nghiệm
- Bài toán có tính chất quỹ đạo (recurrence) tương tự dãy Fibonacci: Số cách đến bậc i phụ thuộc vào số cách đến bậc i-1 và i-2.
- Phải xử lý trường hợp các bậc thang bị hỏng bằng cách gán số cách bằng 0 tại các vị trí đó.
- Giới hạn n ≤ 100000 cho phép giải thuật O(n) chạy trong thời gian chấp nhận được.
Lỗi thường gặp
- Quên kiểm tra xem bậc 1 hoặc bậc n có bị hỏng không. Nếu có, số cách bằng 0.
- Quên xử lý modulo đúng cách khi cộng các số lớn.
- Sử dụng biến có kiểu dữ liệu quá nhỏ (ví dụ: int) có thể gây tràn số nếu không chia lấy dư liên tục (nếu MOD lớn).
Bình luận