Nguồn: Codeforces GroupĐộ khó: Trung bìnhƯớc chung lớn nhấtTiền tố – hậu tố
Đề bài
Sắp đến đợt kiểm tra học kì, Nam rất lo lắng về điểm môn tin học. Vì Nam là 1 học sinh giỏi toàn diện nên cậu muốn điểm môn tin phải cao. Sau khi học tất cả kiến thức cơ bản, cậu thấy môn tin học cực kì dễ dàng. Đến hôm kiểm tra, thầy cho 1 bài khá khó nên Nam không làm được, vì thế nên Nam nhờ các Luyencode Coder làm hộ bài.
Đề bài: cho 1 dãy $a_i$ có $n$ phần tử. Bạn hãy thay thế 1 phần tử trong đoạn $[1, 10^9]$ của dãy $a_i$ để tạo ước chung lớn nhất của dãy $a_i$. Hãy in ra ước chung lớn nhất của dãy $a_i$.
(Hiểu là: chọn đúng 1 phần tử, thay nó bằng một số nguyên bất kỳ trong đoạn $[1, 10^9]$, sao cho ước chung lớn nhất của cả dãy sau khi thay là lớn nhất có thể. In ra giá trị lớn nhất đó.)
Dữ liệu vào:
Dòng 1 là số nguyên $n$ $(1 \le n \le 10^6)$.
Dòng 2 là $n$ số nguyên $a_i$ $(1 \le a_i \le 10^6)$.
Dữ liệu ra: là đáp án của bài toán mà Nam nhờ code hộ.
Ví dụ – input
3
4 6 3
Ví dụ – output
3
Gợi ý của đề: thay đổi $a_1$ thành bất kì số nào chia hết cho 3. Khi đó dãy là $(3k, 6, 3)$ có ước chung lớn nhất bằng $3$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm thêm đó là toàn bộ tin nhắn của mình với em ấy, để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn. Chúc các bạn học tốt và gặt hái nhiều thành công 😇.
Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
“bài này thì em chưa có ý tưởng luôn a. anh cho e 1 vài gợi ý bài này với”
Gợi ý à, hmmm… em sẽ thấy rằng việc nói thay thế 1 giá trị bất kỳ bằng 1 giá trị khác, bản chất của nó có thể nói thẳng ra là loại bỏ giá trị đó ra và tính ước chung lớn nhất của các thằng còn lại thôi 🙂.
Tại vì sao? Giả sử có 5 thằng, giờ cần thay thế 1 thằng, thì ước chung lớn nhất của 4 thằng còn lại giả sử là 4 đi, nhưng vì tính ước chung lớn nhất với cái thằng mà mình đang tính thay thế nên ước chung lớn nhất chỉ còn 2. Vậy nếu mình bỏ thằng đó ra thì ước chung lớn nhất của 4 thằng sẽ là 4 rồi, thì cái thằng mình bỏ ra mình sẽ thay thế nó chính bằng 4 luôn, hoặc 1 số bất kỳ chia hết cho 4, thì coi như ước chung lớn nhất vẫn sẽ được bảo toàn.
Chắc chắn không thể có cách nào thay thế mà ước chung lớn nhất vượt qua 4 được, tại vì đã là ước thì nó chỉ có thể từ đó giảm xuống chứ không có chuyện tăng lên.
Kết luận
Đáp án $= \max\limits_{i} \text{UCLN}(\text{tất cả các phần tử trừ } a_i)$. Thay $a_i$ bằng chính giá trị UCLN đó (luôn $\le 10^6 \le 10^9$ nên hợp lệ) là đạt được.
Đó, thì em hãy nghĩ đến điều đó 😀 gợi ý của anh là như thế, nói thêm nữa sẽ mất vui nè ^^
Kiến thứcTìm UCLN của cả dãy N phần tử
Cũng nói thêm cho em biết làm thế nào để tìm được ước chung lớn nhất của dãy $N$ phần tử từ $a_1$ đến $a_n$?
Đầu tiên nó tìm ước chung lớn nhất của $a_1$ và $a_2$. Sau đó lấy ước chung lớn nhất đó và tìm ước chung lớn nhất của chính nó với $a_3$. Và cứ thế làm tương tự với $a_4, a_5, \ldots$ cho đến $a_n$. Sau cùng kết quả thu được nó là ước chung lớn nhất của dãy $N$ phần tử.
Mẹo nhỏ: $\text{UCLN}(0, x) = x$, nên có thể cho biến kết quả bắt đầu từ $0$ rồi cứ lần lượt "gộp" từng phần tử vào. Hàm __gcd của C++ và math.gcd của Python đều chạy đúng như vậy.
HV
“A gợi ý xí xi nưaz a Sơn”
Ok. Với từng vị trí $i$, hãy tìm ước chung lớn nhất của toàn bộ các phần tử còn lại ngoài vị trí $i$. Và so sánh kết quả Max với lần lượt từng vị trí $i$. Ví dụ test 4 6 3:
Vị trí bỏ
Dãy
UCLN phần còn lại
Bỏ đi 4
463
UCLN(6, 3) = 3
✔ Max
Bỏ đi 6
463
UCLN(4, 3) = 1
Bỏ đi 3
463
UCLN(4, 6) = 2
⇒ Max chọn 3.
Cách 1Vét cạn: bỏ từng vị trí rồi tính lại – O(N² log A)
Làm đúng y như gợi ý trên: với mỗi $i$, duyệt lại cả dãy (trừ $a_i$) để tính UCLN. Code này mình viết thêm để các bạn dễ hình dung và để dùng làm code đối chứng:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
if(n == 1){
cout << 1000000000;
return 0;
}
int Max = 0;
for(int i = 0; i < n; ++i){
int g = 0;
for(int j = 0; j < n; ++j){
if(j != i){
g = __gcd(g, a[j]);
}
}
Max = max(Max, g);
}
cout << Max;
return 0;
}
import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
if n == 1:
print(10**9)
else:
Max = 0
for i in range(n):
g = 0
for j in range(n):
if j != i:
g = gcd(g, a[j])
Max = max(Max, g)
print(Max)
C++▶ Chạy tay từng dòng codeCách 1 (vét cạn): bỏ từng vị trí i rồi tính lại UCLN cả phần còn lại, O(N² log A).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<int> a(n);
10for(int i = 0; i < n; ++i){
11cin >> a[i];
12 }
13if(n == 1){
14cout << 1000000000;
15return0;
16 }
17int Max = 0;
18for(int i = 0; i < n; ++i){
19int g = 0;
20for(int j = 0; j < n; ++j){
21if(j != i){
22 g = __gcd(g, a[j]);
23 }
24 }
25 Max = max(Max, g);
26 }
27cout << Max;
28return0;
29}
Riêng trường hợp $n = 1$: bỏ phần tử duy nhất đi thì không còn ai ràng buộc, ta thay nó bằng số lớn nhất được phép là $10^9$, UCLN của dãy 1 phần tử chính là nó, nên đáp án là $10^9$.
Nhưng chẳng lẽ cứ mỗi lần không tính 1 vị trí $i$ mà ta lại phải duyệt lại toàn bộ $n - 1$ phần tử để tìm ước chung lớn nhất (gọi tắt là UCLN)? Như thế thì rất lâu. Bởi vì UCLN của $n - 1$ phần tử là phải xét qua $n - 2$ cặp, với mỗi cặp tìm ra UCLN của 2 đứa. Em có biết là hàm __gcd có sẵn tìm UCLN của 2 số nó được xây dựng tối ưu rồi thì độ phức tạp sẽ là $O(\log(\min(a, b)))$ không? Mà mỗi lần loại đi 1 vị trí $i$ là phải xét $n - 2$ cặp, mà ta có đến $n$ vị trí $i$ cần xét, vậy số cặp phải xét là $n \cdot (n - 2)$. Vậy có thể thấy độ phức tạp sẽ là $n \cdot (n - 2) \cdot \log(\min(a, b))$, nội $n \cdot (n - 2)$ đã coi như $n^2$.
Bài đó cho $n$ tối đa $10^6$ thì như thế $n^2$ là phải xét qua cả $10^{12}$ cặp, là đủ TLE rồi (vì ngưỡng tối đa 1 giây chỉ là $10^8$ thôi), còn chưa tính đến chi phí tìm UCLN giữa 2 thằng. Nên chắc chắn làm như vậy sẽ bị TLE.
Cách 2Hai mảng phụ left, right – O(N log A) – AC
HV
“triển khai codde này có cần kỹ thuật dùng 2 mảng phụ để sử lý à anh”
Đúng, cần phải có mảng phụ.
HV
“tại sao phải tìm gcd cả dãy theo 2 chiều vậy anh”
Có phải nếu mảng $n$ phần tử, với từng vị trí $i$ ta sẽ giả sử loại bỏ phần tử $a_i$ đó không tính nó, chỉ tính UCLN của các phần tử còn lại, nghĩa là UCLN của $a_0, a_1,$ $\ldots,$ $a_{i-1},$ $a_{i+1},$ $\ldots,$ $a_{n-1}$. Như Cách 1 đã phân tích, tính lại từ đầu cho mỗi $i$ thì quá lâu. Vậy nên 1 cách tốt hơn là tạo:
Mảng left với ý nghĩa left[i] là UCLN của toàn bộ các phần tử từ đầu mảng tính đến ngay tại vị trí $i$, tức là left[i] = UCLN$(a_0, a_1, a_2, \ldots, a_i)$.
Tương tự có mảng right với ý nghĩa right[i] là UCLN của toàn bộ các phần tử từ vị trí $i$ trở về cuối mảng, tức là right[i] = UCLN$(a_i, a_{i+1}, a_{i+2}, \ldots, a_{n-1})$.
Vậy có phải khi xét đến 1 vị trí $i$ cần loại bỏ thì thay vì phải xét tìm UCLN của $n - 1$ thằng còn lại, lúc này ta chỉ cần tìm UCLN giữa thằng left[i - 1] và thằng right[i + 1] là coi như nó chính là kết quả UCLN của toàn bộ mảng sau khi đã loại thằng a[i] ra. Em ngẫm xem đúng không nè ^^
Hai đầu mút thì đặc biệt hơn chút: bỏ $a_0$ thì phần còn lại chính là right[1], bỏ $a_{n-1}$ thì phần còn lại chính là left[n - 2]. Em nhập dãy rồi bấm Tiếp để xem cả quá trình dựng 2 mảng và ghép kết quả:
Ví dụ nhanh:
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), left(n), right(n);
cin >> a[0];
left[0] = a[0];
for(int i = 1; i < n; ++i){
cin >> a[i];
left[i] = __gcd(left[i - 1], a[i]);
}
right[n - 1] = a[n - 1];
for(int i = n - 2; i >= 0; --i){
right[i] = __gcd(right[i + 1], a[i]);
}
int Max = max(right[1], left[n - 2]);
int sz = n - 1;
for(int i = 1; i < sz; ++i){
Max = max(Max, __gcd(left[i - 1], right[i + 1]));
}
cout << Max;
return 0;
}
import sys
import math
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
left = [0] * n
right = [0] * n
left[0] = a[0]
for i in range(1, n):
left[i] = math.gcd(left[i - 1], a[i])
right[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
right[i] = math.gcd(right[i + 1], a[i])
Max = max(right[1], left[n - 2])
sz = n - 1
for i in range(1, sz):
Max = max(Max, math.gcd(left[i - 1], right[i + 1]))
print(Max)
Duyệt ngược từ cuối để tính right[i] = __gcd(right[i + 1], a[i]).
Max khởi tạo bằng kết quả của 2 đầu mút: max(right[1], left[n - 2]).
Các vị trí ở giữa $1 \le i \le n - 2$: __gcd(left[i - 1], right[i + 1]).
Lưu ý trường hợp n = 1
Đề cho $1 \le n$, nhưng code trên khi $n = 1$ sẽ truy cập right[1] và left[-1], ra ngoài mảng (bản Python sẽ báo lỗi IndexError). Code này đã AC trên hệ thống nên có lẽ bộ test không có $n = 1$. Để chắc ăn, em có thể thêm vào ngay sau khi đọc $n$: if(n == 1){ cout << 1000000000; return 0; } như trong Cách 1 và Cách 3 nhé.
Không gian$O(N)$
Thời gian$O(N \log A)$
HV
“Ồ em hiểu r ạ. Cái này là lúc làm anh nghĩ ra luôn hay kinh nghiệm thế anh”
Lúc anh đọc vào đề là sau tầm vài phút anh nghĩ ra ý tưởng này á ^^ Đại khái là cứ hãy luôn nghĩ trong đầu: hãy làm sao để tiết kiệm chi phí phải xét duyệt. Cứ luôn nghĩ về điều đó sẽ giúp ta nhìn ra được những hướng giải tốt hơn.
Thậm chí anh còn đang suy nghĩ: bài đó cả thảy anh dùng 3 mảng. Anh cho rằng có thể bỏ bớt 1 mảng đi. Em thử nghĩ xem ^^
Cách 3Bỏ bớt mảng left – lời giải câu đố của anh
Đây là phần mình viết thêm để trả lời câu đố trên, các bạn tự nghĩ trước rồi hãy đọc nha 😉. Để ý là khi duyệt $i$ từ trái sang phải, left[i - 1] chỉ được dùng đúng 1 lần rồi bỏ. Vậy thay vì lưu cả mảng left, ta dùng 1 biến g = UCLN của các phần tử đứng trước $i$, vừa duyệt vừa gộp dần:
Tính mảng right như cũ, nhưng cho thêm 1 ô right[n] = 0 (vì UCLN$(0, x) = x$, ô này đóng vai "rỗng").
Với mỗi $i$ từ $0$ đến $n - 1$: kết quả khi bỏ $a_i$ là __gcd(g, right[i + 1]), rồi gộp $a_i$ vào: g = __gcd(g, a[i]).
Nhờ g = 0 lúc đầu và right[n] = 0, hai đầu mút được xử lý luôn trong cùng 1 vòng lặp, không cần tách riêng.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), right(n + 1, 0);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
if(n == 1){
cout << 1000000000;
return 0;
}
for(int i = n - 1; i >= 0; --i){
right[i] = __gcd(right[i + 1], a[i]);
}
int Max = 0, g = 0;
for(int i = 0; i < n; ++i){
Max = max(Max, __gcd(g, right[i + 1]));
g = __gcd(g, a[i]);
}
cout << Max;
return 0;
}
import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
if n == 1:
print(10**9)
else:
right = [0] * (n + 1)
for i in range(n - 1, -1, -1):
right[i] = gcd(right[i + 1], a[i])
Max = 0
g = 0
for i in range(n):
Max = max(Max, gcd(g, right[i + 1]))
g = gcd(g, a[i])
print(Max)
C++▶ Chạy tay từng dòng codeCách 3: chỉ giữ mảng right, phần UCLN bên trái gộp dần vào biến g, O(N log A).
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4int main(){
5ios::sync_with_stdio(0);
6cin.tie(0);
7int n;
8cin >> n;
9vector<int> a(n), right(n + 1, 0);
10for(int i = 0; i < n; ++i){
11cin >> a[i];
12 }
13if(n == 1){
14cout << 1000000000;
15return0;
16 }
17for(int i = n - 1; i >= 0; --i){
18 right[i] = __gcd(right[i + 1], a[i]);
19 }
20int Max = 0, g = 0;
21for(int i = 0; i < n; ++i){
22 Max = max(Max, __gcd(g, right[i + 1]));
23 g = __gcd(g, a[i]);
24 }
25cout << Max;
26return0;
27}
Vẫn là $O(N \log A)$ thời gian, nhưng chỉ còn 2 mảng $a$ và right. Thật ra cũng có thể bỏ luôn mảng $a$ bằng cách đọc dữ liệu 2 lần… nhưng đọc input chỉ được 1 lần thôi, nên 2 mảng là gọn nhất rồi 😄.
Ghi chú của mình: Cách 1, Cách 3 và các bản Python đi kèm là mình viết thêm; bản Python của Cách 2 là của anh. Tất cả các bản đã được kiểm tra với 400 bộ test ngẫu nhiên (có cả $n = 1$, $n = 2$ và các dãy nhiều bội chung) so với cách tính trực tiếp bằng định nghĩa: khớp 100%. Với $n = 10^6$, bản C++ Cách 2 và Cách 3 chạy khoảng 0.05–0.07 giây, bản Python khoảng 0.7 giây trên máy mình.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
Nguồn: Codeforces GroupĐộ khó: KháQuy hoạch độngĐệ quy có nhớThừa số nguyên tố
Đề bài
Cho trước một dãy số nguyên dương gồm $n$ phần tử. Nhiệm vụ của bạn rất đơn giản, hãy chọn ra $k$ phần tử từ dãy số đã cho sao cho tích của chúng có nhiều chữ số 0 tận cùng bên phải nhất có thể.
Input
Dòng thứ nhất gồm 2 số nguyên dương $n, k$ $(k \le n)$.
Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^{18})$ là dãy số cho trước.
Output
Đưa ra một dòng ghi một số nguyên dương là số chữ số 0 tận cùng bên phải của tích $k$ phần tử được chọn trong cách chọn tối ưu nhất.
Subtask:
Subtask 1 (60% số điểm): $n \le 20$.
Subtask 2 (40% số điểm): $n \le 100$.
Ví dụ – input
3 2
50 4 20
Ví dụ – output
3
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: cho 2 số nguyên dương $n, k$ với $n \le 100$, $k \le n$; sau đó là $n$ số nguyên dương $a[i]$ với $a[i] \le 10^{18}$. Hãy chọn ra $k$ phần tử từ dãy sao cho tích của $k$ số đã chọn có nhiều chữ số 0 tận cùng bên phải nhất có thể, và in ra số chữ số 0 đó.
Ví dụ: $n = 3$, $k = 2$, $a = \{50, 4, 20\}$. Ta sẽ chọn 2 phần tử là $50$ và $20$, tích của chúng là $50 \times 20 = 1000$, có 3 chữ số 0 ở cuối nên kết quả là $3$.
Cách làm đơn giản nhất của bài này chính là vét cạn thôi, tức là ta thử mọi trường hợp: chọn ra mọi tập con có $k$ phần tử, sau đó nhân vào và xem nó có bao nhiêu số 0. Nhưng mà $a[i] \le 10^{18}$ lận, tức là ta phải dùng kiểu long long để lưu; nếu nhân 2 số lớn vậy thì chắc chắn sẽ bị tràn số, vì long long chỉ lưu được tới khoảng $2^{63}$ thôi mà nhân 2 số $10^{18}$ sẽ bằng $10^{36}$. Nếu $k = n = 100$ thì tích tối đa sẽ là $(10^{18})^{100} = 10^{1800}$, không thể lưu trữ nổi nha.
Vậy để xử lý ta cần biết khi nào thì nhân các số vào sẽ có số 0 ở cuối. Với 1 số nguyên $a[i] \ge 2$ thì ta có thể phân tích nó thành thừa số nguyên tố: $a[i] = p_1^{q_1} \cdot p_2^{q_2} \cdots p_k^{q_k}$ với $p$ là các số nguyên tố. Ví dụ: $2 = 2$; $3 = 3$; $6 = 2 \cdot 3$; $20 = 2^2 \cdot 5$; $50 = 2 \cdot 5^2$. Xem vài phép nhân sau:
Phép nhân
Phân tích
Gộp lại
Kết quả
Số 0 cuối
20 × 50
(2²·5) · (2·5²)
2³·5³
1000
3
20 × 25
(2²·5) · (5²)
2²·5³
500
2
20 × 10
(2²·5) · (2·5)
2³·5²
200
2
60 × 40
(2²·3·5) · (2³·5)
2⁵·3·5²
2400
2
Từ vài ví dụ trên ta sẽ thấy: số 0 ở cuối sẽ chỉ phụ thuộc vào số mũ của 2 và số mũ của 5 mà thôi. Cụ thể kết quả là $2^x \cdot 5^y \cdot (\ldots)$ thì số chữ số 0 ở cuối sẽ bằng $\min(x, y)$, vì mỗi cặp $2 \cdot 5 = 10$ là thêm 1 số 0 ở cuối. $2^3 \cdot 5^3 = 10^3$ có 3 chữ số 0; $2^3 \cdot 5^4$ thì cũng chính là $2^3 \cdot 5^3$ thôi, thừa lại 1 số 5; tương tự với $2^4 \cdot 5^3$, kết quả đều cho ra 3 số 0 ở cuối.
20 × 50 = 2³·5³
25=10
25=10
25=10
min(3, 3) = 3 số 0 → 1000
20 × 25 = 2²·5³
25=10
25=10
5thừa
min(2, 3) = 2 số 0 → 500
60 × 40 = 2⁵·5²·3
25=10
25=10
2thừa
2thừa
2thừa
min(5, 2) = 2 số 0 → 2400
Chính vì vậy khi ta chọn ra được $k$ số thì ta không cần nhân hết chúng vào, mà chỉ cần ở mỗi số phân tích xem nó là $2^{\text{mấy}}$ và $5^{\text{mấy}}$. Vì $2^{x_1} \cdot 2^{x_2} \cdots 2^{x_k}$ $= 2^{x_1 + x_2 + \ldots + x_k}$ nên số mũ của 2 trong tích là $x = x_1 + x_2 + \ldots + x_k$: phần tử đầu phân tích được $2^{x_1}$ thì x += x1, phần tử thứ 2 được $2^{x_2}$ thì x += x2, cứ vậy đến $x_k$. Làm tương tự với 5 ta có $2^x$ và $5^y$, lúc này số số 0 ở cuối là $\min(x, y)$.
Giờ ta sẽ viết một hàm giúp ta biết khi phân tích 1 số $n$ ra thừa số nguyên tố thì số mũ của số nguyên tố $p$ là bao nhiêu, tức $n = \ldots \cdot p^{cnt} \cdot \ldots$ thì hàm trả về $cnt$:
typedef long long ll;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
Đầu tiên ta khởi tạo biến đếm bằng 0, và chừng nào $n$ còn chia hết cho $p$ thì ta tăng biến đếm và lấy $n$ chia cho $p$. Bởi vì $n = \ldots \cdot p^{cnt} \cdot \ldots$ nên $n$ sẽ chia hết cho $p$ được đúng $cnt$ lần. Ví dụ countP(50, 5): $50 \to 10 \to 2$, chia được 2 lần nên trả về 2.
Cách 1Đệ quy chọn / không chọn – O(2^N)
Đầu vào ta lưu mảng a với mỗi phần tử a[i] là một pair<int, int>: .first lưu số mũ của 2, .second lưu số mũ của 5 khi phân tích $a[i]$ ra thừa số nguyên tố. Ta làm vậy để tiện việc khi chọn ra $k$ phần tử thì biết $cnt2$ trong $2^{cnt2}$ và $cnt5$ trong $5^{cnt5}$ của tích $k$ phần tử đó. Cách chọn ra $k$ phần tử như sau:
Gọi hàm Try(i, n, k, cnt2, cnt5) trả về số số 0 nhiều nhất ta có thể kiếm được bằng cách chọn $k$ phần tử nằm trong khoảng từ $i$ tới $n$, với lúc đầu ta đã có $2^{cnt2}$ và $5^{cnt5}$. Mảng a khai báo toàn cục.
Điều kiện dừng có 2 phần:
Khi $k = 0$: không thể chọn thêm phần tử nào nữa, số lượng số 0 kiếm được sẽ là $\min(cnt2, cnt5)$ như đã phân tích ở trên → return min(cnt2, cnt5);
Khi $i = n + 1$: ta đã đi qua hết tất cả các phần tử mà chắc chắn $k \ne 0$ (vì $k = 0$ thì ở trên đã return rồi), tức là đi hết mà vẫn không chọn đủ $k$ phần tử → trường hợp này không hợp lệ, trả về một giá trị rất bé INT_MIN $= -2^{31}$. Vì hàm có mục đích tìm lớn nhất nên để trường hợp không hợp lệ không gây ảnh hưởng thì ta phải trả về giá trị bé nhất.
Xử lý chạy: ở mỗi phần tử $i$ ta có 2 lựa chọn là lấy hoặc không lấy. Biến excl (exclude: không lấy) lưu kết quả của việc không lấy phần tử đó, biến incl (include: có lấy) lưu kết quả của việc có lấy phần tử đó. Tính xong 2 trường hợp thì return max(excl, incl); – trường hợp nào cho nhiều số 0 ở cuối hơn thì lấy trường hợp đó.
Cây lời gọi của Try với ví dụ $a = \{50, 4, 20\}$, $k = 2$ ($50 = 2^1 5^2$, $4 = 2^2$, $20 = 2^2 5^1$): nhánh trái là không lấy, nhánh phải là lấy; ô xanh là $k = 0$ (trả về $\min$), ô đỏ là hết phần tử mà chưa đủ $k$ (trả về INT_MIN), số dưới mỗi ô là giá trị trả về:
Source code về ý tưởng trên cho anh em nào cần tham khảo:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
pii a[105];
int Try(int i, int n, int k, int cnt2, int cnt5) {
if(k == 0) {
return min(cnt2, cnt5);
}
if(i == n + 1) {
return INT_MIN;
}
int excl = Try(i + 1, n, k, cnt2, cnt5);
int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second);
return max(excl, incl);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
ll x;
cin >> x;
a[i] = (pii){countP(x, 2), countP(x, 5)};
}
cout << Try(1, n, k, 0, 0);
return 0;
}
import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [None] + [(countP(int(x), 2), countP(int(x), 5)) for x in data[2:2 + n]]
NEG = -(1 << 31) # giống INT_MIN
def Try(i, k, cnt2, cnt5):
if k == 0:
return min(cnt2, cnt5)
if i == n + 1:
return NEG
excl = Try(i + 1, k, cnt2, cnt5)
incl = Try(i + 1, k - 1, cnt2 + a[i][0], cnt5 + a[i][1])
return max(excl, incl)
print(Try(1, k, 0, 0))
sys.setrecursionlimit(10000)
main()
C++▶ Chạy tay từng dòng codeCách 1: đệ quy Try chọn / không chọn từng phần tử, O(2^N).
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2#defineendl'\n'
3usingnamespace std;
4typedeflonglongll;
5typedefpair<int, int> pii;
6int countP(ll n, ll p) {
7int cnt = 0;
8while(n % p == 0) {
9 cnt++;
10 n /= p;
11 }
12return cnt;
13}
14pii a[105];
15int Try(int i, int n, int k, int cnt2, int cnt5) {
16if(k == 0) {
17returnmin(cnt2, cnt5);
18 }
19if(i == n + 1) {
20return INT_MIN;
21 }
22int excl = Try(i + 1, n, k, cnt2, cnt5);
23int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second);
24returnmax(excl, incl);
25}
26int main() {
27 ios_base::sync_with_stdio(0);
28cin.tie(0);
29int n, k;
30cin >> n >> k;
31for(int i = 1; i <= n; ++i) {
32ll x;
33cin >> x;
34 a[i] = (pii){countP(x, 2), countP(x, 5)};
35 }
36cout << Try(1, n, k, 0, 0);
37return0;
38}
Giải thích một số chỗ trong code:
a[i] = (pii){countP(x, 2), countP(x, 5)}; ở đây chính là mình ép kiểu dữ liệu pair, phải ép thì mới gán được nha.
Try(1, n, k, 0, 0): bắt đầu xét từ phần tử 1 tới phần tử $n$, lúc đầu được chọn $k$ phần tử và $cnt2$, $cnt5$ đều bằng 0 vì chưa chọn phần tử nào cả.
Đánh giá độ phức tạp:
Không gian$O(n)$
Thời gian$O(2^n)$
Trường hợp xấu nhất mỗi phần tử ta đều có 2 cách chọn là chọn hoặc không, nên $n$ phần tử sẽ có $2^n$ cách chọn. Với $n$ tối đa $= 100$ thì không thể nào thực hiện $2^{100}$ phép tính trong 1 giây được, nên cách trên chắc chắn sẽ bị TLE. Code này ăn được subtask 1 ($n \le 20$), tức 60/100 test. Nếu đi thi mà ta code nhanh ra được cách trên đã là ngon lắm rồi nha.
Cách 2Đệ quy có nhớ (top-down) với mảng 4 chiều
Ở đâu ta đệ quy được thì ở đó ta có thể quy hoạch động top-down được hen: nhờ việc lưu trữ lại kết quả ta sẽ tránh được việc tính đi tính lại các trường hợp đã tính rồi 😇. Từ code trên ta thấy mỗi lần gọi hàm thì chỉ có 4 biến thay đổi: i, k, cnt2 và cnt5. Vậy ta tạo hẳn một mảng 4 chiều để lưu kết quả của hàm Try(); mặc dù có thể tràn bộ nhớ hoặc thậm chí TLE nhưng chúng ta liều ăn nhiều nha, biết đâu lại AC thì sao 🤣.
$i$ nằm trong khoảng từ 1 tới $n$ nên chiều đầu tiên có kích thước $n$; $k$ thì giảm dần nên to nhất là $k$ → F[n][k].
$cnt2$ tối đa là bao nhiêu? Đơn giản là lấy $k$ phần tử có số mũ 2 lớn nhất cộng lại → gọi là max2. Làm tương tự với 5 → max5. Mảng thành F[n][k][max2][max5], và phải tạo bằng vector, chứ mảng tĩnh thì không nổi đâu.
Lúc đầu lấp đầy $F = -1$ nghĩa là chưa tính. Sau phần điều kiện dừng ta kiểm tra != -1 tức là đã từng tính rồi thì return luôn; còn chưa thì tính xong gán vào $F$ rồi mới return.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
pii a[105];
int Try(int i, int n, int k, int cnt2, int cnt5,
vector<vector<vector<vector<int>>>> &f) {
if(k == 0) {
return min(cnt2, cnt5);
}
if(i == n + 1) {
return INT_MIN;
}
if(f[i][k][cnt2][cnt5] != -1) {
return f[i][k][cnt2][cnt5];
}
int excl = Try(i + 1, n, k, cnt2, cnt5, f);
int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second, f);
return f[i][k][cnt2][cnt5] = max(excl, incl);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> calc2, calc5;
for(int i = 1; i <= n; ++i) {
ll x;
cin >> x;
a[i] = (pii){countP(x, 2), countP(x, 5)};
calc2.push_back(countP(x, 2));
calc5.push_back(countP(x, 5));
}
sort(calc2.begin(), calc2.end(), greater<int>());
sort(calc5.begin(), calc5.end(), greater<int>());
int max2 = 0, max5 = 0;
for(int i = 0; i < min(k, (int)calc2.size()); ++i) {
max2 += calc2[i];
}
for(int i = 0; i < min(k, (int)calc5.size()); ++i) {
max5 += calc5[i];
}
vector<vector<vector<vector<int>>>>
f(n + 1, vector<vector<vector<int>>>
(k + 1, vector<vector<int>>
(max2 + 1, vector<int>
(max5 + 1, -1))));
cout << Try(1, n, k, 0, 0, f);
return 0;
}
import sys
from functools import lru_cache
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [None] + [(countP(int(x), 2), countP(int(x), 5)) for x in data[2:2 + n]]
NEG = -(1 << 31)
@lru_cache(maxsize=None) # thay cho mảng 4 chiều f[i][k][cnt2][cnt5]
def Try(i, k, cnt2, cnt5):
if k == 0:
return min(cnt2, cnt5)
if i == n + 1:
return NEG
excl = Try(i + 1, k, cnt2, cnt5)
incl = Try(i + 1, k - 1, cnt2 + a[i][0], cnt5 + a[i][1])
return max(excl, incl)
print(Try(1, k, 0, 0))
sys.setrecursionlimit(10000)
main()
C++▶ Chạy tay từng dòng codeCách 2: đệ quy có nhớ, lưu kết quả vào vector 4 chiều f[i][k][cnt2][cnt5].
Dữ liệu mẫu:
1#include<bits/stdc++.h>
2#defineendl'\n'
3usingnamespace std;
4typedeflonglongll;
5typedefpair<int, int> pii;
6int countP(ll n, ll p) {
7int cnt = 0;
8while(n % p == 0) {
9 cnt++;
10 n /= p;
11 }
12return cnt;
13}
14pii a[105];
15int Try(int i, int n, int k, int cnt2, int cnt5,
16vector<vector<vector<vector<int>>>> &f) {
17if(k == 0) {
18returnmin(cnt2, cnt5);
19 }
20if(i == n + 1) {
21return INT_MIN;
22 }
23if(f[i][k][cnt2][cnt5] != -1) {
24return f[i][k][cnt2][cnt5];
25 }
26int excl = Try(i + 1, n, k, cnt2, cnt5, f);
27int incl = Try(i + 1, n, k - 1, cnt2 + a[i].first, cnt5 + a[i].second, f);
46for(int i = 0; i < min(k, (int)calc2.size()); ++i) {
47 max2 += calc2[i];
48 }
49for(int i = 0; i < min(k, (int)calc5.size()); ++i) {
50 max5 += calc5[i];
51 }
52vector<vector<vector<vector<int>>>>
53 f(n + 1, vector<vector<vector<int>>>
54 (k + 1, vector<vector<int>>
55 (max2 + 1, vector<int>
56 (max5 + 1, -1))));
57cout << Try(1, n, k, 0, 0, f);
58return0;
59}
Với cách trên thì vẫn chỉ được 60/100, mấy test còn lại bị MLE (quá giới hạn bộ nhớ) từ việc tạo vector. Phân tích chút cho các bạn thấy: giả sử trường hợp xấu nhất tất cả các số trong mảng là $10^{18} = 2^{18} \cdot 5^{18}$. Nếu $n = k = 100$ thì $max2 = max5 = 18 \times 100 = 1800$, vector 4 chiều có kích cỡ $100^2 \times 1800^2 = 3.24 \cdot 10^{10}$ ô; chỉ riêng việc gán toàn bộ các phần tử bằng $-1$ thôi đã MLE rồi, nên cách trên vẫn không AC được nha.
Cách 3Quy hoạch động bottom-up 3 chiều
Vậy giờ ta đến với cách quy hoạch động bottom-up, chính là quy hoạch động anh em thường gặp: đi tạo ra công thức truy hồi. Đến cách này mình cải tiến để không dùng mảng 4 chiều nữa. Với ai đã biết cơ bản về quy hoạch động thì ta có 4 bước:
Bước 1: Xác định bài toán con
Ở trên có 4 thứ thay đổi: vị trí phần tử đã xét, số phần tử có thể chọn thêm, số mũ 2 đã lấy được và số mũ 5 đã lấy được. Kết quả số số 0 $= \min(cnt2, cnt5)$, chỉ cần có $cnt2$ và $cnt5$ là có kết quả. Vậy ta cố định số phần tử đã xét, số phần tử đã lấy và số mũ 5 lấy được; còn mũ 2 thì ta ăn nhiều nhất có thể:
Định nghĩa
$F[i][j][m]$ $(0 \le i \le n,\ 0 \le j \le k,\ 0 \le m \le max5)$ = số mũ 2 tối đa lấy được khi xét $i$ phần tử đầu, lấy $j$ phần tử, và tích của $j$ phần tử đó có đúng $5^m$ (số mũ 5 lấy được là $m$).
Tại sao $[m]$ là số mũ 5 mà không phải số mũ 2? Có lý do cả đấy: giả sử $n = k = 100$, mảng có 100 số $2^{59}$ (vì $\log_2(10^{18}) \approx 59$, số $\le 10^{18}$ có nhiều mũ 2 nhất là $2^{59}$), thì $max2 = 59 \times 100 = 5900$, mảng sẽ có kích thước $100 \times 100 \times 5900$. Còn với 5 thì mỗi phần tử tối đa $5^{25}$ (vì $\log_5(10^{18}) \approx 25$), $max5 = 100 \times 25 = 2500$, ít hơn một nửa; mảng có kích thước $100 \times 100 \times 2500 = 2.5 \cdot 10^7$, hoàn toàn có thể khai báo toàn cục. Để $[m]$ là số mũ 5 giúp dùng ít bộ nhớ hơn và chạy nhanh hơn. Nên các bạn nhớ luôn $max5 = \lfloor \log_5(10^{18}) \rfloor \times 100$ $= 2500$ nha.
Bước 2: Bài toán cơ sở
Lúc đầu fill (lấp đầy) mảng $= -1$, tức là trường hợp đó không tồn tại. Vì nhỡ đâu $max5$ có thể là 10 nhưng không thể tạo ra trường hợp nào có số mũ 5 bằng 6 thì sao; trường hợp đó gọi là không tồn tại, gán $-1$.
Nếu không chọn phần tử nào ($j = 0$) thì xét bao nhiêu phần tử đi nữa ($i$ từ 0 tới $n$), số mũ 5 lấy được luôn bằng 0 ($m = 0$) và số mũ 2 tối đa cũng bằng 0 → $F[i][0][0] = 0$ với $i$ từ 0 tới $n$. Những trường hợp vô nghĩa như xét $i$ phần tử mà chọn $j > i$ (xét 3 phần tử mà chọn tận 4), hay số mũ 5 không thể đạt được, đều là $-1$, đã fill từ đầu nên không phải lo nữa.
Bước 3: Đáp án của bài toán
Đáp án là số số 0 tối đa khi xét $n$ phần tử và chọn $k$ phần tử, nên phải nằm ở $F[n][k]$. $F[n][k][m]$ là số mũ 2 tối đa khi tích có số mũ 5 đúng bằng $m$, nên số số 0 tạo ra là $\min(m, F[n][k][m])$. Cho $m$ chạy từ 0 tới $max5$:
Đáp án
$res = \max\limits_{0 \le m \le max5} \min(m, F[n][k][m])$
Bước 4: Công thức truy hồi
Không lấy phần tử thứ $i$: $F[i][j][m]$ $= F[i-1][j][m]$.
Có lấy phần tử thứ $i$ (gọi số mũ 2, mũ 5 của nó là $cnt2$, $cnt5$). Chỉ lấy được khi: (1) $m \ge cnt5$ – số mũ 5 lấy được phải $\ge$ số mũ 5 của phần tử $i$; và (2) trạng thái trước đó tồn tại: $m = cnt5 + x$ với $x = m - cnt5$, khi xét $i - 1$ phần tử và chọn $j - 1$ phần tử (vì vừa chọn phần tử $i$ rồi) có số mũ 5 là $x$ phải tồn tại, tức $F[i-1][j-1][m - cnt5] \ne -1$. Khi đó ta được $F[i-1][j-1][m-cnt5]$ $+ cnt2$.
Công thức truy hồi
$F[i][j][m]$ $= F[i-1][j][m]$; nếu $m \ge cnt5$ và $F[i-1][j-1][m-cnt5] \ne -1$ thì $F[i][j][m]$ $= \max(F[i][j][m],\ F[i-1][j-1][m-cnt5] + cnt2)$.
Trước khi xem code, em nhập dãy số và $k$ rồi bấm Tiếp để xem bảng $F$ thay đổi khi lần lượt xét từng phần tử (mỗi bảng là một tầng $F[i]$: hàng là $j$, cột là $m$, ô là số mũ 2 tối đa, ô trống là $-1$):
Ví dụ nhanh:
Source code về ý tưởng trên:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
const int max5 = 2500;
ll a[105];
int f[101][101][max5 + 1];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(&f[0][0][0], &f[100][100][max5 + 1], -1);
for(int i = 0; i <= n; ++i) {
f[i][0][0] = 0;
}
for(int i = 1; i <= n; ++i) {
cin >> a[i];
int cnt2 = countP(a[i], 2), cnt5 = countP(a[i], 5);
for(int j = 1; j <= min(i, k); ++j) {
for(int m = 0; m <= max5; ++m) {
f[i][j][m] = f[i - 1][j][m];
if(m >= cnt5 && f[i - 1][j - 1][m - cnt5] != -1) {
f[i][j][m] = max(f[i][j][m], f[i - 1][j - 1][m - cnt5] + cnt2);
}
}
}
}
int res = 0;
for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[n][k][m]));
cout << res;
return 0;
}
import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
max5 = sum(countP(x, 5) for x in a) # tổng mũ 5 tối đa thật sự (<= 2500)
# Chỉ giữ 2 tầng f[i - 1] (prev) và f[i] (cur) của mảng 3 chiều f[i][j][m]
prev = [[-1] * (max5 + 1) for _ in range(k + 1)]
prev[0][0] = 0 # f[0][0][0] = 0
for i in range(1, n + 1):
cnt2, cnt5 = countP(a[i - 1], 2), countP(a[i - 1], 5)
cur = [row[:] for row in prev] # f[i][j][m] = f[i - 1][j][m] (cur[0][0] = 0 sẵn)
for j in range(1, min(i, k) + 1):
pj, cj = prev[j - 1], cur[j]
for m in range(cnt5, max5 + 1):
if pj[m - cnt5] != -1 and pj[m - cnt5] + cnt2 > cj[m]:
cj[m] = pj[m - cnt5] + cnt2
prev = cur
res = 0
for m in range(max5 + 1):
res = max(res, min(m, prev[k][m]))
print(res)
39for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[n][k][m]));
40cout << res;
41return0;
42}
Giải thích một số chỗ trong code:
fill(&f[0][0][0], &f[100][100][max5 + 1], -1); lấp đầy cả mảng bằng $-1$ (địa chỉ cuối là ngay sau phần tử cuối cùng của mảng).
for $i$ từ 1 tới $n$: $i = 0$ không cần xét vì xét 0 phần tử thì chỉ có $f[0][0][0] = 0$, các $f[0][j][m]$ khác đều $-1$ đã fill từ đầu.
for $j$ từ 1 tới $\min(i, k)$: chỉ được chọn tối đa $k$ phần tử, và xét $i$ phần tử thì không thể chọn quá $i$ phần tử.
for $m$ từ 0 tới $max5$: đi từ không lấy được số mũ 5 nào đến lấy tối đa.
Không gian$O(n \cdot k \cdot max5)$
Thời gian$O(n \cdot k \cdot max5)$
Không gian: mảng $F$ có $100 \times 100 \times 2500 = 2.5 \cdot 10^7$ ô, mảng $a$ không đáng kể. Thời gian: chính là thời gian lấp đầy mảng $F$, $2.5 \cdot 10^7$ phép tính, vẫn nhỏ hơn $10^8$ nên đảm bảo dưới 1 giây. Với cách này ta đã AC bài này rồi. Việc làm mảng bé hơn cũng giúp chương trình tăng tốc độ chạy đáng kể dù độ phức tạp thời gian như nhau, vì khởi tạo gán mảng ít hơn, truy xuất phần tử cũng nhanh hơn.
Cách 4Bỏ chiều i – mảng 2 chiều, chạy ngược
Giờ đến 1 hướng tiếp cận khác: bỏ đi việc xét bao nhiêu phần tử, mảng $F$ chỉ còn 2 chiều $F[j][m]$ $(0 \le j \le k,\ 0 \le m \le max5)$ = số mũ 2 tối đa lấy được nếu chọn $j$ phần tử và số mũ 5 lấy được là $m$. Để tránh trường hợp một phần tử đang xét bị dùng lặp đi lặp lại thì ta cho cả 2 vòng for chạy ngược. Trước đó for(j) và for(m) là thế này:
$j$ chạy ngược từ $\min(i, k)$ về 1; $m$ chạy ngược từ $max5$ về $cnt5$. Vì đã loại bỏ $[i]$ nên không còn công thức $F[i][j][m]$ $= F[i-1][j][m]$ nữa (giá trị cũ cứ nằm yên trong ô đó chính là trường hợp "không lấy"), ta chỉ còn quan tâm công thức dưới. Mà điều kiện vào được công thức dưới là $m \ge cnt5$, nên cho $m$ chạy từ $max5$ ngược về $cnt5$ thì đỡ phải kiểm tra điều kiện đó.
Chạy xuôi m (sai)
Xét phần tử $cnt5 = 1, cnt2 = 1$. Tính $F[1][1]$ từ $F[0][0]$, rồi lúc tới $m = 2$ lại đọc $F[1][1]$ vừa được cập nhật bởi chính phần tử này → coi như lấy nó 2 lần.
Chạy ngược m, j (đúng)
Ô $F[j-1][m-cnt5]$ nằm ở hàng nhỏ hơn và cột nhỏ hơn, chạy ngược thì nó chưa bị cập nhật ở lượt phần tử $i$ → vẫn là giá trị của $i-1$ phần tử đầu.
Công thức truy hồi: $F[j][m]$ $= \max(F[j][m],\ F[j-1][m-cnt5] + cnt2)$ khi $F[j-1][m-cnt5] \ne -1$. Vòng for $i$ bên ngoài chạy từ đầu mảng đến cuối mảng đã ngầm định là ta đã xét bao nhiêu phần tử rồi. Trường hợp cơ sở cũng chỉ còn $F[0][0] = 0$ (vẫn fill cả mảng bằng $-1$ trước). Đáp án: $res = \max(res, \min(m, F[k][m]))$ với $m$ chạy từ 0 tới $max5$.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int countP(ll n, ll p) {
int cnt = 0;
while(n % p == 0) {
cnt++;
n /= p;
}
return cnt;
}
const int max5 = 2500;
ll a[105];
int f[101][max5 + 1];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
fill(&f[0][0], &f[100][max5 + 1], -1);
f[0][0] = 0;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
int cnt2 = countP(a[i], 2), cnt5 = countP(a[i], 5);
for(int j = min(i, k); j >= 1; --j) {
for(int m = max5; m >= cnt5; --m) {
if(f[j - 1][m - cnt5] != -1) {
f[j][m] = max(f[j][m], f[j - 1][m - cnt5] + cnt2);
}
}
}
}
int res = 0;
for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[k][m]));
cout << res;
return 0;
}
import sys
def countP(n, p):
cnt = 0
while n % p == 0:
cnt += 1
n //= p
return cnt
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
NEG = -10**9 # thay cho -1 (không tồn tại), cộng thêm vẫn âm
f = [[NEG] * 2501 for _ in range(k + 1)]
f[0][0] = 0
tot5 = 0 # tổng mũ 5 của các phần tử đã xét
for i in range(1, n + 1):
cnt2, cnt5 = countP(a[i - 1], 2), countP(a[i - 1], 5)
tot5 += cnt5
for j in range(min(i, k), 0, -1): # chạy ngược j
src, dst = f[j - 1], f[j]
# m chạy từ cnt5 tới tot5 (lớn hơn tot5 thì chắc chắn không tồn tại)
new = [y + cnt2 for y in src[0:tot5 - cnt5 + 1]]
dst[cnt5:tot5 + 1] = [x if x >= y else y for x, y in zip(dst[cnt5:tot5 + 1], new)]
res = 0
for m in range(tot5 + 1):
res = max(res, min(m, f[k][m]))
print(res)
C++▶ Chạy tay từng dòng codeCách 4: bỏ chiều i, f[j][m] với j, m chạy ngược, bộ nhớ O(K·max5).
36for(int m = 0; m <= max5; ++m) res = max(res, min(m, f[k][m]));
37cout << res;
38return0;
39}
Không gian$O(k \cdot max5)$
Thời gian$O(n \cdot k \cdot max5)$
Với cách này thời gian chạy đã nhanh hơn và dùng ít bộ nhớ hơn ($100 \times 2500 = 2.5 \cdot 10^5$ ô). Tuy nhiên không phải bài nào cũng áp dụng được cách trên nha; thường anh em ra đến cách DP bottom-up (Cách 3) mà AC là ok rồi, cách đó dễ hiểu hơn nhiều. Còn Cách 4 thì tuỳ từng bài mới áp dụng được thôi.
Cách
Ý tưởng
Bộ nhớ (xấu nhất)
Thời gian
Kết quả
1
Đệ quy chọn / không chọn
$O(n)$
$O(2^n)$
60/100 (TLE)
2
Đệ quy có nhớ 4 chiều
$3.24 \cdot 10^{10}$ ô
–
60/100 (MLE)
3
QHĐ bottom-up $F[i][j][m]$
$2.5 \cdot 10^{7}$ ô
$O(n \cdot k \cdot max5)$
AC
4
QHĐ $F[j][m]$ chạy ngược
$2.5 \cdot 10^{5}$ ô
$O(n \cdot k \cdot max5)$
AC, nhanh hơn
Ghi chú của mình: 4 code C++ ở trên là của anh, các bản Python là mình viết thêm. Tất cả (C++ và Python) đã được kiểm tra với 220 bộ test ngẫu nhiên $n \le 11$, so với cách vét cạn nhân thật mọi tổ hợp $k$ số bằng số nguyên lớn rồi đếm số 0 – khớp hết; Cách 3 và Cách 4 còn được so với nhau trên 30 bộ $n = 100$. Đo thời gian: với $n = 20$, Cách 1 C++ khoảng 0.006 giây, Cách 2 khoảng 0.013 giây; với $n = k = 100$ (toàn $5^{25}$ và $2^{59}$), Cách 3 C++ khoảng 0.07 giây, Cách 4 khoảng 0.01 giây; bản Python Cách 3 khoảng 0.65 giây, Cách 4 khoảng 0.5 giây. Python Cách 3 chỉ giữ 2 tầng $F[i-1]$, $F[i]$ và Python Cách 4 chỉ chạy $m$ tới tổng mũ 5 thực tế để đỡ chậm. Cách 2 với $n = k = 100$ thì đúng như phân tích là không đủ bộ nhớ.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
