Hướng dẫn giải của [Beginner Free Contest 06] HARMONY
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
Cho T bộ test, mỗi bộ là dãy A có N phần tử. Dãy con liên tiếp dài nhất mà hai phần tử kề nhau luôn cách nhau đúng 1 đơn vị được gọi là đoạn "chỉ số hài hòa". Dãy A hài hòa khi đoạn này dài hơn 50% N. In Yes hoặc No cho từng bộ.
Sub 1: Vét cạn mọi điểm bắt đầu — ~O(n^2)~
Với mỗi vị trí L làm điểm bắt đầu, đi tiếp R cho đến khi gặp cặp kề nhau có chênh lệch khác 1, rồi ghi nhận độ dài R − L + 1 lớn nhất. Dãy hài hòa khi 2·(độ dài lớn nhất) > N. Đạt 10/10 test (N ≤ 1000).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Sub 1: voi moi L, di tiep R cho den khi cap (i-1, i) vi pham |A_{i-1}-A_i|=1
int best = 1;
for (int L = 0; L < n; L++) {
int R = L;
while (R + 1 < n && abs(a[R] - a[R + 1]) == 1) R++;
best = max(best, R - L + 1);
}
cout << (2 * best > n ? "Yes" : "No") << "\n";
}
return 0;
}
Sub 2: Duyệt một lần, đếm đoạn hiện tại — ~O(n)~
Duyệt từ trái sang phải và giữ độ dài đoạn hiện tại cur. Nếu |A{i-1} − Ai| = 1 thì cur tăng thêm 1; nếu không thì đặt lại cur = 1 vì đoạn mới bắt đầu từ phần tử i. Ghi lại cur lớn nhất. Cuối cùng so sánh 2·best với N. Đạt 10/10 test.
Bẫy cần chú ý: đoạn có độ dài 1 luôn hợp lệ nên best khởi tạo bằng 1, và phải so sánh bằng 2·best > N thay vì chia số thực để tránh sai số.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Duyet mot lan: cur la do dai doan hien tai co cac buoc |diff| = 1
int best = 1, cur = 1;
for (int i = 1; i < n; i++) {
if (abs(a[i - 1] - a[i]) == 1) cur++; // tiep tuc doan
else cur = 1; // bat dau doan moi
best = max(best, cur);
}
// Hai hoa khi chi so hai hoa > 50% do dai (2*best > n)
cout << (2 * best > n ? "Yes" : "No") << "\n";
}
return 0;
}
Bình luận