Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án)

Nội dung text: Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án)

1. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn đếm số lượng số trong phạm vi [퐿, ] mà 푖 ⊕ 푖+1 ⊕ ⊕ 푗 = ⊕ +1 ⊕ ⊕ 푡 = 0; và không chứa hai chữ số nào cạnh nhau có tổng chia hết cho 5. Ta có thể giải quyết bằng quy hoạch động chữ số, cài đặt bằng đệ quy và sử dụng mảng nhớ. Độ phức tạp: × log5 ( ) , với hằng số thuật toán là 16 × 16 × 5 × 10. - Subtask 6: 퐿 là luỹ thừa của 10 và = 10 × 퐿 ―1 và = 2. Với ràng buộc này, các số đều có số chữ số bằng nhau và có thể bỏ qua ràng buộc về phạm vi của . Sử dụng cách đếm ở subtask 2 ; nhưng các số 푖,푗, ,푡 có thể xây dựng bằng đệ quy thay vì vòng lặp (tương tự như cách xây dựng số ). Cấu hình cần đếm chính là bộ ba ( , , ) trong đó = 1, 2, , 푛 là một dãy các chữ số thập phân; = 1, 2, , 푛 là một dãy nhị phân có các bit 1 nằm kề nhau; = 1, 2, , 푛 là một dãy nhị phân có các bit 1 nằm kề nhau; sao cho các chữ số của lấy tại các vị trí bit 1 của có xor bằng 0 và các chữ số của lấy tại các vị trí bit 1 của có xor bằng 0. Có thể đếm số cấu hình như vậy bằng cách đệ quy xây dựng từng vị trí của cả ba số ( , , ) cùng một lúc; sau đó sử dụng mảng nhớ để khử trùng lặp các bài toán. Để xử lý cho nhiều trường hợp thử nghiệm cùng một lúc, có thể cho phép số có chữ số 0 đứng đầu. Độ phức tạp phần tiền xử lý: (log ( )) với hằng số thuật toán là 16 × 16 × 5 × 40. Độ phức tạp phần trả lời các trường hợp test: ( ), với là tổng số chữ số của tất cả các số 퐿 và trong các trường hợp test. - Subtask 7: Không có ràng buộc nào thêm. Với = 2, sử dụng cách đếm tương tự như subtask 6 nhưng xử lý thêm ràng buộc về phạm vi của . Để đếm số cấu hình bé hơn , ta có thể xét 푖 là vị trí đầu tiên mà 푖 < 푖, và xét hết các khả năng các số , có thể có tính đến 푖. Mặc dù số khả năng của và lớn, nhưng giá trị xor của các chữ số tương ứng là bé hơn 16 ; do đó có thể xét các khả năng của các giá trị xor này, qua 162 trường hợp. Độ phức tạp phần tiền xử lý: (log ( )) với hằng số thuật toán là 16 × 16 × 5 × 40. Độ phức tạp phần trả lời các trường hợp test: ( ), với hằng số thuật toán là 16 × 16 × 40 và là tổng số chữ số của tất cả các số 퐿 và trong các trường hợp test. DeThi.edu.vn
2. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn ĐỀ SỐ 2 BỘ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT - NĂM HỌC 2024-2025 ĐỀ CHÍNH THỨC Môn: TIN HỌC Thời gian: 180 phút (Không kể thời gian giao đề) TỔNG QUAN ĐỀ THI Tiêu đề File chương trình File dữ liệu File kết quả Bài 4 Vòng tròn CYCLE.* CYCLE.INP CYCLE.OUT Bài 5 Hai dãy số TSEQ.* TSEQ.INP TSEQ.OUT Bài 6 Mã hoá dãy số ENCODE.* ENCODE.INP ENCODE.OUT Dấu * được thay thế bởi PAS hoặc CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal hoặc + + hoặc Python. - Mỗi bài bao gồm nhiều subtask, mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn. Hãy lâp trình giải các bài toán sau: Bài 4: Vòng tròn (7,0 điểm) Một trường THPT chuyên đang tổ chức trò chơi tập thể cho học sinh lớp chuyên Toán đánh số từ 1 đến và 퐿 học sinh lớp chuyên Văn đánh số từ 1 đến 퐿. Trên sân, có vị trí cách đều nhau đã được đánh dấu sẵn, các vị trí được đánh số từ 1 đến tạo thành một vòng tròn: - Vị trí thứ 1 kề với vị trí thứ 2 và thứ ; - Vị trí thứ 푖(2 ≤ 푖 ≤ ―1) kề với vị trí thứ 푖 ―1 và thứ 푖 +1; - Vị trí thứ kề với vị trí thứ ―1 và thứ 1. Hình vẽ dưới đây minh hoạ vòng tròn trên sân có 12 vị trí: Ban đầu, + 퐿 học sinh đứng ở các vị trí sao cho không có 2 học sinh nào đứng cùng một vị trí. Học sinh thứ của lớp chuyên Toán đứng ở vị trí 푃 (1 ≤ ≤ ), học sinh thứ 푣 của lớp chuyên Văn đứng ở vị trí 푄푣(1 ≤ 푣 ≤ 퐿). Mỗi bước, học sinh có thể di chuyển sang một DeThi.edu.vn
3. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn trong 2 vị trí kề với vị trí đang đứng. Lưu ý, trong quá trình di chuyển, một vị trí có thể có nhiều hơn một học sinh. Các thầy cô muốn xác định vị trí tập trung của từng bạn sao cho: - Vị trí tập trung của học sinh lớp chuyên Toán là vị trí liên tiếp ở trên vòng tròn; - Vị trí tập trung của 퐿 học sinh lớp chuyên Văn là 퐿 vị trí liên tiếp trên vòng tròn; - Không có 2 học sinh nào đứng cùng một vị trí. Yêu cầu: Hãy giúp các thầy cô xác định vị trí tập trung của các học sinh sao cho tổng số bước phải di chuyển của tất cả các học sinh là nhỏ nhất. Dữ liệu: Vào từ file văn bản CYCLE.INP: Dòng đầu chứa một số nguyên là số lượng trường hợp test (1 ≤ ≤ 105). Tiếp theo là nhóm dòng, mỗi nhóm dòng mô tả một trường hợp test như sau: - Dòng thứ nhất chứa 3 số nguyên dương , và 퐿(2 ≤ + 퐿 ≤ ≤ 105). - Dòng thứ hai chứa số nguyên dương 푃1,푃2, ,푃 (1 ≤ 푃1,푃2, ,푃 ≤ ). - Dòng thứ ba chứa 퐿 số nguyên dương 푄1,푄2, ,푄퐿(1 ≤ 푄1,푄2, ,푄퐿 ≤ ). Dữ liệu bảo đảm tổng các số trong một file dữ liệu vào không vượt quá 2 × 105. Các số trên cùng một dòng cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản CYCLE.OUT: - Gồm dòng, mỗi dòng chứa một số nguyên duy nhất là tổng số bước di chuyển nhỏ nhất của tất cả các học sinh tương ứng với trường hợp test trong dữ liệu vào. Ví dụ: CYCLE.INP CYCLE.OUT 1 15 12 6 4 1 3 5 7 9 11 2 12 8 4 Giải thích - Trong phương án 1, số bước di chuyển của các học sinh chuyên Văn lần lượt là: 1,2,3,0; số bước di chuyển của các học sinh chuyên Toán lần lượt là: 2,3,2,1,0,1. DeThi.edu.vn
4. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn - Trong phương án 2, số bước di chuyển của các học sinh chuyên Văn lần lượt là: 0,1,4,1; số bước di chuyển của các học sinh chuyên Toán lần lượt là: 2,3,2,1,0,1. - Cả 2 phương án đều tối ưu và đều có tổng số bước là 15. Chấm điểm - Subtask 1 (10% số điểm): ≤ 10; ≤ 10. - Subtask 2 (15% số điểm): ; . ≤ 500;1 ≤ 푃1,푃2, ,푃 < 2;1 ≤ 푄1,푄2, ,푄퐿 < 2 ≤ 10 - Subtask 3 (15% số điểm): ; . ≤ 5000;1 ≤ 푃1,푃2, ,푃 < 2;1 ≤ 푄1,푄2 ,푄퐿 < 2 ≤ 10 - Subtask 4 (20% số điểm): ≤ 5000; ≤ 10. - Subtask 5 (20% số điểm): . 1 ≤ 푃1,푃2, ,푃 < 2;1 ≤ 푄1,푄2, ,푄퐿 < 2; ≤ 10 - Subtask 6 (20% số điểm): Không có ràng buộc nào thêm. Bài 5: Hai dãy số (7,0 điểm) Với niềm đam mê về các bài toán trên dãy số của mình, hôm nay thầy giáo Lê nghiên cứu bài toán trên hai dãy số A và B. Dãy A gồm các số tự nhiên sắp xếp tăng dần từ 1 tới 109. Dãy B chỉ gồm duy nhất một số 0. Thầy Lê lần lượt đưa ra Q yêu cầu, mỗi yêu cầu thuộc một trong 3 loại sau: - Loại 1: Cho hai số X và K, yêu cầu cắt K số đầu tiên của dãy A, ghép vào ngay sau số có giá trị X của dãy B; - Loại 2: Cho hai số Y và H, yêu cầu xóa đi H số ngay sau số có giá trị Y của dãy B; - Loại 3: Cho hai số L và R, yêu cầu tính tổng của các số từ vị trí L đến vị trí R của dãy B. Vị trí các phần tử trong dãy B được đánh số từ 1. Yêu cầu: Hãy thực hiện các yêu cầu đó theo đúng thứ tự mà thầy Lê đưa ra. Dữ liệu: Vào từ file văn bản TSEQ.INP: - Dòng đầu chứa một số nguyên 푄 là số lượng yêu cầu thầy Lê cần thực hiện (1 ≤ 푄 ≤ 5 × 105). - Mỗi dòng trong số 푄 dòng tiếp theo chứa ba số nguyên mô tả một trong ba loại yêu cầu theo định dạng sau: - 1 XK mô tả yêu cầu loại 1(0 ≤ ≤ 109;1 ≤ 퐾 ≤ 109). Dữ liệu bảo đảm tổng 퐾 của tất cả các yêu cầu 1 không quá 109 và giá trị X hiện đang có trong dãy ; - 2 Y H mô tả yêu cầu loại 2(0 ≤ 푌 ≤ 109;1 ≤ ≤ 109). Dữ liệu bảo đảm có ít nhất số sau giá trị 푌 và giá trị 푌 hiện đang có trong dãy ; - 3 L R mô tả yêu cầu loại 3(1 ≤ 퐿 ≤ 푅 ≤ | |, với | | là số lượng phần tử hiện tại của dãy ). Các số trên cùng một dòng cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản TSEQ.OUT: DeThi.edu.vn
5. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn - Với mỗi yêu cầu loại 3, ghi ra trên một dòng một số nguyên là đáp án tính được. Ví dụ TSEQ.INP TSEQ.OUT 6 11 1 0 3 35 1 1 2 3 3 5 2 4 2 1 4 4 3 2 7 Giải thích Yêu cầu Dãy B Giải thích Ban đầu [0] 1 [0, 1, 2, 3] 2 [0, 1, 4, 5, 2, 3] 3 [0, 1, 4, 5, 2, 3] Các số từ vị trí 3 đến 5 là [4,5,2] có tổng là 11 4 [0, 1, 4, 3] 5 [0, 1, 4, 6, 7, 8, 9, 3] 6 [0,1,4,6,7,8,9,3] Các số từ vị trí 2 đến 7 là [ 1,4,6,7,8,9] có tổng là 35 Chấm điểm: - Subtask 1 (15% số điểm): 푄,퐾 ≤ 500. - Subtask 2 (15% số điểm): 푄 ≤ 5000. - Subtask 3 (20% số điểm): Không có yêu cầu loại 2; Các yêu cầu loại 1 xuất hiện trước tất cả các yêu cầu loại 3 . - Subtask 4 (25% số điểm): Không có yêu cầu loại 2. - Subtask 5 (25% số điểm): Không có ràng buộc nào thêm. Bài 6: Mã hoá dãy số (6,0 điểm) Ngày nay, lĩnh vực an ninh mạng đang dần trở thành một lĩnh vực thiết yếu trong việc bảo mật an toàn thông tin trên toàn thế giới. Tuấn là một kỹ sư an ninh mạng và rất đam mê khám phá các bài toán về mã hoá bảo mật. Cậu đang quan tâm đến bài toán mã hoá một dãy số 푆 = (푆1,푆2, ,푆 ) với các phần tử là các số nguyên dương không quá 퐾. Cậu thử nghiệm việc mã hoá bằng cách viết ra tất cả các dãy hậu tố của dãy 푆. Cụ thể, với mỗi 푖 ∈ {1,2, , }, Tuấn viết ra dãy 푖 = (푆푖,푆푖+1, ,푆 ). Sau đó, cậu sấp xếp các dãy này tăng dần theo thứ tự từ điển. Cuối cùng, cậu ghi lại độ dài của các dãy theo thứ tự đã sắp xếp, thu được dãy DeThi.edu.vn
6. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn 퐿 = (퐿1,퐿2, ,퐿 ) và gọi đây là dãy đặc trưng của 푆. Ví dụ, với dãy 푆 = (2,1,4,3,1,3,4) thì Tuấn sẽ viết ra 7 dãy: 1 = (2,1,4,3,1,3,4); 2 = (1,4,3,1,3,4); 3 = (4,3,1,3,4); 4 = (3,1,3,4); 5 = (1,3,4); 6 = (3,4); 7 = (4). Sau khi sắp xếp tăng dần theo thứ tự từ điển, Tuấn thu được: ( 5, 2, 1, 4, 6, 7, 3). Cuối cùng, Tuấn ghi lại độ dài các dãy theo thứ tự đó và thu được dãy đặc trưng của 푆 là 퐿 = (3,6,7,4,2,1,5). Nhắc lại, dãy ( 1, 2, ) gọi là đi trước dãy (푌1,푌2, ,푌푣) theo thứ tự từ điển nếu một trong hai điều kiện sau thoả mãn: - Tồn tại 푖 ∈ {1,2, ,min( ,푣)} sao cho 1 = 푌1, 2 = 푌2, , 푖―1 = 푌푖―1 và 푖 < 푌푖; - 1 = 푌1, 2 = 푌2, , = 푌 và < 푣. Bây giờ Tuấn muốn biết khả năng giải mã ngược lại ra dãy 푆 nếu chỉ biết số 퐾, dãy 퐿 và phương pháp xây dựng dãy 퐿. Tuấn nhận ra rằng có thể tồn tại nhiều dãy 푆 có các phần tử là các số nguyên dương không quá 퐾 mà sau khi thực hiện phương pháp mã hoá như trên có thể cho ra cùng một dãy đặc trưng 퐿. Tiếp tục quá trình thử nghiệm, Tuấn thực hiện 푄 phép biến đổi liên tiếp trên dãy 퐿. Với mỗi phép biến đổi, cậu sẽ chọn hai phần tử của dãy 퐿 hiện tại và đổi giá trị cho nhau, sau đó đếm số dãy 푆 thoả mãn dãy đặc trưng 퐿 vừa được biến đổi. Sau mỗi phép biến đổi, dãy 퐿 được cập nhật. Yêu cầu: Cho biết ,퐾, dãy 퐿 và các phép biến đổi của Tuấn. Trước lần biến đổi đầu tiên và sau mỗi lần biến đổi của Tuấn trên dãy 퐿, hãy tính số lượng dãy 푆 có phần tử, các phần tử là các số nguyên dương không quá 퐾, sao cho dãy đặc trưng của 푆 là dãy 퐿. Dữ liệu: Vào từ file văn bản ENCODE.INP: - Dòng đầu tiên chứa ba số nguyên ,퐾,푄(1 ≤ ,퐾 ≤ 5 × 105;0 ≤ 푄 ≤ 5 × 105). - Dòng thứ hai chứa số nguyên dương 퐿1,퐿2, ,퐿 . Dữ liệu bảo đảm dãy 퐿 = (퐿1,퐿2, ,퐿 ) là một hoán vị của số tự nhiên 1,2, , . - Mỗi dòng trong số 푄 dòng tiếp theo chứa hai số nguyên dương khác nhau 푖,푗 (1 ≤ 푖,푗 ≤ ) mô tả một phép biến đổi của Tuấn với ý nghĩa là đổi giá trị của 퐿푖 và 퐿푗 cho nhau. Các số trên cùng một dòng cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản ENCODE.OUT: - Gồm 푄 +1 dòng, mỗi dòng là phần dư trong phép chia cho 1000000007 của số lượng dãy 푆 tính được cho dãy 퐿 ban đầu và cho dãy 퐿 sau mỗi phép biến đổi theo thứ tự đầu vào. Ví dụ ENCODE.INP ENCODE.OUT Giải thích 332 4 - Các dãy S có dãy đặc trung L = (3,1,2) là: (1,2,2) ; 312 4 (1,3,3) ; (2,3,3) ; (1,3,2). 23 1 - Các dãy S có dãy đặc trưng L = (3,2,1) là: (1,1,2) ; DeThi.edu.vn
7. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn 12 (1,1,3) ; (2,2,3) ; (1,2,3). - Các dãy S có dãy đặc trưng L = (2,3,1) là: (2,1,3). Chấm điểm - Subtask 1 (10% số điểm): ,퐾,푄 ≤ 8. - Subtask 2 (10% số điểm): ,푄 ≤ 8. - Subtask 3(24% số điểm): 푄 = 0 và 퐿 là dãy tăng dần hoặc giảm dần. - Subtask 4 (28% số điểm): ,퐾,푄 ≤ 1000. - Subtask 5 (28% số điểm): Không có ràng buộc nào thêm. ---------HẾT--------- DeThi.edu.vn
8. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn ĐÁP ÁN Bài 4: Vòng tròn (7,0 điểm) Không mất tính tổng quát, giả thiết chiều tăng dần của chỉ số vị trí là chiều kim đồng hồ. - Subtask 1 (10% số điểm): ≤ 10; ≤ 10. Đối với mỗi học sinh, duyệt mọi trạng thái kết thúc có thể. Sau khi duyệt toàn bộ 퐿 + học sinh, với mỗi trạng thái kết thúc, kiểm tra điều kiện mất ( ). Tổng độ phức tạp là ( ! × ). - Subtask số điểm): ; . 2(15% ≤ 500;1 ≤ 푃1, ,푃 < 2;1 ≤ 푄1, ,푄퐿 < 2 ≤ 10 Ta ký hiệu: - 푙[ ] là chi phí tối thiểu để sắp xếp 퐿 bạn lớp Văn liên tiếp nhau theo chiều kim đồng hồ bắt đầu từ . - bm[u] là chi phí tối thiểu để sắp xếp bạn lớp Toán liên tiếp nhau theo chiều kim đồng hồ bắt đầu từ . Ta thực hiện việc tính mảng , 푙 độc lập với nhau. Không mất tính tổng quát, ta xét việc tính cho dãy 푃1, ,푃 dã sắp xếp tăng dần. Do đều bé hơn nên di chuyển từ tới bất kỳ, ta không bao giờ phải sử dụng bước đi 푃푖 2 푃푖 푣 từ tới 1. Tuy nhiên, ta vẫn có thể bước đi từ 1 đến . Gọi là số bạn phải sử dụng bước đi 1→ . Ta có nhận xét sau: + Với < /2, = 0. + Với ≥ /2, ≤ min( ― , ). Do vậy với mỗi , ta cho lần lượt vào các vị trí bắt đầu từ theo chiều kim < 2 푃1, ,푃 đồng hồ và tính khoảng cách tương ứng. Độ phức tạp tính toán: ( ). Còn với , ta duyệt và tìm giá trị cho tổng khoảng cách bé nhất. Độ phức tạp tính toán: ≥ 2 ( 2). Do vậy, chi phí tính toán ra và 푙 là ( 3). Đáp án của bài toán có thể tính trong ( 2) bằng cách duyệt mọi vị trí bắt đằu đoạn liên tiếp của hai lớp. Tổng độ phức tạp là ( 3). - Subtask số điểm): ; . 3(15% ≤ 5000;1 ≤ 푃1, ,푃 < 2;1 ≤ 푄1, ,푄퐿 < 2 ≤ 10 Ta sử dụng: - bm_head [ ] là chi phí để bạn có vị trí bé nhất dồn về vị trí từ 1 tới . - bm_tail [ ] là chi phí để bạn có vị trí lớn nhất dồn về vị trí từ tới ― +1. DeThi.edu.vn
9. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn - Sử dụng hai mảng tính sẵn này, chi phí di chuyển với , cho trước có thể tính trong (1). Dộ phức tạp tính toán cho việc tìm ra [ ] là ( ). Tổ Subtask 4 (20% số điểm): ≤ 5000; ≤ 10. Ta thực hiện việc tính mảng , 푙 với ý nghĩa như ở subtask 3. Tuy nhiên, ta cần thực hiện như sau: - Chia tập học sinh lớp chuyên toán thành 2 tập, di chuyển theo chiều kim đồng hồ và di chuyển ngược chiều kim đồng hồ. - Việc chia tập có 2 khả năng. Gọi ,푞 là điểm đầu và điểm cuối của tập di chuyển ngược chiều kim đồng hồ, ta có thể tính: - Tổng khoảng cách để dồn toàn bộ học sinh từ đến 푞 về phía . - Tổng khoảng cách để dồn toàn bộ học sinh từ 푞 +1 đến ―1 về phía ―1. - Tính được cách giá trị [ ] với nằm trong khoảng ―1 và . Độ phức tạp thuật toán ( 2). - Subtask 5 (20% số điểm): . 1 ≤ 푃1, ,푃 < 2;1 ≤ 푄1, ,푄퐿 < 2; ≤ 10 Tư tưởng tương tự như subtask 3 nhưng chúng ta cần tăng tốc tính toán mảng và bl. Gọi opt là giá trị giúp tổng khoảng cách là bé nhất. Với , ta có opt 표 푡. 2 ≤ < 0 ≤ +1 ≤ Do đó, ta cập nhật dần các phương án tối ưu cho trường hợp trong . Độ phức tạp ≥ 2 (1) cho việc tính là ( ). Áp dụng STL deque, ta có thể tính đáp án bài toán từ và 푙 trong ( ). Tổng độ phức tạp là ( ). - Subtask 6 (20% số điểm): Không có ràng buộc nào thêm. Tư tưởng tương tự như subtask 4 nhưng chúng ta cần tăng tốc tính toán mảng và bl. Đễ làm được việc này, ta phân tích quá trình tính toán [ ]. Khi tính giá trị [ ] ta cần quan tâm 3 tập sau: - Có 1 số học sinh di chuyển thuận chiều kim đồng hồ (tập ); - Có 1 số học sinh giữ nguyên vị trí (tập ); - Có 1 số học sinh di chuyển ngược chiều kim đồng hồ (tập ). Ta có nhận xét: - Khi tính giá trị [ +1], tổng khoảng cách sẽ tăng lên 1 lượng | | + | | ― | |. - Sau khi tính [ +1], ta phải cập nhật lại các tập , , . - Ban đầu, ta có thể khởi tạo ngẫu nhiên nhát cắt ,푞. - Lưu ý rằng mỗi học sinh chỉ đổi từ sang , sang đúng 1 lần. Áp dụng STL deque, ta có thể tính mảng trong ( ). Tổng độ phức tạp là ( ). DeThi.edu.vn
10. Tuyển tập 31 Đề thi Học sinh giỏi Quốc gia THPT môn Tin học (Có đáp án) - DeThi.edu.vn Bài 5: Hai dãy số (7,0 điểm) - Subtask 1 (15% số điểm): 푄,퐾 ≤ 500. Làm đúng như yêu cầu đề bài. Độ dài tối đa của dãy B là 푄 × 퐾. Độ phức tạp của mỗi yêu cầu là (푄 × 퐾). Độ phức tạp chung là (푄2 × 퐾). - Subtask 2 (15% số điểm): 푄 ≤ 5000. Thay vì lưu từng phần tử, ta lưu các đoạn vào cấu dữ liệu danh sách. Độ dài danh sách là (푄). Thế nên, việc quản lý danh sách sẽ mất độ phức tạp là (푄). Độ phức tạp chung là (푄2). - Subtask 3 (20% số điểm): Không có yêu cầu loại 2 và các yêu cầu loại 1 xuất hiện trước tất cả các yêu cầu loại 3. Dùng con trỏ để truy được vị trí các đoạn (퓁, ) trên danh sách. Mỗi thao tác chèn, ta tìm đối tượng (퓁, ) trên danh sách. Sau đó, ta xóa đi và chèn lại các đoạn thay thế. Sau khi có được danh sách trên, ta dùng mảng cộng dồn để tính kết quả mỗi yêu cầu loại 3. Độ phức tạp chung là (푄log 푄). - Subtask 4 (25% số điểm): Không có yêu cầu loại 2. Xử lý offline để xây dựng được danh sách các đoạn (퓁, ). Sử dụng cây Fenwick để cập nhật độ dài khi được thêm và yêu cầu loại 3. Độ phức tạp chung là (푄log 푄). - Subtask 5 (25% số điểm): Không có ràng buộc nào thêm. Ta phải xử lý thêm thao tác xóa bằng kỹ thuật Nâng nhị phân trên cây Fenwick (Binary Lifting on Fenwick tree). Độ phức tạp vẫn là (푄log 푄). Bài 6: Mã hoá dãy số (6,0 điểm) - Subtask 1 (10% số điểm): ,퐾,푄 ≤ 8. Xây dựng tất cả 푛 dãy 푠 khác nhau có thể có và kiểm tra từng dãy. Độ phức tạp: 푄 × 퐾 × log . - Subtask 2 (10% số điểm): ,푄 ≤ 8. Giả sử dãy 푠 chỉ chứa các giá trị {1,2, ,푡} và mỗi giá trị đều xuất hiện ít nhất một lần. Khi đó có thể xây dựng tất cả các dãy 푠 có thể có; số lượng dãy 푠 như vậy là không quá 푛푛. Kiểm tra từng dãy 푠, nếu 푠 có dãy đặc trưng là 퐿 thì kết quả sẽ tăng thêm 푡 (chính là số cách để chọn ra 푡 số trong số được phép). Độ phức tạp: 푄 × × log . DeThi.edu.vn