Hướng dẫn giải của [200 đề thầy Đức] Bài 147: Tổng chẵn
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
Cần đếm số dãy con liên tiếp có tổng chẵn. Với mỗi dãy con, tổng chẵn khi và chỉ khi tiền tố tại hai đầu có cùng tính chẵn/lẻ.
Sub 1: Vét cạn mọi dãy con — ~O(T \cdot N^2)~
Với mỗi điểm bắt đầu ~l~, cộng dồn ~r~ từ ~l~ đến hết dãy, mỗi lần tổng chẵn thì tăng đáp án. Đạt 21/21 test (N tối đa 1000, T tối đa 200).
#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 (int &x : a) cin >> x;
// Vét cạn: thử mọi dãy con a[l..r], tính tổng rồi kiểm tra chẵn
long long ans = 0;
for (int l = 0; l < n; l++) {
long long sum = 0;
for (int r = l; r < n; r++) {
sum += a[r];
if (sum % 2 == 0) ans++;
}
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Đếm tiền tố chẵn/lẻ — ~O(T \cdot N)~
Gọi ~S_i~ là tổng ~i~ phần tử đầu, dãy con ~[l..r] chẵn khi ~Sr~ và ~S{l-1}~ cùng tính chẵn lẻ. Đếm số tiền tố chẵn và lẻ đã gặp, mỗi phần tử mới cộng thêm số tiền tố cùng tính chất. Tiền tố ~S_0 = 0~ là chẵn. Đạt 21/21 test.
#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;
// Tổng đoạn [l..r] chẵn khi tiền tố S[r] và S[l-1] cùng tính chẵn/lẻ.
// Đếm số tiền tố chẵn và lẻ, mỗi cặp cùng tính chất là một dãy con chẵn.
long long cnt[2] = {1, 0}; // S[0] = 0 là chẵn
long long ans = 0;
int prefix = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
prefix = (prefix + x) % 2;
ans += cnt[prefix]; // các tiền tố trước đó cùng tính chẵn/lẻ với S[i+1]
cnt[prefix]++;
}
cout << ans << "\n";
}
return 0;
}
Bình luận