Hướng dẫn giải của [200 đề thầy Đức] Bài 184: Những con bò băng qua đường
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 quan sát gồm số hiệu con bò và bên đường (0 hoặc 1). Một lượt băng đường được tính khi hai lần quan sát liên tiếp của cùng một con bò nằm ở hai bên khác nhau. Cần đếm tổng số lượt băng đường của mọi con bò.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi quan sát i, lùi dần về phía trước để tìm lần quan sát gần nhất của cùng con bò. Nếu bên của lần đó khác bên ở i thì tăng số lượt lên 1. Đạt 9/19 test, 10 test còn lại quá giờ vì N lớn làm số lần lùi tìm kiếm rất lớn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> cow(n), side(n);
for (int i = 0; i < n; i++) cin >> cow[i] >> side[i];
// Vét cạn: với mỗi quan sát i, lùi về trước tìm lần quan sát gần nhất của cùng con bò.
// Nếu bên khác với lần đó thì con bò đã băng qua đường một lần.
long long cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (cow[j] == cow[i]) {
if (side[j] != side[i]) cnt++;
break;
}
}
}
cout << cnt << "\n";
return 0;
}
Sub 2: Nhớ bên lần trước của mỗi con bò — ~O(N)~
Số hiệu con bò nằm trong 1..100000 nên dùng mảng last kích thước 100001, last[c] là bên của con bò c ở lần quan sát trước (ban đầu là -1, nghĩa là chưa thấy). Với mỗi quan sát (c, s): nếu last[c] đã có giá trị và khác s thì tăng đáp án, rồi cập nhật last[c] = s. Mỗi quan sát chỉ xử lý O(1).
Bẫy cần chú ý: lần quan sát đầu tiên của một con bò không tính là băng đường. Đáp án có thể lên tới khoảng 10^5 nên dùng long long. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// last[c] = bên của con bò c ở lần quan sát trước đó (-1 nếu chưa thấy).
// Số hiệu con bò nằm trong 1..100000.
vector<int> last(100001, -1);
long long cnt = 0;
for (int i = 0; i < n; i++) {
int c, s;
cin >> c >> s;
// Nếu đã có quan sát trước và khác bên thì con bò vừa băng đường
if (last[c] != -1 && last[c] != s) cnt++;
last[c] = s;
}
cout << cnt << "\n";
return 0;
}
Bình luận