Hướng dẫn giải của Bedao Regular Contest 07 - TRAIN
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Tác giả:
Đoàn tàu sẽ đến tọa độ ~x~ ở các thời điểm ~2k \times L + x~ và ~(2k + 1) \times L - x~ với mọi số nguyên ~k \ge 0~.
Như vậy, giả sử thời điểm hiện tại là ~t~, ta cần tìm thời điểm gần nhất mà đoàn tàu đến được điểm ~x~. Thời điểm đó có thể được tìm thấy bằng cách sử dụng tìm kiếm nhị phân trên số ~k~ hoặc sử dụng công thức trực tiếp.
Code mẫu
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, l; cin >> n >> l; vector<int> x(n), t(n); for (int &a : x) { cin >> a; } for (int &a : t) { cin >> a; } x.push_back(0); t.push_back(0); long long res = 0; for (int i = 0; i <= n; ++i) { for (int j = 0; j < 2; ++j) { long long cyc = res / (2 * l); while (true) { if (res <= cyc * 2 * l + x[i]) { res = cyc * 2 * l + x[i]; break; } if (res <= cyc * 2 * l + 2 * l - x[i]) { res = cyc * 2 * l + 2 * l - x[i]; break; } ++cyc; } if (j < 1) { res += t[i]; } } } cout << res << '\n'; return 0; }
Bình luận
mình nghĩ các thời điểm xe tới tọa đọ x là (2kl+x)và(2k+2)*l-x với mọi k nguyên không âm
Ai có code rồi cho em tham khảo với ạ, em vẫn khó hình dung ra ý tưởng.
đây là code của mình bạn có thể tham khảo 😉
https://ideone.com/D7bl5g
Uầy! Cảm ơn bạn nhiều. <3