"live" editorial cho contest TLEoj thảm nhất: TLEoj Contest #09 (2) - F (+3 nhận xét đầu của bài G)

Channel:

Lib

Subscribers:

120

Published on October 9, 2023 5:17:37 AM ● Video Link: https://www.youtube.com/watch?v=qrFX1O3sKjE

Game:

Counter-Strike: Source (2004)

Duration: 1:50:26

47 views

0

bài không shitty lắm nữa.
====
Tóm tắt:
- F (tính số cặp số):
+ Sử dụng sàng O(N) để tìm ước lớn nhất của mọi i từ 1 đến N mà không chia hết cho bất kì 1 SCP khác 1 nào. Gọi ước đấy là id(i). Tống nó vào các nhóm có id bằng nhau. kết quả là số cách chọn ra 2 số nguyên dương phân biệt nhỏ hơn hoặc bằng n trừ đi số cặp số phân biệt cùng nhóm
- F (xử lí truy vấn)
+ tham lam để chọn ra C nhóm chứa C thành phố quan trọng và K-C nhóm chưa được chọn và chứa nhiều thành phố nhất
+ dp knapsack để tìm ra số thành phố lớn nhất có thể của bên chứa ít thành phố hơn.
+ đặt sum = số thành phố trong các nhóm ta chọn, minside là số thành phố trong bên ít thành phố hơn. khi đó ans=minside*2 + (1 nếu minside*2==sum)
- Ý tưởng F: Bài 2 đề DHBB lớp 10 2020 + 1 hình vẽ tồn tại trên bảng gần 3 năm (trước khi nó bị xóa đi vào t4 tuần trước) + phần DP knapsack để tính chênh lệch min trong bài Orientation của POI 2005

- G (3 nhận xét đầu):
+ Gọi DistA[i] và DistB[i] lần lượt là khoảng cách từ tiệm bánh i đến 2 đỉnh A và B. Thời gian tối thiểu để mua bánh ở tiệm i 1 lần là min(DistA[i],DistB[i]), để mua bánh ở tiệm i 2 lần là max(DistA[i],DistB[i])
+ Tồn tại 1 phương án mua bánh tối ưu mà trong đó, nếu 1 tiệm bánh được thăm 2 lần, 2 lần thăm đó sẽ là liên tiếp
+ Gọi V0, V1,V2 lần lượt là tập hợp các tiệm bánh được đi thăm ít nhất 0,1,2 lần. Khi đó, tất cả các đỉnh cùng thuộc 1 trong 3 tập V0,V1,V2 đều thuộc 1 thành phần liên thông

(btw, bài + tests + sol (mõm) + code mẫu ) : https://drive.google.com/drive/u/0/folders/1voqXa4lE5jQthBek-KhX8jJzW7Yo-A9q (bỏ b,c,d đi pls)

Other Statistics