Hướng dẫn giải của [Beginner Free Contest 18] FINDPER
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
Mỗi bước thêm a_i vào cuối B rồi đảo ngược B. Đảo ngược chỉ đổi hướng nhìn dãy, nên có thể không cần đảo thật.
Sub 1: Mô phỏng - ~O(n^2)~, dùng khi ~n \le 5000~
Làm đúng như đề: mỗi bước thêm rồi đảo cả dãy. Nếu chỉ nộp sub này: đúng 4/12 test.
Sub 2: Deque và cờ đảo chiều - ~O(n)~
Giữ deque D và cờ rev. Khi rev = 0 thì thêm vào cuối D, khi rev = 1 thì thêm vào đầu D (vì B đang bị lật). Sau mỗi bước đổi cờ. Cuối cùng nếu rev = 1 thì đảo D rồi in. Đúng 12/12 test.
Chương trình hoàn chỉnh
main đọc N và dãy a. Nếu ~n \le 5000~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: mo phong truc tiep - moi buoc them a_i vao cuoi B roi dao nguoc B. Dung khi n <= 5000.
void sub1() {
vector<long long> B;
for (int i = 0; i < n; i++) {
B.push_back(a[i]);
reverse(B.begin(), B.end());
}
for (int i = 0; i < (int)B.size(); i++)
cout << B[i] << (i + 1 < (int)B.size() ? " " : "\n");
}
// Sub 2: dung deque + co huong. Dao nguoc B chi can doi huong (rev ^= 1),
// neu rev = 0 thi "cuoi B" la cuoi D, neu rev = 1 thi "cuoi B" la dau D.
void sub2() {
deque<long long> D;
int rev = 0;
for (int i = 0; i < n; i++) {
if (rev == 0) D.push_back(a[i]);
else D.push_front(a[i]);
rev ^= 1;
}
if (rev == 1) reverse(D.begin(), D.end()); // in B theo dung thu tu
for (int i = 0; i < (int)D.size(); i++)
cout << D[i] << (i + 1 < (int)D.size() ? " " : "\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (auto& x : a) cin >> x;
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận