02/02/2024
Bài này mình sưu tầm của . Chúc các bạn học tốt và gặt hái nhiều thành công. Các bạn có thể vào link này nhé: https://hnoj.edu.vn/contest/prehnoi2023.
"anh ơi bài xây hàng rào này em đọc mãi k hiểu test ví dụ 1 tính như nào ra 15 anh giải thích giúp em đc k ạ"
---------------------
Bài đó tóm lại là thế này, (a[i], b[i]) là 1 thằng nhé, thì hãy chọn ra 1 thằng ở mảng b, và k-1 thằng ở mảng a, sao cho tổng tụi nó là lớn nhất và các chỉ số index phân biệt nhau
Ví dụ test đó, Tính index từ 1 cho dễ nhé. Thì khi k = 3, Chọn thằng b[2] và a[1], a[3]. Nên là: 8 + 3 + 4 = 15.
Tóm lại là: Trong mảng b chọn 1 thằng, và trong mảng a chọn k-1 thằng, tất cả index đều phải phân biệt nhau, chọn sao cho tổng là lớn nhất
---------------------
"s k chọn là 8 + 5 + 4 mà là 3 vs 4 ạ"
---------------------
Nếu chọn thằng 5 ở mảng a thì đó là index 2, trong khi ta đã chọn index 2 ở mảng b rồi mà em, không được trùng. Số 8 đã chọn là index 2 ở mảng b rồi. Em hiểu không? Nếu đã chọn b[2] thì sẽ không được chọn a[2] và ngược lại
---------------------
"e đọc e chỉ hiểu là ngta chọn ra k-1 tấm a và 1 tấm b chứ e không thấy nó phải né vị trí nhau"
---------------------
Em đọc kỹ đề bài khúc đầu tiên nó có nói câu này: tấm gỗ thứ i sẽ có độ đẹp là Ai hoặc Bi. Có nghĩa là (a[i], b[i]) là 1 lựa chọn. Ví dụ nếu chọn index 1 Thì nó chỉ có thể là a[1] hoặc b[1] Chứ không thể cùng cả 2 Vì tụi nó chỉ là 1 lựa chọn thôi
---------------------
"à vâng v em hiểu r ạ. anh gợi ý đi anh ơi"
---------------------
Bài này dùng tư tưởng tham lam (Greedy) để giải quyết. Kể cả bạn nào có không biết về tư tưởng tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết. Cho bạn nào không biết thì mình có thể nói nhanh như thế này: Tham lam ở đây nghĩa là ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách giải quyết tốt nhất đó nếu lại đứng trước nhiều lựa chọn cách giải quyết khác nhau nữa thì ta lại cố gắng chọn theo cách giải quyết tốt nhất trong số đó tóm lại cứ tốt nhất mà triển vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ còn lại không có công thức từng bước cụ thể giải quyết như mấy thuật toán khác. Mà ta có thể giải quyết theo cách bất kỳ miễn cái tư tưởng mà ta giải quyết luôn là chọn theo hướng tốt nhất trong các lựa chọn thì đó chính là tư tưởng của tham lam
Anh nói em thế này: Mọi bài nếu chưa nhìn ra thuật ăn full 100% của nó thì trước tiên hãy làm theo cách VÉT CẠN để ăn thử trước 1 số subtask và cũng để kiểm chứng ý tưởng VÉT CẠN đó có đúng không? Rồi khi thấy nó đúng rồi (Tức là ăn hết được 1 số subtask nhỏ và bị TLE với các subtask lớn, tuyệt đối không có bị WA mà chỉ bị TLE) thì lúc này nhìn vào code vét cạn đó mà cải tiến lên để ăn full
Như bài xây hàng rào đó, code vét cạn có thể ăn được subtask 2, 3 tức là 50% số điểm. Từ đó code thêm 1 chút của trường hợp đặc biệt là subtask 1 tức là ăn được 75% điểm. Còn subtask 4 thì mới là khó nhất. Nhưng nếu đi thi ăn được 75% điểm cũng tốt rồi.
Giờ em thử ăn 75% điểm = vét cạn cho anh xem. Tất nhiên nói là vét cạn nhưng tư tưởng của nó cũng vẫn phải THAM LAM nha
---------------------
"anh ơi thật sự là bài xây hàng rào em k bt phải vét cạn nnao nữa :)) anh gợi ý j đi ạ"
---------------------
gợi ý thôi nhé 😉 chọn 1 phần tử ở mảng b, và chọn k-1 phần tử ở mảng a thì k có thể lớn lắm với k a[9].second) + a[10].first
a[10].second + a[9].first
Chọn Max của tất cả các thằng trên thì đó là đáp án
---------------------
K = 3
max(a[1].second -> a[8].second) + a[10].first + a[9].first
a[10].second + a[9].first + a[8].first
a[9].second + a[10].first + a[8].first
Chọn Max của tất cả các thằng trên thì đó là đáp án
---------------------
K = 4:
max(a[1].second -> a[7].second) + a[10].first + a[9].first + a[8].first
a[10].second + a[9].first + a[8].first + a[7].first
a[9].second + a[10].first + a[8].first + a[7].first
a[8].second + a[10].first + a[9].first + a[7].first
Chọn Max của tất cả các thằng trên thì đó là đáp án
---------------------
đó thì với tư tưởng tham lam này dễ thấy với mỗi trường hợp K ta sẽ xét qua hết N phần tử là ra đáp án, và sẽ có Q câu hỏi như vậy. Vậy có thể thấy cách làm vét cạn trước mắt sẽ có độ phức tạp: O(Q * N) mà Q, N tối đa 10^5 nên Q * N = 10^10 thì chắc chắn TLE vì đã vượt quá ngưỡng giới hạn 1 giây là 10^8 rồi (bị vượt quá cả 100 lần). Nên chỉ ăn được 3 subtask đầu tiên, ăn được subtask 1, 2, 3 nhé, tức là 75% điểm
Subtask 1: Q = 1 => O(Q * N) = 1 * N = N mà N tối đa 10^5 nên sẽ là 10^5
Subtask 2: 1 n >> q;
vector a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first;
}
for(int i = 0; i < n; ++i){
cin >> a[i].second;
}
sort(a.begin(), a.end());
while(q--){
long long k;
cin >> k;
k = n - k;
long long sum = 0;
for(int i = k + 1; i < n; ++i){
sum += a[i].first;
}
long long Max = a[0].second;
for(int i = 1; i a[10].first)
sum(a[9].first -> a[10].first) - a[10].first + a[10].second
============
K = 3: Lấy Max của các thằng sau:
max(a[1].second -> a[8].second) + sum(a[9].first -> a[10].first)
sum(a[8].first -> a[10].first) - a[10].first + a[10].second
sum(a[8].first -> a[10].first) - a[9].first + a[9].second
============
K = 4: Lấy Max của các thằng sau:
max(a[1].second -> a[7].second) + sum(a[8].first -> a[10].first)
sum(a[7].first -> a[10].first) - a[10].first + a[10].second
sum(a[7].first -> a[10].first) - a[9].first + a[9].second
sum(a[7].first -> a[10].first) - a[8].first + a[8].second
Hãy nhìn cách từ K = 2 nó chuyển qua K = 3, từ K = 3 chuyển qua K = 4.
Hãy xem tấm hình sau (Lưu ý: tấm hình được đính kèm ở comment dưới bài viết có chữ "Hình 1" nhé)
anh đánh dấu 3 màu: đỏ, cam, vàng
ở K = 2 thì chỉ có đỏ, cam không có vàng
còn từ K = 3 trở lên là có đủ 3 màu
em hãy nhìn những khối cùng màu trong các trường hợp K
ví dụ từ khối màu cam của K = 2 đi qua khối màu cam của K = 3 rồi đi qua khối màu cam của K = 4
ví dụ từ khối màu vàng của K = 3 đi qua khối màu vàng của K = 4
anh nghĩ em sẽ nhìn ra thứ gì đó 😉 để giải đáp được câu hỏi: Làm sao chỉ 1 vòng for chạy từ 1 đến N là tính ra được hết các đáp án ứng với K từ 1 đến N
em nhìn nhé, giả sử n = 10 mảng đang sort tăng dần theo first và k = 5
nhìn hình này cho dễ hình dung (Lưu ý: tấm hình được đính kèm ở comment dưới bài viết có chữ "Hình 2" nhé)
khi k = 5 nghĩa là hiểu rằng sẽ cần lấy 1 cái từ second và 4 cái từ first, như thế ở trường hợp 1: Sẽ lấy 4 cái first to nhất (vì đang sắp tăng dần nên 4 thằng cuối cùng sẽ là 4 thằng to nhất), lấy 4 cái to nhất là anh đã in vàng đó, còn lại các thằng second được tô xanh thì sẽ lấy thằng có giá trị lớn nhất trong đó
trường hợp 2: Bắt đầu second sẽ lấy vào lần lượt các vị trí của 4 thằng first tô vàng ở trường hợp 1, thì như thế khi second lấy vào vị trí thằng tô vàng nào thì thằng tô vàng đó sẽ dịch xuống 1 vị trí, như em nhìn TH2 thì thằng second lấy vào vị trí 7, thì thằng first ở vị trí 7 sẽ bỏ đi và ta lấy first ở vị trí 6. Như em nhìn TH3 thì thằng second lấy vào vị trí 8, thì thằng first ở vị trí 8 sẽ bỏ đi và ta lấy first ở vị trí 6, 7. như thế em có thể thấy là từ trường hợp 2 trở đi, tức là các trường hợp 2, 3, 4, 5 thì first sẽ cứ lấy tổng từ vị trí 6 đến 10, sau đó giả lập second lấy từng vị trí 7, 8, 9, 10 thì trừ đi first ở vị trí tương ứng đó:
TH2: sum(first từ a[6] đến a[10]) + a[7].second - a[7].first
TH3: sum(first từ a[6] đến a[10]) + a[8].second - a[8].first
TH4: sum(first từ a[6] đến a[10]) + a[9].second - a[9].first
TH5: sum(first từ a[6] đến a[10]) + a[10].second - a[10].first
nhìn hình sẽ dễ tưởng tượng hơn, rồi thì sẽ lấy Max của 5 trường hợp trên thì đó là đáp án
đó thì như thế với mỗi giá trị K em sẽ chỉ cần xét qua N phần tử là có kết quả rồi, em hãy thử nhìn kỹ lại rồi code lại xem, còn nếu vẫn không được thì anh sẽ nói luôn tư tưởng cho em nhé rồi em thử code, nếu vẫn không được anh sẽ cho em tham khảo code hen, có gì nhắn lại anh hen.
---------------------
"chắc anh nói giúp em tư tưởng với em k ra anh ạ :))"
---------------------
Đầu tiên em cần tạo ra mảng 1 chiều MaxSecond lưu trữ các giá trị của second sao cho MaxSecond[i] = giá trị second lớn nhất của a[1], a[2], ... a[i] (tức là giá trị lớn nhất của các phần tử second từ đầu đến vị trí i đó)
=> Chỉ cần O(N) là tạo ra được mảng Max này.
--------------------
Tiếp đó em cần tạo ra mảng 1 chiều SumFirst lưu trữ các giá trị sao cho SumFirst[i] = tổng các giá trị first từ vị trí i đến cuối mảng, tức là: SumFirst[i] = a[i] + a[i+1] + ... + a[n]
=> Chỉ cần O(N) là tạo ra được mảng Sum này.
--------------------
Hãy nhìn lại tấm hình "Hình 1"
Với màu đỏ:
với K = 2 thì nó sẽ là: MaxSecond[9] + SumFirst[10].
Với K = 3 thì nó sẽ là: MaxSecond[8] + SumFirst[9].
Với K = 4 thì nó sẽ là: MaxSecond[7] + SumFirst[8].
Em có thấy cứ mỗi cái K tăng lên 1 thì index của 2 thằng MaxSecond, SumFirst bị giảm đi 1 so với trước đó không?
Với K = 2 thì 2 index truyền vào là 9, 10.
Với K = 3 thì 2 index truyền vào là: 8, 9.
Với K = 4 thì 2 index truyền vào là: 7, 8.
-------------------
Với màu cam:
K = 2 thì nó là: SumFirst[9] - a[10].first + a[10].second
K = 3 thì nó là: SumFirst[8] - a[10].first + a[10].second => Tức là lúc này nó chính là trường hợp K = 2 nhưng có cộng thêm a[8].first
K = 4 thì nó là:
SumFirst[7] - a[10].first + a[10].second => Tức là lúc này nó chính là trường hợp K = 3 nhưng có cộng thêm a[7].first
Và riêng trường hợp K = 4 này thì có thêm 1 cái nữa là: SumFirst[7] - a[9].first + a[9].second. Tức là vẫn là SumFirst[7] đó nhưng giờ sẽ trừ cho index giảm đi 1 so với trước đó (trước đó là trừ cho a[10].first và cộng cho a[10].second) còn giờ là trừ cho a[9].first và cộng cho a[9].second.
---------------------
Còn với màu vàng:
K = 2 thì nó không có, nhưng kể từ K = 3 thì nó có, cụ thể như sau:
K = 3: SumFirst[8] - a[9].first + a[9].second
qua K = 4 thì nó là: SumFirst[7] - a[8].first + a[8].second. Em có thấy nó chỉ lùi lại 1 index so với trường hợp màu vàng của K = 3 không? K = 3 thì gọi SumFirst[8] còn K = 4 thì gọi SumFirst[7], và K = 3 thì trừ cho a[9].first + a[9].second còn qua K = 4 thì trừ cho a[8].first + a[8].second
------------------------
Đó thì em nhìn ra những điểm tương đồng của nó thì từ đó ở mỗi thằng em tính ra 3 cái Max (Max1, Max2, Max3) ứng với Max của màu đỏ, cam, vàng rồi khi đi qua trường hợp K tiếp theo thì dựa trên 3 biến Max1, Max2, Max3 của trường hợp trước đó mà sinh ra thêm cái mới rồi lại so sánh cập nhật lại 3 biến => 1 for chạy từ 1 đến N là đủ rồi.
Anh chỉ ra đến đây là rõ lắm rồi, nếu vẫn không được nữa thì anh sẽ cho em tham khảo code của anh theo đúng những gì anh đã phân tích ở đây nhé
---------------------
"anh ơi nhưng mà cái màu cam k càng đi lên nó càng nhiều em đang k hình dung đc phải xử lí nnao"
---------------------
Ok vậy chắc anh nghĩ anh sẽ đưa luôn cho em xem nhé: Đây là code của anh theo đúng ý tưởng đã nói đó, đã nộp AC trên web:
using namespace std;
int main(){
freopen("xayhangrao.inp", "r", stdin);
freopen("xayhangrao.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, q;
cin >> n >> q;
vector a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first;
}
for(int i = 0; i < n; ++i){
cin >> a[i].second;
}
sort(a.begin(), a.end());
vector MaxSecond(n);
MaxSecond[0] = a[0].second;
for(int i = 1; i < n; ++i){
MaxSecond[i] = max(MaxSecond[i - 1], a[i].second);
}
vector sumFirst(n);
sumFirst[n - 1] = a[n - 1].first;
for(int i = n - 2; i >= 0; --i){
sumFirst[i] = sumFirst[i + 1] + a[i].first;
}
unordered_map ump;
ump[1] = MaxSecond[n - 1];
if(n >= 2){
long long Max1 = MaxSecond[n - 2] + sumFirst[n - 1];
long long Max2 = sumFirst[n - 2] - a[n - 1].first + a[n - 1].second;
ump[2] = max(Max1, Max2);
int j = 0;
for(int k = 3; k > x;
cout
02/02/2024