Hướng dẫn giải của Chia dãy bằng nhau
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
Chia dãy thành nhiều đoạn liên tiếp sao cho mọi đoạn có cùng tổng. Nếu có ~K~ đoạn với tổng mỗi đoạn là ~s~ thì ~K \cdot s = T~ (~T~ là tổng cả dãy), nên chỉ cần thử các giá trị ~s~ phù hợp. Với một ~s~ cố định, đi từ trái sang phải và cắt ngay khi tổng đoạn hiện tại bằng ~s~ là cách cắt được nhiều đoạn nhất và chỉ số cuối nhỏ nhất.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 30~
Thử mọi tổng đoạn liên tiếp làm ~s~, với mỗi ~s~ cắt tham lam, giữ phương án có nhiều đoạn nhất.
Sub 2: Chỉ thử ~s = T/K~ — ~O(n^2)~
Chỉ thử ~s = T/K~ với ~K~ là ước của ~T~ (nếu ~T = 0~ thì ~s = 0~). Mỗi ~s~ cắt tham lam trong ~O(n)~.
Chương trình hoàn chỉnh
Chương trình đọc ~n~ và dãy; nếu ~n \le 30~ gọi sub1, còn lại gọi sub2. Khi có nhiều phương án cùng số đoạn, chọn phương án có tổng các chỉ số cuối nhỏ nhất (cách hiểu “tổng các phần tử” trong đề là tổng các chỉ số cuối; đề mơ hồ chỗ này).
Bài này không có test chấm (checker báo NO_TESTS): lời giải chưa được kiểm chứng trên máy chấm. Đã chạy thử ví dụ của đề cho kết quả 3 / 1 3 6.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[105]; // a[1..n]
long long T; // tong toan bo day
// Voi tong moi doan la s, di tu trai sang phai: moi khi tong doan hien tai dung bang s thi cat.
// Cat som nhat la tot nhat (tong chi so cuoi nho nhat). Tra ve chi so cuoi cua cac doan;
// neu khong cat den dung chi so n thi tra ve rong (khong phai phuong an hop le).
vector<int> greedyCut(long long s) {
vector<int> ends;
long long cur = 0;
for (int i = 1; i <= n; i++) {
cur += a[i];
if (cur == s) {
ends.push_back(i);
cur = 0;
}
}
if (ends.empty() || ends.back() != n) ends.clear();
return ends;
}
// Giu lai phuong an tot hon: nhieu doan hon thi tot hon; cung so doan thi chon tong chi so cuoi nho hon
void consider(const vector<int>& ends, vector<int>& best) {
if (ends.empty()) return;
if (ends.size() > best.size()) {
best = ends;
return;
}
if (ends.size() == best.size()) {
long long s1 = accumulate(ends.begin(), ends.end(), 0LL);
long long s2 = accumulate(best.begin(), best.end(), 0LL);
if (s1 < s2) best = ends;
}
}
void printAns(const vector<int>& best) {
cout << best.size() << "\n";
for (size_t i = 0; i < best.size(); i++) cout << best[i] << (i + 1 < best.size() ? ' ' : '\n');
}
// Sub 1: vet can. Thu moi tong doan lien tiep [i..j] lam tong cua moi doan, cat tham lam, giu phuong an tot.
// O(n^3). Dung khi n <= 30
void sub1() {
vector<int> best;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
long long s = 0;
for (int k = i; k <= j; k++) s += a[k];
consider(greedyCut(s), best);
}
printAns(best);
}
// Sub 2: day du. Neu cac doan co cung tong s va co K doan thi K*s = T (tong ca day),
// nen chi can thu s = T/K voi K la uoc cua T (neu T = 0 thi s = 0). O(n^2).
void sub2() {
vector<int> best;
if (T == 0) {
consider(greedyCut(0), best);
} else {
for (int K = 1; K <= n; K++)
if (T % K == 0) consider(greedyCut(T / K), best);
}
printAns(best);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
T = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
T += a[i];
}
if (n <= 30) sub1();
else sub2();
return 0;
}
Bình luận