Hướng dẫn giải của [200 đề thầy Đức] Bài 40: Alibaba lấy vàng
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 chọn một tập con các túi có tổng chẵn và lớn nhất. Nếu tổng tất cả các túi đã chẵn thì lấy hết. Nếu tổng lẻ thì phải bỏ đi ít nhất một túi lẻ, và bỏ đúng một túi lẻ nhỏ nhất là tốt nhất.
Sub 1: Vét cạn một túi cần bỏ — ~O(N^2)~
Thử không bỏ túi nào, và thử bỏ từng túi i một rồi tính tổng còn lại (tính lại từ đầu bằng vòng lặp). Lấy tổng chẵn lớn nhất. Cách này chậm với N lớn nên bị TLE ở một số test, nhưng kết quả đúng. Đạt 11/22 test, TLE 11 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> A(n);
long long S = 0;
for (int i = 0; i < n; i++) {
cin >> A[i];
S += A[i];
}
// Vet can: thu khong bo tui nao, hoac bo tung tui i, roi tinh tong con lai
// Chon tong chan lon nhat trong cac phuong an
long long best = 0; // lay khong tui nao thi tong la 0
if (S % 2 == 0) best = S;
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = 0; j < n; j++)
if (j != i) sum += A[j];
if (sum % 2 == 0) best = max(best, sum);
}
cout << best << "\n";
return 0;
}
Sub 2: Tổng và túi lẻ nhỏ nhất — ~O(N)~
Tính tổng S và túi lẻ nhỏ nhất. Nếu S chẵn thì in S; nếu S lẻ thì in S - (túi lẻ nhỏ nhất). Bẫy: tổng có thể lên tới 10^5 · 10^9 nên phải dùng số nguyên 64 bit. Đạt 22/22 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long S = 0; // tong tat ca cac tui
long long minOdd = LLONG_MAX; // tui le nho nhat
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
S += a;
if (a % 2 == 1) minOdd = min(minOdd, a);
}
// Neu tong chan thi lay het. Neu tong le thi phai bo di 1 tui le nho nhat
// (bo hai tui le hoac nhieu hon chi lam giam tong nhieu hon)
if (S % 2 == 0) cout << S << "\n";
else cout << S - minOdd << "\n";
return 0;
}
Bình luận