Hướng dẫn giải của Nguyên tố
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 số đoạn con của xâu (tính theo vị trí) mà mọi chữ cái xuất hiện trong đoạn đó đều có số lần là số nguyên tố.
Lưu ý quy ước: hai đoạn ở vị trí khác nhau nhưng giống nhau về nội dung vẫn được đếm riêng (VD aaa có các đoạn aa, aa, aaa). Ví dụ aaa trong đề ghi đáp án 2 (đếm xâu phân biệt) nhưng bộ test chấm đều khớp cách đếm theo vị trí (chẳng hạn test 2 cho 167; đếm xâu phân biệt chỉ được 124), nên bài này đếm theo vị trí.
Sub 1: Vét cạn — ~O(N^3)~, dùng khi ~N \le 100~
Với mỗi đoạn ~[i..j]~, đếm lại số lần từng chữ rồi kiểm tra tất cả các số đếm khác 0 đều là số nguyên tố.
Nếu chỉ nộp sub này: đúng 12/12 test.
Sub 2: Duyệt mở rộng — ~O(N^2)~, dùng khi ~N \le 2000~
Với mỗi điểm bắt đầu i, mở rộng j và giữ bộ đếm ~bad~ = số chữ có số lần khác 0 mà không nguyên tố. Mỗi bước cập nhật ~bad~ trong O(1); đoạn hợp lệ khi ~bad = 0~.
Nếu chỉ nộp sub này: đúng 12/12 test.
Chương trình hoàn chỉnh
Chương trình đọc xâu S. Nếu ~|S| \le 100~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
bool isp[2005];
// Dem so doan [i..j] (tinh theo vi tri) ma moi chu xuat hien trong doan co so lan la so nguyen to.
// Du lieu cham (test) cho thay dem theo vi tri, khong loai xau con trung.
// Sub 1: voi moi doan, dem lai so lan tung chu roi kiem tra. O(n^3). Dung khi n <= 100
long long sub1() {
long long ans = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
int cnt[26] = {0};
for (int k = i; k <= j; k++) cnt[s[k] - 'a']++;
bool ok = true;
for (int c = 0; c < 26; c++)
if (cnt[c] > 0 && !isp[cnt[c]]) { ok = false; break; }
if (ok) ans++;
}
return ans;
}
// Sub 2: voi moi diem bat dau i, mo rong j va cap nhat bo dem "bad" (so chu co so lan khong nguyen to).
// Moi lan mo rong chi can O(1). O(n^2). Dung cho n <= 2000
long long sub2() {
long long ans = 0;
for (int i = 0; i < n; i++) {
int cnt[26] = {0};
int bad = 0;
for (int j = i; j < n; j++) {
int c = s[j] - 'a';
if (cnt[c] > 0 && !isp[cnt[c]]) bad--;
cnt[c]++;
if (!isp[cnt[c]]) bad++;
if (bad == 0) ans++;
}
}
return ans;
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i < 2005; i++) isp[i] = false;
for (int i = 2; i < 2005; i++) {
isp[i] = true;
for (int d = 2; d * d <= i; d++)
if (i % d == 0) { isp[i] = false; break; }
}
cin >> s;
n = s.size();
if (n <= 100) cout << sub1() << "\n";
else cout << sub2() << "\n";
return 0;
}
Bình luận