Hướng dẫn giải của Bedao Mini Contest 24 - Reverse Cow
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ả:
,Subtask 1:
- Duyệt trâu. Tổng độ phức tạp ~O(n * k * d)~.
Subtask 2:
Gọi ~nxt[i]~ là vị trí tiếp theo của con bò đang ở vị trí ~i~ sau một ngày.
Ở mỗi ngày, ta sẽ xác định vị trí tiếp theo của ~n~ con bò.
Do đó, tổng độ phức tạp là ~O(n * k + n * log(d))~.
Subtask 3:
Gọi ~nxt[i][w]~ là vị trí tiếp theo của con bò đang ở vị trí ~i~ sau ~2^w~ ngày.
Sử dụng sparse table để xây dựng mảng ~nxt~.
Để tìm vị trí của ~n~ con bò sau ~d~ ngày, ta có thể sử dụng kĩ thuật binary lifting
Do đó, tổng độ phức tạp là ~O(n * k+ n * log(d))~.
#include <bits/stdc++.h> // QioCas using namespace std; using ll = long long; const int N = 200200; int n, k, d, a[N]; int rmq[N][31]; int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> k >> d; iota(a + 1, a + n + 1, 1); for(int t = 1; t <= k; ++t) { int l, r; cin >> l >> r; for(int i = l; i <= r && i <= r - i + l; ++i) swap(a[i], a[r - i + l]); } for(int i = 1; i <= n; ++i) rmq[i][0] = a[i]; for(int s = 1; s <= 30; ++s) for(int i = 1; i <= n; ++i) rmq[i][s] = rmq[rmq[i][s - 1]][s - 1]; iota(a + 1, a + n + 1, 1); for(int s = 30; s >= 0; --s) if(d >> s & 1) { for(int i = 1; i <= n; ++i) a[i] = rmq[a[i]][s]; } for(int i = 1; i <= n; ++i) cout << a[i] << " "; return 0; }
Bình luận
Chắc lời giải ghi nhầm á,độ phức tạp của sub2 phải là O(nk + nd)
Mình thử tính đpt sub 2 thì mình thấy nó đủ để AC full bài mà ạ@@?