Sáng kiến kinh nghiệm Cấu trúc dữ liệu nâng cao trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin học

 PHỤ LỤC
THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN...........3
 1. Tên sáng kiến: Cấu trúc dữ liệu nâng cao trong bồi dưỡng học sinh giỏi cấp tỉnh.3
 2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Tháng 10 năm 2023 ......3
 3. Các thông tin cần được bảo mật ..............................................................................3
 4. Mô tả các giải pháp cũ thường làm..........................................................................3
 5. Sự cần thiết phải áp dụng giải pháp sáng kiến.........................................................3
 6. Mục đích của giải pháp sáng kiến ...........................................................................3
 7. Nội dung ..................................................................................................................4
 7.1. Thuyết minh giải pháp mới hoặc cải tiến..........................................................4
 7.2. Thuyết minh về phạm vi áp dụng sáng kiến .....................................................9
 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến .......................................9
PHỤ LỤC SỐ 1: MỘT SỐ BÀI ĐƠN GIẢN SỬ DỤNG CẤU TRÚC DỮ LIỆU ............11
 I. Bài toán đếm phần tử là bội của k..........................................................................11
 II. Bài toán các số khác nhau.....................................................................................12
 III. Bài toán số duy nhất ............................................................................................13
 IV. Bài toán xóa xố....................................................................................................14
 V. Bài toán dãy ngoặc đúng.......................................................................................15
 VI. Trạm xăng............................................................................................................16
PHỤ LỤC SỐ 2: MỘT SỐ BÀI TẬP ỨNG DỤNG SỬ DỤNG CẤU TRÚC DỮ LIỆU .18
 I. Bài toán phần thưởng .............................................................................................18
 II. Bài toán đếm cặp...................................................................................................19
 III. Bài toán xếp hàng ................................................................................................20
 IV. Bài toán tìm max .................................................................................................22
 V. Bài toán ba điểm thẳng hàng ................................................................................23
 VI. Bài toán phần thưởng (đề thi học sinh giỏi tỉnh năm 2020)................................25
PHỤ LỤC SỐ 3: MỘT SỐ BÀI TẬP KHÓ SỬ DỤNG CẤU TRÚC DỮ LIỆU ...............27
 I. Bài toán Trọng số (Nguồn Codeforces) .................................................................27
 II. Bài toán chia đôi mảng .........................................................................................29
 III. Bài toán Beginner Free Contest 34......................................................................30
 IV. Bài toán dãy con liên tiếp có tổng chia hết cho k (đề thi học sinh giỏi năm 2023)..32
 V. Hình chữ nhật lớn nhất .........................................................................................35
 VI. Phần thưởng (đề thi học sinh giỏi tỉnh năm 2022) ..............................................40
PHỤ LỤC SỐ 3: BIÊN BẢN XÁC NHẬN ÁP DỤNG GIẢI PHÁP Ở CÁC TRƯỜNG .44
TÀI LIỆU THAM KHẢO ........................................................................................................50
 Trang 2 Giải pháp này nhằm mục đích hệ thống một số bài tập sử dụng cấu trúc dữ liệu 
nâng cao, làm tài liệu tham khảo cho giáo viên, giúp giáo viên có cái nhìn tổng quan 
về các dạng bài tập về sử dụng cấu trúc dữ liệu nâng cao; đồng thời sử dụng để bồi 
dưỡng học sinh giỏi giúp học sinh giải các bài toán sử dụng cấu trúc dữ liệu nâng cao.
 Giải pháp 2: Lựa chọn các bài tập sử dụng cấu trúc dữ liệu nâng cao và áp 
dụng vào giảng dạy để củng cố, rèn luyện kỹ năng giải bài toán bằng phương pháp 
ứng dụng sử dụng cấu trúc dữ liệu nâng cao cho học sinh.
 Giải pháp này nhằm mục đích củng cố, rèn kỹ năng giải toán bằng phương 
pháp ứng sử dụng cấu trúc dữ liệu nâng cao cho học sinh. Học sinh được thực hành, 
ôn luyện các bài toán cùng dạng, giúp học sinh biết phân tích bài toán, điểm khác 
biệt và điểm chung của bài tập tương tự với sử dụng cấu trúc dữ liệu nâng cao đơn 
giản qua đó giúp học sinh cải tiến thuật toán.
 Giải pháp 3: Lựa chọn các bài toán sử dụng cấu trúc dữ liệu nâng cao để giải các 
bài toán khó
 Với mỗi bài toán có thể có nhiều cách giải khác nhau, giải pháp đưa ra một số 
cách giải bài toán, trong đó có ứng dụng sử dụng cấu trúc dữ liệu nâng cao để giải các 
bài toán khó giúp học sinh lựa chọn thuật toán tối ưu:
 Giải pháp 4: Đánh giá giải pháp khi áp dụng với một số trường THPT
 Đánh giá tính khả thi của giải pháp với điều kiện trường THPT Chuyên Bắc 
Giang, trường THPT Ngô Sĩ Liên, THPT Thái Thuận và THPT DTNT Tỉnh. Đánh 
giá hiệu quả của giải pháp đối với học sinh trong việc củng cố, rèn kỹ năng giải 
toán bằng phương pháp sử dụng cấu trúc dữ liệu nâng cao nhằm giúp học sinh yêu 
thích môn học, chọn được cách tối ưu khi giải các bài toán tin học, phát triển tư 
duy, phẩm chất và năng lực của học sinh.
 Kết hợp 4 giải pháp trên, sáng kiến kinh nghiệm góp phần giúp nhận diện bài 
toán có sử dụng cấu trúc dữ liệu nâng cao khi lựa chọn thuật toán tối ưu, góp phần 
tổng kết kinh nghiệm của bản thân, chia sẻ, giúp đỡ đồng nghiệp trong việc tìm hiểu và 
thực hiện bồi dưỡng học sinh giỏi đạt hiệu quả cao nhất.
7. Nội dung
7.1. Thuyết minh giải pháp mới hoặc cải tiến
 * Giải pháp 1: 
 - Tên giải pháp: Lựa chọn các bài tập sử dụng cấu trúc dữ liệu nâng cao đơn giản 
để giúp học sinh làm quen với dạng bài tập về sử dụng cấu trúc dữ liệu nâng cao
 - Nội dung: Chọn một số bài tập về sử dụng cấu trúc dữ liệu nâng cao đơn giản
 + Đếm phần tử là bội của k: Viết chương trình nhập vào 2 số nguyên dương m, n 
và mảng 2 chiều gồm m x n phần tử là các số nguyên. Đếm các phần tử của mảng là 
bội của số nguyên k cho trước;
 + Các số khác nhau: Cho số nguyên dương n và dãy số nguyên A1, A2, , An. Đưa 
ra số lượng các số đôi một khác nhau trong dãy.
 Trang 4 * Giải pháp 3: 
 - Tên giải pháp: Lựa chọn các bài toán khó sử dụng cấu trúc dữ liệu nâng cao để giải.
 - Nội dung: Sử dụng cấu trúc dữ liệu nâng cao vào giải các bài toán khó. 
 - Các bước tiến hành thực hiện giải pháp: Với mỗi bài toán, phân tích bài toán, 
 đưa ra một số cách giải quyết bài toán đó, sau đó so sánh với việc sử dụng cấu trúc dữ 
 liệu nâng cao vào giải, đánh giá độ phức tạp thuật toán.
 + Trọng số;
 + Chia mảng;
 + Beginner Free Contest 34;
 + Dãy con liên tiếp có tổng chia hết cho k (đề thi học sinh giỏi tỉnh năm 2023);
 + Hình chữ nhật lớn nhất;
 + Phần thưởng (đề thi học sinh giỏi tỉnh năm 2022);
 - Kết quả khi thực hiện giải pháp: 
 + Sản phẩm được tạo ra từ giải pháp: Phân tích thuật toán, ứng dụng thuật toán 
 sắp xếp và tìm kiếm nhị phân vào giải bài toán và cài đặt (Chi tiết tại phụ lục số 3)
 * Giải pháp 4: 
 - Tên giải pháp: Đánh giá giải pháp khi áp dụng với một số trường THPT
 - Nội dung: Áp dụng giải pháp cho công tác bồi dưỡng HSG cấp tỉnh đối với 
 trường THPT Chuyên, Trường THPT Ngô Sĩ Liên, Trường THPT Thái Thuận, Trường 
 THPT DTNT Tỉnh. Đánh giá kết quả thực hiện các trường trên
 - Các bước tiến hành thực hiện giải pháp: 
 Bước 1: Chọn các bài toán sử dụng cấu trúc dữ liệu nâng cao đã tiến hành trong giải 
 pháp 1, 2 và 3.
 Bước 2: Giới thiệu sáng kiến đến giáo viên đang bồi dưỡng học sinh giỏi tại 
 trường THPT:
 + Năm học 2023-2024: giới thiệu sáng kiến kinh nghiệm tới GV bồi dưỡng học 
 sinh giỏi tại trường THPT Ngô Sĩ Liên.
 Trình độ
 TT Họ và tên Nơi công tác Số điện thoại Chức vụ
 chuyên môn
 1 Lê Anh Tuấn THPT Ngô Sĩ Liên 0945.528.620 Thạc sĩ TPCM
 + Năm học 2023-2024: giới thiệu sáng kiến kinh nghiệm tới giáo viên bồi dưỡng 
 học sinh giỏi tại trường THPT Thái Thuận.
 Trình độ
TT Họ và tên Nơi công tác Số điện thoại Chức vụ
 chuyên môn
 1 Chu Thu Hằng THPT Thái Thuận 0868958632 Đại học Giáo viên
 Trang 6 Bảng 1: Đối sánh kết quả trước và sau khi thực hiện sáng kiến kinh nghiệm 
năm học 2023-2024
 Có 
 Điểm Điểm 
 Giới vận 
TT Họ và tên học sinh Trường THPT bài KT bài KT 
 tính dụng 
 số 1 số 2
 SK
 1 Vũ Thị Ngọc Anh Nữ Chuyên Bắc Giang 7.5 8.5
 2 Thân Hồng Dương Nữ Chuyên Bắc Giang 8 9
 3 Hoàng Hà Nam Chuyên Bắc Giang 7.5 9
 4 Trần Tuấn Hùng Nam Chuyên Bắc Giang 6.5 8.5
 5 Nguyễn Đắc Hưng Nam Chuyên Bắc Giang 6 8
 6 Nguyễn Đức Kiên Nam Chuyên Bắc Giang 7 9
 7 Trịnh Hữu Tuấn Minh Nam Chuyên Bắc Giang 7.5 9
 8 Đặng Đình Gia Nghĩa Nam Chuyên Bắc Giang 4 5.5
 9 Hoàng Văn Trà Nam Chuyên Bắc Giang 8 9.5
10 Đỗ Thành Vinh Nam Chuyên Bắc Giang 8 9.5
11 Nguyễn Lương Vinh Nam Chuyên Bắc Giang 7 8
12 Nguyễn Gia Minh Nam Chuyên Bắc Giang 4.5 6
13 Nguyễn Phương Thảo Nữ Chuyên Bắc Giang 7 8.5
14 Nguyễn Minh Hiếu Nam Chuyên Bắc Giang 3 5
15 Kiều Nguyễn Phương Hà Nữ Chuyên Bắc Giang 6.5 5.5 x
16 Tô Minh Hải Hà Nữ Chuyên Bắc Giang 6 5 x
17 Nguyễn Tiến Việt Hùng Nam Chuyên Bắc Giang 7 6 x
18 Nguyễn Phương Hoa Nữ Chuyên Bắc Giang 7 6.5 x
19 Chu Bá Huy Hoàng Nam Chuyên Bắc Giang 6.5 7 x
20 Lê Đức Minh Nam Chuyên Bắc Giang 4.5 6
21 Nguyễn Tống Duy Long Nam THPT Ngô Sĩ Liên 6.5 8.5
22 Trần Đức Đạt Nam THPT Ngô Sĩ Liên 7 8
23 Bùi Ngọc Dũng Nam THPT Ngô Sĩ Liên 6.5 8
24 Nguyễn Trung Kiên Nam THPT Thái Thuận 8 9.5
25 Nguyễn Minh Bảo Nam THPT Thái Thuận 6.5 8
26 Giáp Văn Long Nam THPT Thái Thuận 7.5 8 x
27 Ngô Văn Duy Nam THPT DTNT Tỉnh 6 7
28 Hà Lê Nga Nữ THPT DTNT Tỉnh 6 7.5
 (ghi chú “x”: là học sinh không tham gia bồi dưỡng sáng kiến - nhóm đối chứng)
 Trang 8 - Về lợi ích xã hội: 
 Sáng kiến kinh nghiệm này là tài liệu tham khảo hữu ích, giúp giáo viên nâng cao 
năng lực chuyên môn, đóng góp hiệu quả cho công tác giảng dạy mũi nhọn bồi dưỡng 
học sinh giỏi ở trường phổ thông, đồng thời góp phần định hướng phát triển năng lực 
tư duy, năng lực tự học cho học sinh, giúp học sinh nhận diện được bài toán sử dụng 
cấu trúc dữ liệu nâng cao.
 * Cam kết: Chúng tôi xin cam đoan những điều khai trên là trung thực, đúng sự 
thật và không sao chép hoặc vi phạm bản quyền.
 Trên đây chỉ là một vài kinh nghiệm của chúng tôi. Chúng tôi rất mong nhận 
được sự đóng góp của Hội đồng sáng kiến cấp cơ sở và các thầy cô đồng nghiệp, để 
giải pháp của tôi có hiệu quả hơn trong những năm dạy học tiếp theo!
 XÁC NHẬN CỦA TÁC GIẢ SÁNG KIẾN
 TRƯỜNG THPT CHUYÊN BẮC GIANG
 Đỗ Minh Thuấn
 Phan Quang Hương
 Trang 10 for(int i=1;i<=m;i++)
 for(int j=1;j<=n;j++)
 if(a[i][j]%k==0)dem++;
 cout<<dem;
 }
II. Bài toán các số khác nhau
1. Phát biểu bài toán
 Cho số nguyên dương n và dãy số nguyên A1, A2, , An. Đưa ra số lượng các số đôi 
một khác nhau trong dãy.
 * Input: đọc từ file văn bản KHACNHAU.INP gồm:
 - Dòng 1 ghi số nguyên dương n (n 106);
 9
 - Dòng 2 ghi n số nguyên A1, A2, , An (|Ai| 10 , i=1..n). Các số cách nhau ít 
 nhất 1 dấu cách.
 * Output: ghi ra file văn bản KHACNHAU.OUT gồm 1 số duy nhất là số lượng 
 các số đôi một khác nhau trong dãy
 * Example:
 KHACNHAU.INP KHACNHAU.OUT Giải thích
 10 5 Gồm các số -1, 5, -2, 9, 10
 -1 5 -2 5 9 -1 -2 10 5 9
2. Thuật toán
 - Sử dụng cấu trúc dữ liệu set;
 - Duyệt các phần tử của mảng, đẩy các phần tử vào set;
 - Đưa ra kích thước của set, là kết quả bài toán.
3. Cài đặt
#include
using namespace std;
int n,a[1000009];
sets;
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 freopen("khacnhau.inp","r",stdin);
 freopen("khacnhau.out","w",stdout);
 cin>>n;
 for(int i=1;i>a[i];s.insert(a[i]);}
 cout<<s.size();
}
 Trang 12