Hướng dẫn giải của [VT Thiếu nhi] BÀI 25: TREE
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ỗi con đường là một xâu ký tự. Đoạn đường xanh đẹp là một đoạn liên tiếp các ký tự giống nhau. Cần tìm độ dài lớn nhất của đoạn như vậy trong mọi con đường.
Sub 1: Vét cạn theo vị trí bắt đầu — ~O(N·L^2)~
Với mỗi con đường và mỗi vị trí i, đếm số ký tự liên tiếp bằng s[i] bắt đầu từ i, lấy max. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TREE.INP", "r")) { freopen("TREE.INP", "r", stdin); freopen("TREE.OUT", "w", stdout); }
int n;
cin >> n;
int best = 0;
for (int k = 0; k < n; k++) {
string s;
cin >> s;
// Vét cạn: với mỗi vị trí bắt đầu i, đếm số ký tự liên tiếp giống s[i]
for (size_t i = 0; i < s.size(); i++) {
int len = 0;
while (i + len < s.size() && s[i + len] == s[i]) len++;
best = max(best, len);
}
}
cout << best << "\n";
return 0;
}
Sub 2: Quét một lượt — ~O(N·L)~
Duyệt xâu một lần: nếu s[i] giống s[i-1] thì độ dài đoạn hiện tại tăng 1, còn không thì đặt lại bằng 1. Cập nhật kết quả max mỗi bước. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TREE.INP", "r")) { freopen("TREE.INP", "r", stdin); freopen("TREE.OUT", "w", stdout); }
int n;
cin >> n;
int best = 0;
for (int k = 0; k < n; k++) {
string s;
cin >> s;
// Quét một lượt: đếm độ dài đoạn hiện tại các ký tự giống nhau
int cur = 0;
for (size_t i = 0; i < s.size(); i++) {
if (i > 0 && s[i] == s[i - 1]) cur++;
else cur = 1;
best = max(best, cur);
}
}
cout << best << "\n";
return 0;
}
Bình luận