Hướng dẫn giải của [200 đề thầy Đức] Bài 195: Chia dãy
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 ~k~ đoạn liên tiếp, mỗi đoạn có tổng lẻ. Gọi ~P_i~ là tổng tiền tố. Đoạn ~(i, j]~ có tổng lẻ khi ~P_i~ và ~P_j~ khác tính chẵn lẻ. Vì vậy điểm cắt thứ ~j~ (với ~r_k = n~) phải thỏa ~P_{r_j} \equiv j \pmod{2}~, bắt đầu từ ~P_0 = 0~ chẵn.
Sub 1: Quy hoạch động — ~O(k \cdot n^2)~, dùng khi ~n \le 60~
Đặt ~f[m][i]~ là có thể chia ~a_{i+1}, \dots, a_n~ thành ~m~ đoạn lẻ hay không, tính theo quy hoạch động. Nếu ~f[k][0]~ đúng thì lần ngược từ đầu, mỗi bước chọn điểm cắt nhỏ nhất còn đảm bảo chia tiếp được. Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Tham lam — ~O(n)~
Quét ~i = 1, \dots, n-1~ và lấy ngay điểm đầu tiên có tính chẵn lẻ đúng với yêu cầu của điểm cắt kế tiếp, đến khi đủ ~k-1~ điểm cắt. Cuối cùng kiểm tra ~P_n \equiv k \pmod{2}~. Cách này cho cùng kết quả với sub 1. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~q~ truy vấn. Với mỗi truy vấn, nếu ~n \le 60~ thì gọi sub1, ngược lại gọi sub2. In NO, hoặc YES kèm dòng chỉ số ~r_1, \dots, r_k~.
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[100005];
long long P[100005]; // tổng tiền tố P[i] = a[1] + ... + a[i]
// Quy tắc chung: đoạn (i, j] có tổng lẻ khi P[i] và P[j] khác tính chẵn lẻ.
// Các điểm cắt r_1 < ... < r_k = n phải có P[r_j] cùng tính chẵn lẻ với j (mod 2), vì P[0] = 0 chẵn.
// Sub 1: vét cạn bằng quy hoạch động O(k * n^2). f[m][i]: có thể chia a[i+1..n] thành m đoạn lẻ không?
// Lấy điểm cắt nhỏ nhất có thể ở mỗi bước, để kết quả trùng với sub 2.
void sub1() {
vector<vector<char>> f(k + 1, vector<char>(n + 1, 0));
f[0][n] = 1;
for (int m = 1; m <= k; m++)
for (int i = 0; i < n; i++)
for (int t = i + 1; t <= n && !f[m][i]; t++)
if (((P[t] - P[i]) % 2 + 2) % 2 == 1 && f[m - 1][t]) f[m][i] = 1;
if (!f[k][0]) {
printf("NO\n");
return;
}
printf("YES\n");
int p = 0;
for (int s = 1; s <= k; s++) {
for (int t = p + 1; t <= n; t++)
if (((P[t] - P[p]) % 2 + 2) % 2 == 1 && f[k - s][t]) {
printf("%d%c", t, s == k ? '\n' : ' ');
p = t;
break;
}
}
}
// Sub 2: O(n). Tham lam: chọn điểm cắt sớm nhất có đúng tính chẵn lẻ cần thiết.
// Điểm cắt thứ j cần P lẻ nếu j lẻ, chẵn nếu j chẵn. Cuối cùng cần P[n] cùng tính chẵn lẻ với k.
void sub2() {
vector<int> cut;
int need = 1; // cần tìm điểm cắt tiếp theo có P lẻ (j = 1)
for (int i = 1; i < n && (int)cut.size() < k - 1; i++) {
if (P[i] % 2 == need) {
cut.push_back(i);
need ^= 1;
}
}
if ((int)cut.size() < k - 1 || (P[n] % 2) != (k % 2)) {
printf("NO\n");
return;
}
cut.push_back(n);
printf("YES\n");
for (int j = 0; j < k; j++) printf("%d%c", cut[j], j == k - 1 ? '\n' : ' ');
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
cin >> n >> k;
P[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
P[i] = P[i - 1] + a[i];
}
if (n <= 60) sub1(); // dữ liệu nhỏ: quy hoạch động
else sub2();
}
return 0;
}
Bình luận