Hướng dẫn giải của SETMAP05: Thành phố và tiểu bang
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 thành phố có hai thông tin: tên (hai chữ cái đầu là mã tiểu bang của thành phố khác) và mã tiểu bang của chính nó. Cặp (X, Y) đặc biệt khi hai chữ cái đầu của X là tiểu bang của Y, hai chữ cái đầu của Y là tiểu bang của X, và hai tiểu bang khác nhau.
Sub 1: Vét cạn mọi cặp — ~O(n^2)~
Thử mọi cặp thành phố (i, j) rồi kiểm tra điều kiện. Đạt 4/10 test, 6 test còn lại quá giờ vì N lên tới 2·10^5.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> prefix(n), state(n);
for (int i = 0; i < n; i++) {
string city;
cin >> city >> state[i];
prefix[i] = city.substr(0, 2); // hai chữ cái đầu là mã tiểu bang của thành phố khác
}
// Vét cạn: thử mọi cặp (i, j), kiểm tra hai điều kiện đối xứng và khác tiểu bang
long long cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (prefix[i] == state[j] && prefix[j] == state[i] && state[i] != state[j])
cnt++;
cout << cnt << "\n";
return 0;
}
Sub 2: Dùng bảng đếm — ~O(n \log n)~
Đếm số thành phố ứng với từng cặp (hai chữ đầu, tiểu bang) bằng map. Với mỗi thành phố i, tra số thành phố j có (hai chữ đầu, tiểu bang) = (tiểu bang i, hai chữ đầu i). Bỏ qua các thành phố có hai chữ đầu trùng tiểu bang vì không có cặp nào khác tiểu bang. Mỗi cặp được đếm hai lần nên chia 2 ở cuối. Đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> prefix(n), state(n);
// Đếm số thành phố ứng với mỗi cặp (hai chữ đầu, mã tiểu bang)
map<pair<string, string>, long long> cnt;
for (int i = 0; i < n; i++) {
string city;
cin >> city >> state[i];
prefix[i] = city.substr(0, 2);
cnt[{prefix[i], state[i]}]++;
}
// Với thành phố i, cần thành phố j có (hai chữ đầu j, tiểu bang j) = (state[i], prefix[i])
// Nếu prefix[i] == state[i] thì không có cặp nào khác tiểu bang, bỏ qua
long long total = 0;
for (int i = 0; i < n; i++) {
if (prefix[i] == state[i]) continue;
auto it = cnt.find({state[i], prefix[i]});
if (it != cnt.end()) total += it->second;
}
// Mỗi cặp được đếm 2 lần (từ i và từ j) nên chia 2
cout << total / 2 << "\n";
return 0;
}
Bình luận