Hướng dẫn giải của Quân xe (đề Cần Thơ 2021)
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
Phép xoay 90 độ theo chiều kim đồng hồ đưa ô (x, y) thành ô (y, n+1-x).
Sub 1: Vét cạn, ~O(n^2)~ (n ≤ 10^3)
Với mỗi hàng r, duyệt mọi quân xe tìm quân có hàng mới bằng r. Đúng 15/20 test.
Sub 2: Mảng chỉ số, ~O(n)~
Gán ans[y] = n+1-x rồi in theo hàng. Đúng 20/20 test.
Chương trình hoàn chỉnh
main: n ≤ 1000 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: 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;
vector<int> X, Y; // vi tri (hang, cot) cua tung quan xe truoc khi xoay
// Sub 1: vet can. Voi moi hang r (tu 1 den n), duyet tat ca quan xe de tim quan nam o hang r sau khi xoay.
// Phep xoay 90 do theo chieu kim dong ho: o (x, y) chuyen thanh o (y, n + 1 - x).
void sub1() {
for (int r = 1; r <= n; r++)
for (int k = 0; k < n; k++) {
int nr = Y[k];
int nc = n + 1 - X[k];
if (nr == r) {
cout << r << " " << nc << "\n";
break;
}
}
}
// Sub 2: dung mang chi so. Quan xe moi o hang nr se ghi thang vao ans[nr].
void sub2() {
vector<int> ans(n + 1, 0);
for (int k = 0; k < n; k++) ans[Y[k]] = n + 1 - X[k];
for (int r = 1; r <= n; r++) cout << r << " " << ans[r] << "\n";
}
int main() {
freopen("quanxe.inp", "r", stdin);
freopen("quanxe.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
X.resize(n);
Y.resize(n);
for (int k = 0; k < n; k++) cin >> X[k] >> Y[k];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận