Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án)

Nội dung text: Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án)

1. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn } int max_cells = -1; // Duyệt qua mọi cặp hàng (r1, r2) for (int r1 = 1; r1 <= m; ++r1) { vector col_sum(n + 1, 0); for (int r2 = r1; r2 <= m; ++r2) { // Cập nhật tổng các cột từ hàng r1 đến r2 for (int c = 1; c <= n; ++c) { col_sum[c] += grid[r2][c]; } // Dùng Two Pointers tìm dải cột (c1, c2) sao cho tổng = K ll current_sum = 0; int left = 1; for (int right = 1; right <= n; ++right) { current_sum += col_sum[right]; while (current_sum > K && left <= right) { current_sum -= col_sum[left]; left++; } if (current_sum == K) { int rows = r2 - r1 + 1; int cols = right - left + 1; max_cells = max(max_cells, rows * cols); } } } } fo << max_cells << endl; fi.close(); fo.close(); return 0; DeThi.edu.vn
2. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn } Bài 4. Tổng ước lớn nhất C++ #include #include #include #include using namespace std; const int MAX_VAL = 1000001; const int MAX_N = 1000001; int sum_div[MAX_VAL]; // Mảng lưu tổng các ước thực sự int a[MAX_N]; // Mảng chứa giá trị tổng ước của các phần tử đề bài cho int max_in_window[MAX_N]; // Lưu kết quả Max cho cửa sổ k bắt đầu từ i // Bước 1: Sàng để tính tổng ước thực sự trong O(V log V) void sieve_sum_divisors() { for (int i = 1; i < MAX_VAL; ++i) { for (int j = 2 * i; j < MAX_VAL; j += i) { sum_div[j] += i; } } } int main() { // Tối ưu nhập xuất cho dữ liệu lớn ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k, q; if (!(cin >> n >> k >> q)) return 0; sieve_sum_divisors(); DeThi.edu.vn
3. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn // Bước 2: Nhập mảng và chuyển thành mảng tổng ước for (int i = 1; i <= n; ++i) { int temp; cin >> temp; a[i] = sum_div[temp]; } // Bước 3: Tìm Max cửa sổ trượt độ dài k bằng Deque trong O(n) deque dq; for (int i = 1; i <= n; ++i) { // Loại bỏ các chỉ số nằm ngoài cửa sổ k if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // Loại bỏ các giá trị nhỏ hơn giá trị hiện tại vì chúng không thể là Max while (!dq.empty() && a[dq.back()] <= a[i]) { dq.pop_back(); } dq.push_back(i); // Lưu kết quả cho cửa sổ kết thúc tại i (tương ứng bắt đầu tại i-k+1) if (i >= k) { max_in_window[i - k + 1] = a[dq.front()]; } } // Bước 4: Trả lời q truy vấn trong O(1) mỗi truy vấn while (q--) { int i_query; cin >> i_query; if (i_query >= 1 && i_query <= n - k + 1) { cout << max_in_window[i_query] << "\n"; } } return 0; } DeThi.edu.vn
4. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn Bài 5. Kế hoạch sửa đường C++ #include #include using namespace std; // Khai báo các biến toàn cục để lưu dữ liệu int n, m; int parent[100005]; // Mảng dùng cho DSU để quản lý các nhóm vùng int num_regions; // Biến lưu số lượng vùng dân cư độc lập hiện tại // Cấu trúc để lưu thông tin một con đường nối 2 khu dân cư u và v struct Edge { int u, v; } edges[100005]; int repair_order[100005]; // Thứ tự các con đường bị sửa chữa int results[100005]; // Mảng lưu kết quả mức độ chia cắt từng bước // Hàm tìm đại diện của một vùng (kỹ thuật DSU) int find_set(int v) { if (v == parent[v]) return v; return parent[v] = find_set(parent[v]); // Nén đường đi để chạy nhanh hơn } // Hàm nối hai khu dân cư u và v lại với nhau void unite_sets(int u, int v) { u = find_set(u); v = find_set(v); if (u != v) { parent[u] = v; num_regions--; // Nếu nối được 2 vùng khác nhau, tổng số vùng giảm đi 1 } } int main() { // Tối ưu tốc độ nhập dữ liệu ios_base::sync_with_stdio(false); DeThi.edu.vn
5. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn cin.tie(NULL); // Bước 1: Nhập dữ liệu từ file PLAN.INP (nếu cần dùng file) if (!(cin >> n >> m)) return 0; for (int i = 1; i <= m; i++) { cin >> edges[i].u >> edges[i].v; } for (int i = 1; i <= m; i++) { cin >> repair_order[i]; } // Bước 2: Chuẩn bị cho quá trình làm ngược // Khởi tạo DSU: ban đầu mỗi khu dân cư là một vùng riêng biệt for (int i = 1; i <= n; i++) { parent[i] = i; } num_regions = n; // Số vùng ban đầu bằng đúng số khu dân cư // Bước 3: Duyệt ngược danh sách sửa chữa từ dưới lên for (int i = m; i >= 1; i--) { // Mức độ chia cắt tại bước i chính là số vùng hiện tại results[i] = num_regions; // Thêm lại con đường bị xóa ở bước i vào hệ thống int edge_idx = repair_order[i]; unite_sets(edges[edge_idx].u, edges[edge_idx].v); } // Bước 4: In kết quả ra màn hình (hoặc file PLAN.OUT) for (int i = 1; i <= m; i++) { cout << results[i] << "\n"; } return 0; } DeThi.edu.vn
6. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 2 SỞ GD & ĐT THANH HÓA ĐỀ KIỂM TRA CHẤT LƯỢNG HỌC SINH GIỎI CỤM 8 TRƯỜNG THPT LẦN 8 CẤP TRƯỜNG MÔN: TIN HỌC – LỚP 12 Thời gian: 150 phút (không kể thời gian giao đề) Tổng quan bài thi Bài Tên bài File chương trình File dữ liệu vào File kết quả 1 SỐ TÍ HON TIHON.* TIHON.INP TIHON.OUT 2 RBPOINT RBPOINT.* RBPOINT.INP RBPOINT.OUT 3 DANCING DANCING.* DANCING.INP DANCING.OUT 4 FWORD FWORD.* FWORD.INP FWORD.OUT 5 LIBRARY LIBRARY.* LIBRARY.INP LIBRARY.OUT Sử dụng ngôn ngữ lập trình C hoặc C++ hoặc Python để lập trình giải các bài toán sau, dữ liệu vào là đúng đắn, không cần phải kiểm tra. Các số trên một dòng ghi cách nhau một dấu cách. Bài 1 (6 điểm): SỐ TÍ HON An là một người rất thích khám phá và tìm hiểu những điều thú vị về các con số. Điều đó giúp cậu luôn cảm thấy vui vẻ và yêu thích chúng hơn. Với mỗi số tự nhiên, An gọi các “ước thực sự” của nó là những ước số tự nhiên nhỏ hơn số đó. Chẳng hạn 3 là một “ước thực sự” của 6. Thật đáng thương, số 1 chẳng có ước thực sự nào cả . An cũng gọi một số là “số tí hon” nếu nó nhỏ hơn tổng tất cả các ước thực sự của nó. Chẳng hạn ta có 40 là một số tí hon, vì 40 nhỏ hơn tổng các ước thực sự của nó: 1 + 2 + 4 + 5 + 8 + 10 + 20 = 50. An có một dãy các số tự nhiên và muốn kiểm tra xem chúng có phải là những số tí hon hay không. Hãy giúp An kiểm tra xem có bao nhiêu số tí hon trong dãy của bạn ấy nhé! Dữ liệu vào: Được cho tại file TIHON.INP với cấu trúc như sau: - Dòng đầu tiên ghi số tự nhiên n là số lượng các số có trong dãy của An. - Dòng tiếp theo ghi n số tự nhiên 푖 là các số trong dãy, ngăn cách nhau bởi dấu cách. 6 Giới hạn dữ liệu: 1 ≤ 푛 ≤ 10 8 8 1 ≤ 푖 ≤ 10 với mọi 푖 (các số trong dãy không vượt quá 10 ) Kết quả: Ghi kết quả ra file TIHON.OUT gồm một dòng duy nhất chứa một số nguyên là số lượng các số tí hon trong dãy của An. Ví dụ: TIHON.INP TIHON.OUT 3 2 40 12 16 DeThi.edu.vn
7. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn - Subtask 1 (50% số test): n ≤ 10000 - Subtask 2 (50% số test): Không có giới hạn gì thêm Bài 2 (5 điểm): RBPOINT Trên trục tọa độ Ox có n điểm xanh và n điểm đỏ. Điểm xanh thứ i có tọa độ bi, điểm đỏ thứ i có tọa độ ri. Với hai điểm có tọa độ x1 và x2, ta định nghĩa khoảng cách giữa hai điểm đó là |x2 - x1|. Hãy tìm khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì trong số các điểm đã cho. Dữ liệu: Vào file RBPOINT.INP gồm: - Dòng đầu tiên gồm số nguyên n (1 ≤ n ≤ 105) - số điểm xanh và cũng là số điểm đỏ. 9 - Dòng thứ hai gồm n số nguyên b1, b2,..., bn (1 ≤ bi ≤ 10 ) - với bi là tọa độ của điểm xanh thứ i. 9 - Dòng thứ ba gồm n số nguyên r1, r2, ..., rn (1 ≤ ri ≤ 10 ) - với ri là tọa độ của điểm đỏ thứ i. Kết quả: Ghi ra file văn bản RBPOINT.OUT gồm 1 dòng là khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì. Ví dụ: RBPOINT.INP RBPOINT.OUT 1 4 2 6 2 2 1 7 10 5 - Subtask 1 (50% số test): n ≤ 1000 - Subtask 2 (50% số test): Không có giới hạn gì thêm Bài 3 (4 điểm): DANCING Có N là chàng trai và N cô gái tham gia một bữa tiệc khiêu vũ. Chiều cao của họ đã được đo và đưa vào một danh sách. Mỗi chàng trai sẽ chỉ nhảy với một cô gái và ngược lại. Tức là mỗi người chỉ có nhiều nhất một bạn nhảy. Hai cặp trai gái sẽ không nhảy với nhau nếu như họ có cùng chiều cao. Hãy xác định tối đa các cặp có thể được khiêu vũ với nhau. Dữ liệu vào: Đọc từ file DANCING.INP: - Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 100000). - Dòng thứ hai chứa N số nguyên có giá trị tuyệt đối thuộc [1500, 2500]. Các giá trị tuyệt đối của các số nguyên thể hiện chiều cao của những chàng trai (tính bằng milimet). Chiều cao dương thể hiện chàng trai muốn nhảy với cô gái cao hơn mình, chiều cao âm thể hiện chàng trai muốn nhảy với cô gái thấp hơn mình. DeThi.edu.vn
8. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn - Dòng thứ ba chứa N số nguyên có giá trị tuyệt đối thuộc [1500, 2500]. Các giá trị tuyệt đối của các số nguyên thể hiện chiều cao của những cô gái (tính bằng milimet). Chiều cao dương thể hiện cô gái muốn nhảy với chàng trai cao hơn mình, chiều cao âm thể hiện cô gái muốn nhảy với chàng trai thấp hơn mình. Kết quả: Ghi ra file văn bản DANCING.OUT chứa một số nguyên dương duy nhất là số lượng lớn nhất các cặp nhảy có thể. Ví dụ: Test DANCING.INP DANCING.OUT 1 0 1 -1800 1800 2 1 2 1700 2000 -1800 -1800 2 2 3 -1800 -2200 1900 1700 - Subtask 1 (50% số test): n ≤ 10000 - Subtask 2 (50% số test): Không có giới hạn gì thêm Bài 4 (3 điểm): FWORD Bạn có một từ gồm N chữ cái in thường và trong đó có M chữ cái bị mờ đi không thể đọc được. Ngoài ra, bạn còn có M dòng gợi ý dùng để khôi phục lại từ ban đầu. Dòng thứ i sẽ có K chữ cái là những chữ có thể xuất hiện ở vị trí chữ cái bị mờ thứ i. Từ những gợi ý này bạn có thể tạo ra được một dãy các từ, sắp xếp dãy các từ này tăng dần theo thứ tứ chữ cái và từ ban đầu bạn cần tìm sẽ nằm ở vị trí thứ X. Các bạn hãy viết một chương trình để khôi phục lại từ này nhé! Dữ liệu vào: Đọc từ file FWORD.INP: - Dòng đầu tiên gồm các số tự nhiên N, M , K và X (1 ≤ N ≤ 500, 1 ≤ M ≤ N , 1 ≤ K ≤ 26, 1 ≤ X ≤ 109). - Dòng thứ hai gồm một xâu gồm các chữ cái in thường và dấu # đại diện những vị trí bị mờ. - M dòng tiếp theo, mỗi dòng gồm K chữ cái mà bạn có thể điền vào vị trí bị mờ. Kết quả: Ghi ra file văn bản FWORD.OUT - Gồm một dòng duy nhất là từ mà bạn tìm được. Dữ liệu luôn đảm bảo bài toán có kết quả. DeThi.edu.vn
9. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn Ví dụ: FWORD.INP FWORD.OUT 11 2 4 7 freecontest fr#e#ontest defg abcd - Subtask 1 (60% số test): M = 1 - Subtask 2 (40% số test): Không có ràng buộc gì thêm. Bài 5 (2 điểm): LIBRARY Đất nước A có n thành phố được nối bởi m tuyến đường hai chiều, tuyến đường thứ i nối liền hai thành phố u i và vi. Chính phủ đất nước A mong muốn xây dựng thư viện tại một số thành phố trong đất nước, sao cho từ bất kì một thành phố nào cũng đều có thể đi đến một thành phố có thư viện. Biết rằng chi phí xây dựng thư viện ở thành phố i là a i. Em hãy cho biết tổng chi phí xây dựng thư viện ít nhất có thể. Dữ liệu vào: Đọc từ file LIBRARY.INP: - Dòng đầu tiên gồm hai số nguyên n và m (1 ≤ n, m ≤ 10 5) là số thành phố và số tuyến đường. 9 - Dòng thứ hai gồm n số nguyên a 1, a2,..., an (1 ≤ ai ≤ 10 ) - với ai là chi phí xây dựng thư viện ở thành phố i. - m dòng tiếp theo, dòng thứ i gồm hai số nguyên u i và vi (1 ≤ u i, vi ≤ n, u i,≠ vi ) – mô tả tuyến đường thứ i. Dữ liệu vào đảm bảo mỗi cặp thành phố được nối bởi nhiều nhất một tuyến đường. Kết quả: Ghi ra file LIBRARY.OUT - Một dòng duy nhất là tổng chi phí xây dựng thư viện ít nhất có thể. Ví dụ: LIBRARY.INP LIBRARY.OUT 5 4 5 6 4 2 3 3 1 2 2 4 4 1 3 5 - Subtask 1 (50% số test): n, m ≤ 103 - Subtask 2 (50% số test): Không có ràng buộc gì thêm. ----------HẾT---------- DeThi.edu.vn
10. Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn ĐÁP ÁN Bài 1 (6 điểm): SỐ TÍ HON C++ #include #include #include using namespace std; /** * Hàm kiểm tra một số có phải là số tí hon hay không * Một số là số tí hon nếu tổng các ước thực sự > chính nó. */ bool is_so_ti_hon(int n) { if (n <= 1) return false; // Số 1 không có ước thực sự nào nhỏ hơn nó long long sum_divisors = 1; // 1 luôn là ước thực sự của mọi số > 1 int sqrt_n = sqrt(n); // Tìm các cặp ước từ 2 đến căn bậc hai của n for (int i = 2; i <= sqrt_n; ++i) { if (n % i == 0) { sum_divisors += i; int other_divisor = n / i; if (other_divisor != i) { sum_divisors += other_divisor; } } // Tối ưu: Nếu tổng đã lớn hơn n thì dừng sớm để tiết kiệm thời gian if (sum_divisors > n) return true; } return sum_divisors > n; } int main() { // Tối ưu tốc độ nhập xuất cho dữ liệu lớn (n = 10^6) ios_base::sync_with_stdio(false); cin.tie(NULL); DeThi.edu.vn