Hướng giải của Nhảy Đến Khi Vượt Ngưỡng
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải: Nhảy Đến Khi Vượt Ngưỡng
Phân tích bài toán
Yêu cầu tìm số bước nhảy tối đa liên tiếp từ \(U\) sao cho tổng trọng số các cung không vượt quá \(S\).
Ta định nghĩa sum_val[i][j] là tổng trọng số các cung khi đi đúng \(2^j\) bước từ đỉnh \(i\):
- Cơ sở:
sum_val[i][0] = W_i. - Quy hoạch động:
sum_val[i][j] = sum_val[i][j-1] + sum_val[up[i][j-1]][j-1]. Khi xử lý truy vấn: - Duyệt các bước nhảy nhị phân lớn từ \(j = LOG - 1\) về \(0\).
- Nếu tổng chi phí đi \(2^j\) bước từ đỉnh hiện tại
sum_val[u][j] <= s, ta tiến hành nhảy (cộng \(2^j\) vào kết quả, giảm \(S\) đi một lượng tương ứng và chuyển sang đỉnh mới). - Ngược lại, ta giữ nguyên vị trí và thử các bit nhỏ hơn.
Độ phức tạp
- Thời gian: \(O(N \log S_{max})\) tiền xử lý và \(O(\log S)\) mỗi truy vấn.
- Không gian: \(O(N \log S_{max})\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
int LOG = 60;
vector<vector<int>> up(n, vector<int>(LOG));
vector<vector<long long>> sum_val(n, vector<long long>(LOG));
for (int i = 0; i < n; i++) cin >> up[i][0];
for (int i = 0; i < n; i++) cin >> sum_val[i][0];
for (int j = 1; j < LOG; j++) {
for (int i = 0; i < n; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
sum_val[i][j] = sum_val[i][j - 1] + sum_val[up[i][j - 1]][j - 1];
}
}
while (q--) {
int u;
long long s;
cin >> u >> s;
long long steps = 0;
for (int j = LOG - 1; j >= 0; j--) {
if (sum_val[u][j] <= s) {
s -= sum_val[u][j];
steps += (1LL << j);
u = up[u][j];
}
}
cout << steps << "\n";
}
return 0;
}
Nhận xét