Hướng dẫn giải của Câu 2 (đề Bình Dương 2021)
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
Dãy hạt là một mẫu lặp lại, nên cần tìm chu kỳ nhỏ nhất L của dãy: a[i] = a[i+L] với mọi i hợp lệ. Ví dụ 5 3 1 3 5 2 5 3 1 3 5 2 5 có chu kỳ 6.
Sub 1: Vét cạn thử từng L — ~O(N^3)~
Thử L = 1, 2, ..., N; với mỗi L kiểm tra toàn bộ dãy xem a[i] = a[i+L] có đúng hết không. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: thử từng độ dài mẫu L từ 1 đến N, kiểm tra toàn bộ dãy có lặp chu kỳ L không
for (int L = 1; L <= n; L++) {
bool ok = true;
for (int i = 0; i + L < n && ok; i++)
if (a[i] != a[i + L]) ok = false;
if (ok) {
cout << L << "\n";
return 0;
}
}
cout << n << "\n";
return 0;
}
Sub 2: Thử từng L nhưng dừng sớm — ~O(N^2)~
Vẫn thử từng L, nhưng dừng ngay khi gặp một cặp không khớp để giảm số phép so sánh. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Thử từng L, dừng ngay khi gặp vị trí không khớp để giảm số phép so sánh
for (int L = 1; L <= n; L++) {
int i = 0;
while (i + L < n && a[i] == a[i + L]) i++;
if (i + L >= n) {
cout << L << "\n";
return 0;
}
}
cout << n << "\n";
return 0;
}
Sub 3: Bảng KMP (tiền tố = hậu tố) — ~O(N)~
Chu kỳ nhỏ nhất là N - pi[N-1], với pi là bảng KMP: độ dài tiền tố dài nhất vừa là hậu tố. Trong ví dụ, pi[12] = 7 nên chu kỳ = 13 - 7 = 6. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Chu kỳ nhỏ nhất = n - (độ dài tiền tố dài nhất cũng là hậu tố), tính bằng bảng KMP pi
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && a[i] != a[j]) j = pi[j - 1];
if (a[i] == a[j]) j++;
pi[i] = j;
}
cout << n - pi[n - 1] << "\n";
return 0;
}
Bình luận