Hướng dẫn giải của [VTT Q4 Contest 06] Bài 2: Xây dựng dãy số [SEQUENCE]
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 lệnh chèn giá trị ~y~ vào vị trí ~x~ của dãy hiện tại; chỉ cần mô phỏng lần lượt ~n~ lệnh.
Sub 1: Mô phỏng bằng vector — ~O(n^2)~, ~n \le 1000~
Dùng vector, lệnh thứ ~i~ gọi insert tại vị trí ~x-1~ (đánh số từ 0). Mỗi lần chèn tốn ~O(n)~, tổng ~O(n^2)~ rất nhỏ với ~n \le 1000~. Bài chỉ có một sub vì giới hạn nhỏ, mô phỏng thẳng đã là lời giải đầy đủ. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc ~n~ lệnh rồi gọi sub1.
#include <bits/stdc++.h>
using namespace std;
int n, X[1005];
long long Y[1005];
// Bài đơn giản (n ≤ 1000, chỉ cần mô phỏng trực tiếp) nên chỉ có 1 sub:
// dùng vector, mỗi lệnh chèn y vào vị trí x. ~O(n^2)~
void sub1() {
vector<long long> v;
for (int i = 1; i <= n; i++) v.insert(v.begin() + (X[i] - 1), Y[i]);
for (size_t i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << "\n";
}
int main() {
freopen("SEQUENCE.INP", "r", stdin);
freopen("SEQUENCE.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> X[i] >> Y[i];
sub1();
}
Bình luận