Hướng dẫn giải của [200 đề thầy Đức] Bài 187: Lớp học múa
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
Đổi $a$ thành $+1$ và $b$ thành $-1$. Một đoạn liên tiếp có số $a$ bằng số $b$ khi tổng các giá trị trên đoạn đó bằng $0$. Dùng tổng tiền tố $P$: đoạn $(i, j]$ thỏa khi $Pi = Pj$. Vậy đáp số là số cặp chỉ số có cùng giá trị tiền tố, kể cả $P_0 = 0$.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi điểm đầu $i$, duyệt $j$ và cộng dồn cân bằng, mỗi lần cân bằng bằng $0$ thì tăng đáp số.
Nếu chỉ nộp sub này: đúng 9/15 test (6 test lớn quá giờ).
Sub 2: Đếm theo giá trị tiền tố — ~O(n)~
Tiền tố nằm trong đoạn $[-n, n]$ nên dùng mảng đếm có độ lệch $n$. Với mỗi giá trị xuất hiện $c$ lần, có $\binom{c}{2}$ cặp. Bẫy: đáp số có thể lên tới khoảng $5 \cdot 10^{11}$ nên dùng long long.
Nếu chỉ nộp sub này: đúng 15/15 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu $n \le 5000$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
// Sub 1: vet can O(n^2), dung khi n <= 5000.
// Voi moi diem dau i, duyet j, dem so doan [i, j] co so 'a' bang so 'b'.
void sub1() {
long long ans = 0;
for (int i = 0; i < n; i++) {
int bal = 0;
for (int j = i; j < n; j++) {
bal += (s[j] == 'a') ? 1 : -1;
if (bal == 0) ans++;
}
}
cout << ans << "\n";
}
// Sub 2: O(n) dung tien to. Dat cong 'a' la +1, 'b' la -1. Doan [i+1, j] can bang
// khi P_i = P_j voi P la tong tien to. Dem so cap chi so co cung gia tri P (ke ca P_0 = 0).
void sub2() {
vector<long long> cnt(2 * n + 1, 0); // P nam trong [-n, n]
long long bal = 0;
cnt[n]++; // P_0 = 0
for (int i = 0; i < n; i++) {
bal += (s[i] == 'a') ? 1 : -1;
cnt[bal + n]++;
}
long long ans = 0;
for (long long c : cnt) ans += c * (c - 1) / 2;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
n = s.size();
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận