Hướng dẫn giải của [Beginner Free Contest 03] REVERSE
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.
Hướng dẫn giải
Yêu cầu: cho xâu ~s~ và ~m~ lần đảo các đoạn ~[a_i, n - a_i + 1]~; in xâu sau khi đảo.
Sub 1: Đảo trực tiếp — ~O(n \cdot m)~, dùng khi ~n \cdot m \le 10^7~
Với mỗi lần đảo, dùng hàm đảo đoạn của chuỗi.
Nếu chỉ nộp sub này: đúng 14/50 test.
Sub 2: Đếm theo lớp — ~O(n + m)~
Lần đảo với ~a_i~ đổi vị trí ~k~ và ~n+1-k~ với mọi ~k \ge a_i~. Lớp ~k~ bị hoán đổi khi số lần đảo có ~a_i \le k~ là số lẻ. Duyệt ~k~ tăng dần và hoán đổi khi cần.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Với ~n \cdot m \le 10^7~ gọi sub 1, còn lại gọi sub 2. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
vector<int> a; // a[i]: lần đảo thứ i đảo đoạn [a_i, n - a_i + 1] (đánh số từ 1)
// Sub 1: đảo trực tiếp từng lần O(n*m) — dùng khi n*m <= 10^7
void sub1() {
for (int x : a) reverse(s.begin() + (x - 1), s.begin() + (n - x + 1));
cout << s << "\n";
}
// Sub 2: đếm theo lớp O(n + m) — lời giải đầy đủ
// Lớp k gồm hai vị trí k và n+1-k. Một lần đảo với a_i <= k sẽ hoán đổi hai vị trí của lớp k.
// Lớp k được hoán đổi khi số lần đảo có a_i <= k là lẻ.
void sub2() {
vector<int> cnt(n / 2 + 2, 0);
for (int x : a) cnt[x]++;
long long c = 0;
for (int k = 1; k <= n / 2; k++) {
c += cnt[k];
if (c % 2 == 1) swap(s[k - 1], s[n - k]);
}
cout << s << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> m;
n = s.size();
a.resize(m);
for (auto &x : a) cin >> x;
if ((long long)n * m <= 10000000LL) sub1();
else sub2();
return 0;
}
Bình luận