Hướng dẫn giải của [200 đề thầy Đức] Bài 182: Chụp ảnh
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ượt, người có số áo ~i~ chạy ra rồi đứng bên trái người có số áo ~j~. Điều này tương đương với việc xóa ~i~ khỏi dãy rồi chèn ~i~ ngay trước ~j~. Sau ~m~ lượt, in số áo của người đứng bên trái và bên phải của từng người (0 nếu không có).
Sub 1: Mô phỏng trên mảng — ~O(n \cdot m)~, dùng khi ~n \cdot m \le 4 \cdot 10^6~
Mỗi lượt tìm và xóa ~i~ khỏi dãy, rồi tìm ~j~ và chèn ~i~ ngay trước nó. Sau cùng đọc hàng xóm trái, phải của từng người. Nếu chỉ nộp sub này: đúng 13/19 test.
Sub 2: Danh sách liên kết — ~O(n + m)~
Dùng danh sách liên kết hai chiều, nút ~0~ làm lính canh ở hai đầu hàng. Xóa ~i~: nối ~L_i~ với ~R_i~. Chèn ~i~ trước ~j~: sửa bốn con trỏ. Mỗi lượt chỉ tốn ~O(1)~. Nếu chỉ nộp sub này: đúng 19/19 test.
Chương trình hoàn chỉnh
main đọc ~n~, ~m~ và các cặp ~(i, j)~. Nếu ~n \cdot m \le 4 \cdot 10^6~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int opI[100005], opJ[100005]; // thao tác thứ k: người số opI[k] chạy ra và quay về đứng bên trái người opJ[k]
// Sub 1: vét cạn O(n*m). Mỗi thao tác: xóa i khỏi dãy rồi chèn vào ngay trước j.
void sub1() {
vector<int> seq;
for (int i = 1; i <= n; i++) seq.push_back(i);
for (int k = 0; k < m; k++) {
int i = opI[k], j = opJ[k];
seq.erase(find(seq.begin(), seq.end(), i));
auto it = find(seq.begin(), seq.end(), j);
seq.insert(it, i);
}
vector<int> ansL(n + 1, 0), ansR(n + 1, 0);
for (int p = 0; p < n; p++) {
int v = seq[p];
ansL[v] = p > 0 ? seq[p - 1] : 0;
ansR[v] = p < n - 1 ? seq[p + 1] : 0;
}
for (int i = 1; i <= n; i++) printf("%d %d\n", ansL[i], ansR[i]);
}
// Sub 2: danh sách liên kết O(n + m). Nút 0 là lính canh (đầu/cuối hàng).
// L[x], R[x] là người đứng bên trái, bên phải của x. Dãy ban đầu 0 - 1 - 2 - ... - n - 0.
int L[100005], R[100005];
void sub2() {
L[0] = n;
R[0] = 1;
for (int i = 1; i <= n; i++) {
L[i] = i - 1;
R[i] = i + 1;
}
R[n] = 0;
for (int k = 0; k < m; k++) {
int i = opI[k], j = opJ[k];
// xóa i khỏi dãy
R[L[i]] = R[i];
L[R[i]] = L[i];
// chèn i ngay trước j
int p = L[j];
R[p] = i;
L[i] = p;
R[i] = j;
L[j] = i;
}
for (int i = 1; i <= n; i++) printf("%d %d\n", L[i], R[i]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int k = 0; k < m; k++) cin >> opI[k] >> opJ[k];
if (1LL * n * m <= 4000000LL) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận