Hướng dẫn giải của Giải mật thư (Đề Quảng Trị 2021)
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
Bảng ~M \times N~ chứa các số nguyên dương. Cần sắp xếp toàn bộ các số theo thứ tự tăng dần rồi điền lại vào bảng theo đường xoắn ốc chiều kim đồng hồ, bắt đầu từ góc trên bên trái: đi sang phải ở hàng trên, xuống ở cột phải, sang trái ở hàng dưới, lên ở cột trái, rồi thu hẹp vùng và lặp lại.
Sub 1: Sắp xếp chọn — ~O((M \cdot N)^2)~, dùng khi ~M \cdot N \le 100~
Gom mọi số vào một dãy rồi sắp xếp bằng cách chọn số nhỏ nhất đặt lên đầu, lặp lại. Cách này đơn giản nhưng chậm khi bảng lớn. Nếu chỉ nộp sub này: đúng 11/12 test (1 test lớn bị quá giờ).
Sub 2: Sắp xếp nhanh của thư viện — ~O(M \cdot N \log(M \cdot N))~
Dùng sort của thư viện trên dãy các giá trị, rồi điền theo đường xoắn ốc.
Bẫy cần chú ý: khi điền xoắn ốc phải kiểm tra lại điều kiện còn hàng/cột để tránh ghi trùng ở bảng hẹp (một hàng hoặc một cột).
Nếu chỉ nộp sub này: đúng 12/12 test.
Chương trình hoàn chỉnh
main đọc bảng từ file. Nếu ~M \cdot N \le 100~ gọi sub1, còn lại gọi sub2. Phần điền xoắn ốc dùng bốn biên top, bottom, left, right và thu hẹp sau mỗi cạnh. Đầu main có freopen vì máy chấm đọc/ghi file CAU2.INP, CAU2.OUT.
#include <bits/stdc++.h>
using namespace std;
int M, N;
int grid[1005][1005]; // bang so
int ans[1005][1005]; // bang ket qua sau khi xep
vector<int> vals; // tat ca cac gia tri, se duoc sap xep
// Sub 1: vet can - sap xep bang selection sort O((MN)^2), dung khi M*N <= 100
void sub1() {
int K = vals.size();
for (int i = 0; i < K; i++) {
int best = i;
for (int j = i + 1; j < K; j++)
if (vals[j] < vals[best]) best = j;
swap(vals[i], vals[best]);
}
}
// Sub 2: sap xep bang std::sort O(MN log MN)
void sub2() {
sort(vals.begin(), vals.end());
}
int main() {
freopen("CAU2.INP", "r", stdin); // may cham doc/ghi file
freopen("CAU2.OUT", "w", stdout);
cin >> M >> N;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) {
cin >> grid[i][j];
vals.push_back(grid[i][j]);
}
if (M * N <= 100) sub1(); // bang nho
else sub2(); // bang lon
// Dien cac gia tri da sap xep theo duong xoan oc chieu kim dong ho, bat dau o goc tren trai
int top = 0, bottom = M - 1, left = 0, right = N - 1, k = 0;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) ans[top][j] = vals[k++]; // di sang phai o hang tren
top++;
for (int i = top; i <= bottom; i++) ans[i][right] = vals[k++]; // di xuong o cot phai
right--;
if (top <= bottom)
for (int j = right; j >= left; j--) ans[bottom][j] = vals[k++]; // di sang trai o hang duoi
bottom--;
if (left <= right)
for (int i = bottom; i >= top; i--) ans[i][left] = vals[k++]; // di len o cot trai
left++;
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++)
cout << ans[i][j] << (j + 1 < N ? " " : "\n");
}
return 0;
}
Bình luận