Hướng dẫn giải của Phân hạng ngọc trai (đề Quảng Trị 2020-2021)
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
Hạng của chuỗi là số $K$ nhỏ nhất sao cho mọi đoạn con dài $K$ đều khác nhau. Nếu mọi đoạn dài $K$ khác nhau thì mọi đoạn dài $K + 1$ cũng khác nhau (hai đoạn dài $K+1$ giống nhau thì phần đầu dài $K$ của chúng cũng giống nhau). Vì vậy có thể tìm $K$ bằng nhị phân.
Sub 1: Vét cạn — ~O(n^3 \log n)~, dùng khi ~n \le 100~
Với $K = 1, 2, \dots$: lấy mọi đoạn con dài $K$ đưa vào tập hợp, nếu số phần tử của tập bằng $n - K + 1$ thì không có đoạn nào trùng và in $K$.
Nếu chỉ nộp sub này: đúng 16/20 test (4 test lớn quá giờ).
Sub 2: Nhị phân kết hợp băm — ~O(n \log^2 n)~
Băm mọi đoạn con dài $K$ bằng băm đa thức hai modulo (ghép thành một số 64 bit), sắp xếp và kiểm tra hai giá trị liền kề có bằng nhau không. Nhị phân trên $K$ trong đoạn $[1, n]$; $K = n$ luôn thỏa vì chỉ có một đoạn.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file PHNT.INP, ghi ra PHNT.OUT. Nếu $n \le 100$ 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, dung khi n <= 100.
// Voi K = 1, 2, ...: lay moi doan con dai K, dua vao tap. Neu khong trung thi K la hang.
void sub1() {
for (int K = 1; K <= n; K++) {
set<string> st;
for (int i = 0; i + K <= n; i++) st.insert(s.substr(i, K));
if ((int)st.size() == n - K + 1) { // khong co hai doan giong nhau
cout << K << "\n";
return;
}
}
}
// Sub 2: tim nhi phan tren K + bam bam (hash) cho moi n.
// Nhan xet: neu moi doan do dai K deu khac nhau thi moi doan do dai K+1 cung khac nhau,
// nen tim K nho nhat bang nhi phan.
const long long M1 = 1000000007LL, M2 = 998244353LL, B1 = 131, B2 = 137;
vector<long long> h1, h2, p1, p2;
// Hash cua doan [i, i+K) bang cach ghep hai hash mod M1 va M2 thanh mot so 64 bit
unsigned long long subHash(int i, int K) {
long long x1 = (h1[i + K] - h1[i] * p1[K] % M1 + M1) % M1;
long long x2 = (h2[i + K] - h2[i] * p2[K] % M2 + M2) % M2;
return (unsigned long long)x1 * (unsigned long long)M2 + (unsigned long long)x2;
}
bool allDistinct(int K) {
vector<unsigned long long> v;
v.reserve(n - K + 1);
for (int i = 0; i + K <= n; i++) v.push_back(subHash(i, K));
sort(v.begin(), v.end());
for (size_t i = 1; i < v.size(); i++)
if (v[i] == v[i - 1]) return false;
return true;
}
void sub2() {
h1.assign(n + 1, 0); h2.assign(n + 1, 0);
p1.assign(n + 1, 1); p2.assign(n + 1, 1);
for (int k = 0; k < n; k++) {
h1[k + 1] = (h1[k] * B1 + s[k]) % M1;
h2[k + 1] = (h2[k] * B2 + s[k]) % M2;
p1[k + 1] = p1[k] * B1 % M1;
p2[k + 1] = p2[k] * B2 % M2;
}
int lo = 1, hi = n; // K = n luon phan biet (chi co 1 doan)
while (lo < hi) {
int mid = (lo + hi) / 2;
if (allDistinct(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("PHNT.INP", "r", stdin);
freopen("PHNT.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
n = s.size();
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận