Hướng dẫn giải của Qua sông (đề Quảng Trị 2020-2021)
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.
Hướng dẫn giải
Đếm số đường đi từ hòn đá 1 đến hòn đá ~N~, mỗi bước nhảy có độ dài thuộc hợp của ~K~ đoạn rời nhau. Gọi ~dp[x]~ là số cách đến hòn đá ~x~, ~dp[1] = 1~, ~dp[x] = \sum dp[x-d]~ với mọi ~d~ hợp lệ, ~d < x~. Kết quả lấy dư ~10^9+7~.
Sub 1: Quy hoạch động vét cạn — ~O(N^2 \cdot K)~, dùng khi ~N \le 5000~
Với mỗi ~x~, thử mọi độ dài bước ~d~ từ 1 đến ~x-1~, kiểm tra ~d~ có thuộc đoạn nào không rồi cộng ~dp[x-d]~. Nếu chỉ nộp sub này: đúng 14/20 test (6 test lớn bị quá thời gian).
Sub 2: Tổng tiền tố — ~O(N \cdot K)~
Với mỗi đoạn ~[L_i, R_i]~, các ~d~ trong đoạn ứng với ~dp[x-R_i .. x-L_i]~ là một đoạn liên tiếp, nên tổng lấy bằng mảng tổng tiền tố ~pre~ trong ~O(1)~. Chú ý cắt đoạn cho không vượt dưới 1 và xử lý số âm khi lấy dư. Nộp riêng sub này đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu, nếu ~N \le 5000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, k;
int L[15], R[15];
long long dp[200005], pre[200005];
// Sub 1: quy hoạch động O(N^2) — duyệt mọi bước nhảy d từ 1 đến x-1, kiểm tra d có thuộc đoạn nào không
void sub1() {
dp[1] = 1;
for (int x = 2; x <= n; x++) {
long long s = 0;
for (int d = 1; d < x; d++) {
bool ok = false;
for (int i = 1; i <= k; i++) if (L[i] <= d && d <= R[i]) ok = true;
if (ok) s += dp[x - d];
}
dp[x] = s % MOD;
}
cout << dp[n] % MOD << "\n";
}
// Sub 2: dp với tổng tiền tố, mỗi đoạn [L,R] cộng dp[x-R..x-L] trong O(1): O(N*K)
void sub2() {
dp[1] = 1; pre[1] = 1;
for (int x = 2; x <= n; x++) {
long long s = 0;
for (int i = 1; i <= k; i++) {
int hi = x - L[i], lo = x - R[i];
if (hi < 1) continue;
if (lo < 1) lo = 1;
s += pre[hi] - pre[lo - 1] + MOD;
}
dp[x] = s % MOD;
pre[x] = (pre[x - 1] + dp[x]) % MOD;
}
cout << dp[n] % MOD << "\n";
}
int main() {
freopen("QUASONG.INP", "r", stdin);
freopen("QUASONG.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= k; i++) cin >> L[i] >> R[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận