Hướng dẫn giải của [COUNTPRIME] Số lượng nguyên 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
Với mỗi x, cần phân tích x thành tổng nhiều số nguyên tố nhất, mỗi số nguyên tố dùng một lần, riêng một số nguyên tố nào đó được phép dùng hai lần. Đây là bài cái túi (knapsack) trên tập các số nguyên tố không quá ~10^4~.
Sub 1: Vét cạn quay lui — dùng khi mọi ~x \le 60~
Duyệt các số nguyên tố theo thứ tự tăng dần; với mỗi số chọn dùng 0 lần, 1 lần, hoặc 2 lần (nếu chưa có số nào dùng 2 lần), cắt nhánh khi vượt quá phần còn lại. Số lượng lớn nhất thu được là đáp án (~f(1)=1~ theo quy ước). Rất chậm khi x lớn. Nếu chỉ nộp sub này: đúng 6/14 test.
Sub 2: Quy hoạch động cái túi — ~O(\pi(X) \cdot X)~ với ~X = 10^4~
Gọi ~d_0[s]~ là số lượng nhiều nhất tạo tổng ~s~ khi chưa dùng số nào hai lần, ~d_1[s]~ là khi đã dùng một số hai lần (hoặc không dùng cũng được). Với mỗi số nguyên tố ~p~, duyệt ~s~ giảm dần: ~d_1[s]~ lấy max của ~d_1[s-p]+1~ và ~d_0[s-2p]+2~, ~d_0[s]~ lấy max của ~d_0[s-p]+1~. Cần cập nhật ~d_1~ trước ~d_0~ để không dùng nhầm giá trị đã cập nhật. Tính một lần cho mọi x rồi trả lời từng truy vấn, đáp án là ~\max(d_0[x], d_1[x])~. Nếu chỉ nộp sub này: đúng 14/14 test.
Chương trình hoàn chỉnh
Main đọc hết các x (máy chấm dùng file COUNTPRIME.INP/OUT), nếu mọi x nhỏ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int MX = 10000;
vector<int> q, pr;
int best;
// Sub 1: vét cạn quay lui - duyệt các số nguyên tố tăng dần, mỗi số dùng 0, 1 hoặc 2 lần
// (tối đa một số được dùng 2 lần). Dùng khi mọi x <= 60.
void dfs(int idx, int rest, int cnt, bool dup) {
if (rest == 0) { best = max(best, cnt); return; }
if (idx == (int)pr.size() || pr[idx] > rest) return;
int p = pr[idx];
dfs(idx + 1, rest, cnt, dup); // không dùng p
dfs(idx + 1, rest - p, cnt + 1, dup); // dùng 1 lần
if (!dup && rest >= 2 * p) dfs(idx + 1, rest - 2 * p, cnt + 2, true); // dùng 2 lần
}
void sub1() {
for (int x : q) {
if (x == 1) { printf("1\n"); continue; }
best = 0;
dfs(0, x, 0, false);
printf("%d\n", best);
}
}
// Sub 2: quy hoạch động kiểu cái túi, tính trước cho mọi x <= 10^4.
// d0[s]: số lượng lớn nhất khi chưa dùng số nào 2 lần; d1[s]: đã dùng (hoặc được phép) 1 số 2 lần.
void sub2() {
const int NEG = -1000000;
vector<int> d0(MX + 1, NEG), d1(MX + 1, NEG);
d0[0] = d1[0] = 0;
for (int p : pr) {
for (int s = MX; s >= p; s--) {
int v = d1[s];
if (d1[s - p] > NEG) v = max(v, d1[s - p] + 1);
if (s >= 2 * p && d0[s - 2 * p] > NEG) v = max(v, d0[s - 2 * p] + 2);
d1[s] = v; // cập nhật d1 trước khi sửa d0
if (d0[s - p] > NEG) d0[s] = max(d0[s], d0[s - p] + 1);
}
}
for (int x : q) {
if (x == 1) printf("1\n");
else printf("%d\n", max(d0[x], d1[x]));
}
}
int main() {
freopen("COUNTPRIME.INP", "r", stdin);
freopen("COUNTPRIME.OUT", "w", stdout);
int x, mx = 0;
while (scanf("%d", &x) == 1) { q.push_back(x); mx = max(mx, x); }
vector<bool> comp(MX + 1, false);
for (int i = 2; i <= MX; i++) {
if (!comp[i]) { pr.push_back(i); for (int j = i * i; j <= MX; j += i) comp[j] = true; }
}
if (mx <= 60) sub1();
else sub2();
return 0;
}
Bình luận