Hướng dẫn giải của [200 đề thầy Đức] Bài 185: Phần tử tốt
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
Phần tử tốt là phần tử mà khi bỏ nó đi, tổng các phần tử ở vị trí lẻ bằng tổng các phần tử ở vị trí chẵn của dãy còn lại. Chương trình đếm số phần tử tốt, khớp với ví dụ (đáp án 2). Lưu ý: phần đầu ra của đề ghi "tổng số lần bò băng qua đường", đây là lỗi chép đề, nên lời giải làm theo phần đề mô tả và ví dụ.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 3000~
Thử từng phần tử: bỏ nó, xây lại dãy còn lại, cộng tổng vị trí lẻ và tổng vị trí chẵn rồi so sánh. Nếu chỉ nộp sub này: đúng 11/21 test.
Sub 2: Tổng tiền tố theo tính chẵn lẻ — ~O(n)~
Khi bỏ phần tử ~i~, các phần tử sau ~i~ đổi tính chẵn lẻ. Do đó tổng lẻ mới bằng tổng lẻ trước ~i~ cộng tổng chẵn sau ~i~, và tổng chẵn mới bằng tổng chẵn trước ~i~ cộng tổng lẻ sau ~i~. Đếm các ~i~ thỏa hai tổng này bằng nhau. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~N~ và dãy. Nếu ~N \le 3000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005]; // dãy ban đầu (đánh số từ 1)
// Sub 1: vét cạn O(n^2). Thử bỏ từng phần tử, xây lại dãy còn lại rồi so tổng vị trí lẻ và chẵn.
void sub1() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
vector<long long> b;
for (int k = 1; k <= n; k++)
if (k != i) b.push_back(a[k]);
long long odd = 0, even = 0;
for (int k = 0; k < (int)b.size(); k++) {
if (k % 2 == 0) odd += b[k]; // vị trí lẻ (1-based)
else even += b[k]; // vị trí chẵn (1-based)
}
if (odd == even) cnt++;
}
printf("%d\n", cnt);
}
// Sub 2: O(n) bằng tổng tiền tố. Khi bỏ phần tử i, các phần tử sau i đổi tính chẵn lẻ.
// Tổng vị trí lẻ mới = (tổng lẻ trước i) + (tổng chẵn sau i); tổng chẵn mới = (tổng chẵn trước i) + (tổng lẻ sau i).
void sub2() {
vector<long long> preO(n + 2, 0), preE(n + 2, 0), sufO(n + 2, 0), sufE(n + 2, 0);
for (int k = 1; k <= n; k++) {
preO[k] = preO[k - 1] + (k % 2 == 1 ? a[k] : 0);
preE[k] = preE[k - 1] + (k % 2 == 0 ? a[k] : 0);
}
for (int k = n; k >= 1; k--) {
sufO[k] = sufO[k + 1] + (k % 2 == 1 ? a[k] : 0);
sufE[k] = sufE[k + 1] + (k % 2 == 0 ? a[k] : 0);
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
long long odd = preO[i - 1] + sufE[i + 1];
long long even = preE[i - 1] + sufO[i + 1];
if (odd == even) cnt++;
}
printf("%d\n", cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 3000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận