Hướng dẫn giải của [Beginner Free Contest 13] COUNTSTR
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 cặp ~(l, r)~ với ~l < r~ sao cho ~S_l \ne S_r~ và cả ~S_l~ lẫn ~S_r~ không xuất hiện giữa ~l~ và ~r~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 3000~
Với mỗi ~l~, duyệt ~r~ tăng dần và giữ tập chữ cái nằm strictly giữa ~l~ và ~r~ bằng bitmask. Nếu chỉ nộp sub này: đúng 36/56 test.
Sub 2: Chữ cái xuất hiện cuối cùng — ~O(26 \cdot n)~
Với mỗi ~r~, ~l~ hợp lệ phải là vị trí xuất hiện cuối cùng của một chữ cái ~c \ne S_r~, và phải nằm sau lần xuất hiện trước đó của ~S_r~. Đếm các chữ cái thỏa điều kiện này. Nếu chỉ nộp sub này: đúng 56/56 test.
Chương trình hoàn chỉnh
~main~ đọc xâu, nếu ~|S| \le 3000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
// Sub 1: O(n^2) (n <= 3000). Voi moi l, duyet r tang dan, nho tap chu cai nam strictly giua l va r.
// Cap (l, r) hop le khi S[l] != S[r] va ca S[l], S[r] deu khong xuat hien giua l va r.
void sub1() {
long long ans = 0;
for (int l = 0; l < n; l++) {
unsigned mask = 0; // tap chu cai xuat hien strictly giua l va r
for (int r = l + 1; r < n; r++) {
int cl = s[l] - 'a', cr = s[r] - 'a';
if (cl != cr && !((mask >> cl) & 1) && !((mask >> cr) & 1)) ans++;
mask |= 1u << cr; // S[r] se nam giua l va cac r' > r
}
}
cout << ans << "\n";
}
// Sub 2: O(26 n). Voi moi r, l hop le la vi tri xuat hien cuoi cung cua moi chu cai c != S[r]
// (phai nam sau lan xuat hien truoc do gan nhat cua S[r], de S[r] khong nam giua).
void sub2() {
long long ans = 0;
int last[26];
for (int c = 0; c < 26; c++) last[c] = -1;
for (int r = 0; r < n; r++) {
int cr = s[r] - 'a';
int p = last[cr]; // vi tri gan nhat truoc r ma S[r] xuat hien
for (int c = 0; c < 26; c++)
if (c != cr && last[c] > p) ans++;
last[cr] = r;
}
cout << ans << "\n";
}
int main() {
cin >> s;
n = s.size();
if (n <= 3000) sub1();
else sub2();
return 0;
}
Bình luận