Hướng dẫn giải của Chia hết (Đề chọn ĐTQG Phú Thọ 2017-2018)
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
Điền ~n-1~ dấu ~+~, ~-~ vào giữa các số sao cho tổng chia hết cho ~k~. Chỉ cần quan tâm số dư của tổng khi chia cho ~k~, nên ta quy hoạch động theo (vị trí, số dư) rồi truy vết để in cách điền.
Lưu ý về đáp án: đề cho phép in một cách bất kỳ nhưng máy chấm so từng chữ, nên chương trình phải chọn đúng cách điền như đáp án của ban giám khảo. Quy tắc khớp dữ liệu chấm: số dư tính bằng phép % của C++ (có thể âm, nằm trong khoảng ~(-k, k)~). Đi từ trái sang phải, ở bước ~i~ duyệt các số dư ~r~ đạt được sau ~i-1~ số theo thứ tự tăng dần (từ ~-k+1~ đến ~k-1~), thử dấu ~+~ (số dư mới ~(r + a_i) \% k~) trước rồi dấu ~-~ (~(r - a_i) \% k~); số dư mới nào được đạt tới lần đầu tiên thì ghi lại dấu và số dư trước đó. Cuối cùng truy vết ngược từ số dư ~0~ ở vị trí ~n~. (Cách điền trong ví dụ của đề khác cách này nhưng cũng đúng.)
Sub 1: Vét cạn — ~O(2^{n} \cdot n)~, dùng khi ~n \le 20~
Thử cả ~2^{n-1}~ cách điền dấu, ghi lại ở mỗi vị trí ~i~ tập các số dư (kiểu C++) có thể đạt được. Nếu số dư ~0~ không đạt được ở vị trí ~n~ thì in 0. Ngược lại truy vết từ cuối: ở vị trí ~i~ với số dư ~r~, tìm số dư trước nhỏ nhất (ưu tiên dấu ~+~) dẫn tới ~r~ — đúng bằng quy tắc "đạt lần đầu" ở trên. Nếu chỉ nộp sub này: đúng 8/16 test.
Sub 2: Quy hoạch động theo số dư — ~O(n \cdot k)~
Mảng ~tr[i][r]~ cho biết số dư ~r~ đạt được sau ~i~ số chưa và bằng dấu gì, ~pre[i][r]~ là số dư trước đó. Vì số dư có thể âm nên cộng thêm ~k~ khi làm chỉ số mảng. Mỗi bước duyệt ~2k~ số dư, tổng ~O(n \cdot k)~ với ~n \le 10^4, k \le 100~ rất nhanh. Bài này nhỏ nên lưu cả bảng truy vết (khoảng ~10^4 \cdot 201~ phần tử) vẫn vừa bộ nhớ. Nếu chỉ nộp sub này: đúng 16/16 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~n \le 20~ 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;
int n, k;
int a[10005];
// Số dư được tính bằng phép % của C++ nên nằm trong khoảng (-k, k); cộng thêm OFF = k để làm chỉ số mảng
// Quy tắc chọn đáp án (khớp dữ liệu chấm): duyệt số dư trước đó r tăng dần (từ -k+1 đến k-1),
// thử dấu + trước dấu -, số dư mới nào được đến LẦN ĐẦU thì ghi nhận cách đến đó; cuối cùng truy vết từ số dư 0.
// Sub 1: vét cạn 2^(n-1) cách điền dấu để biết ở mỗi vị trí i có thể đạt những số dư nào,
// sau đó truy vết theo quy tắc trên. Dùng khi n <= 20
void sub1() {
vector<set<int>> reach(n + 1); // reach[i] = các số dư (kiểu C++) đạt được sau i số
for (int mask = 0; mask < (1 << (n - 1)); mask++) {
int r = a[1] % k;
reach[1].insert(r);
for (int i = 2; i <= n; i++) {
r = ((mask >> (i - 2)) & 1) ? (r - a[i]) % k : (r + a[i]) % k;
reach[i].insert(r);
}
}
if (!reach[n].count(0)) { printf("0\n"); return; }
string res(n - 1, '+');
int r = 0;
for (int i = n; i >= 2; i--) {
// tìm số dư trước nhỏ nhất (ưu tiên dấu +) dẫn tới r
for (int p : reach[i - 1]) { // set duyệt tăng dần
if ((p + a[i]) % k == r) { res[i - 2] = '+'; r = p; break; }
if ((p - a[i]) % k == r) { res[i - 2] = '-'; r = p; break; }
}
}
printf("1\n%s\n", res.c_str());
}
// Sub 2: quy hoạch động theo số dư, O(n * k)
// tr[i][r + OFF] = 0 nếu chưa đạt; 1 nếu đạt bằng dấu +; 2 nếu đạt bằng dấu -; pre[i][r + OFF] = số dư trước đó
static char tr[10005][205];
static short pre[10005][205];
void sub2() {
const int OFF = k;
tr[1][a[1] % k + OFF] = 3; // trạng thái xuất phát
for (int i = 2; i <= n; i++)
for (int r = -k + 1; r <= k - 1; r++) {
if (!tr[i - 1][r + OFF]) continue;
int x = (r + a[i]) % k, y = (r - a[i]) % k;
if (!tr[i][x + OFF]) { tr[i][x + OFF] = 1; pre[i][x + OFF] = r; }
if (!tr[i][y + OFF]) { tr[i][y + OFF] = 2; pre[i][y + OFF] = r; }
}
if (!tr[n][OFF]) { printf("0\n"); return; }
string res(n - 1, '+');
int r = 0;
for (int i = n; i >= 2; i--) {
res[i - 2] = (tr[i][r + OFF] == 1 ? '+' : '-');
r = pre[i][r + OFF];
}
printf("1\n%s\n", res.c_str());
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận