Hướng dẫn giải của [200 đề thầy Đức] Bài 35: Trình duyệt web
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
Sau mỗi thao tác, các tab còn mở luôn là một đoạn liên tiếp [a, b] và con trỏ nằm trong đoạn đó. Đóng tab bên trái (tại vị trí i) làm a = i, đóng tab bên phải làm b = i. Cần đưa đoạn về đúng [L, R] với số giây ít nhất.
Sub 1: Tìm kiếm theo trạng thái (BFS) — ~O(N^3)~
Trạng thái là bộ ba (a, b, i). Từ (1, N, P) ta BFS với 4 thao tác: đi trái, đi phải, đóng bên trái (đến (i, b, i)), đóng bên phải (đến (a, i, i)), mỗi thao tác 1 giây. Khi đạt a = L và b = R thì in số giây. Cách này đúng vì không cần suy luận gì thêm. Đạt 229/229 test.
#include <bits/stdc++.h>
using namespace std;
// Trang thai (a, b, i): cac tab chua dong la [a, b], con tro dang o tab i (a <= i <= b)
// Tu trang thai dau (1, N, P), tim so giay it nhat den (L, R) bang BFS
static int dist[102][102][102];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, P, L, R;
cin >> N >> P >> L >> R;
memset(dist, -1, sizeof dist);
queue<array<int, 3>> q;
dist[1][N][P] = 0;
q.push({1, N, P});
while (!q.empty()) {
array<int, 3> s = q.front();
q.pop();
int a = s[0], b = s[1], i = s[2];
int d = dist[a][b][i];
if (a == L && b == R) {
cout << d << "\n";
return 0;
}
// Cac thao tac, moi thao tac ton 1 giay
// 1) Di chuyen con tro sang trai / phai (khong ra khoi [a, b])
if (i - 1 >= a && dist[a][b][i - 1] == -1) {
dist[a][b][i - 1] = d + 1;
q.push({a, b, i - 1});
}
if (i + 1 <= b && dist[a][b][i + 1] == -1) {
dist[a][b][i + 1] = d + 1;
q.push({a, b, i + 1});
}
// 2) Dong tat ca tab ben trai: [a, i-1] -> a moi = i
if (i > a && dist[i][b][i] == -1) {
dist[i][b][i] = d + 1;
q.push({i, b, i});
}
// 3) Dong tat ca tab ben phai: [i+1, b] -> b moi = i
if (i < b && dist[a][i][i] == -1) {
dist[a][i][i] = d + 1;
q.push({a, i, i});
}
}
return 0;
}
Sub 2: Công thức — ~O(1)~
Nếu L > 1 thì phải đến tab L và đóng bên trái. Nếu R < N thì phải đến tab R và đóng bên phải. Trường hợp chỉ cần một phía: đi đến vị trí đó rồi đóng, tốn |P - vị trí| + 1 giây. Trường hợp cần cả hai: phải đi qua L và R, nên chọn thứ tự tốt hơn là (R - L) + 2 + min(|P - L|, |P - R|). Nếu không cần đóng gì thì đáp án là 0. Đạt 229/229 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, P, L, R;
cin >> N >> P >> L >> R;
// Can dong tab ben trai neu L > 1 (phai di den tab L roi dong [1, L-1])
// Can dong tab ben phai neu R < N (phai di den tab R roi dong [R+1, N])
bool needL = (L > 1), needR = (R < N);
long long ans;
if (!needL && !needR) {
ans = 0;
} else if (!needR) {
ans = abs(P - L) + 1; // di den L roi dong ben trai
} else if (!needL) {
ans = abs(P - R) + 1; // di den R roi dong ben phai
} else {
// Phai di qua ca L va R: di den mot dau truoc, roi di sang dau kia
ans = (R - L) + 2 + min(abs(P - L), abs(P - R));
}
cout << ans << "\n";
return 0;
}
Bình luận