Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề cấu trúc dữ liệu đặc biệt khi khai thác stl trong c++

CẤU TRÚC DỮ LIỆU ĐẶC BIỆT KHI KHAI THÁC STL TRONG C++ A. MỞ ĐẦU I. Lý do chọn đề tài Trong chuyên đề hội thảo năm 2014 ở Vĩnh Phúc các thầy cô đã phân tích và trình bày rất đầy đủ nguyên lí hoạt động, cách cài đặt và ứng dụng của một số cấu trúc dữ liệu trừu tượng như Hàng đợi, Ngăn xếp, Heap-max… và ứng dụng của nó. Tuy nhiên khi cài đặt bằng một ngôn ngữ lập trình cụ thể người viết phải xây dựng một số hàm và thủ tục để từ đó khai thác thuận lợi. Ở ngôn ngữ lập trình C++ thì có sẵn các thư viện lưu trữ cấu trúc dữ liệu nâng cao thường gặp khi xử lí thuật toán. Có rất nhiều loại cấu trúc dữ liệu đặc biệt, ta quan tâm đến 6 lại cấu trúc:  Hàng đợi hai đầu : dequeue.  Ngăn xếp: stack.  Hàng đợi ưu tiên(đống) : priority-queue.  Tập hợp ánh xạ (set/map)  Vector  Danh sách liên kết (list) Các thư viện có sẵn giúp chúng ta giảm chi phí về thời gian khi phải xây dựng các hàm. Đơn giản như trong Pascal các bạn phải viết thủ tục Quicksort (1,n) để sắp xếp mảng gồm n phần tử thì trong C++ chúng ta chỉ cần gõ dòng lệnh sort(a+1, a+n+1) là được ngay mảng a sắp xếp không giảm. Tuy nhiên trong chuyên đề này tôi xin trình bày hai cấu trúc dữ liệu:  Hàng đợi hai đầu : dequeue.  Hàng đợi ưu tiên (đống): priority_queue . II.Mục đích của đề tài Hàng đợi ưu tiên và Hàng đợi hai đầu là hai cấu trúc dữ liệu trừu tượng rất hữu ích trong quá trình giải các bài toán trong các kì thi học sinh giỏi. Về nội dung kiến thức của hàng đợi hai đầu và hàng đợi ưu tiên đã có rất nhiều tài liệu đề cập đến, trong chuyên đề này tôi không trình bày lại khái niệm, nguyên lí hoạt động mà chỉ nhắc lại các thao tác cơ bản trên hàng đợi để đưa vào áp dụng để giải một số bài toán cụ thế, và cũng là tài liệu tham khảo cho học sinh và giáo viên trong quá trình học tập và giảng dạy các đội tuyển học sinh giỏi. B. NỘI DUNG: I HÀNG ĐỢI HAI ĐẦU 1. Khai báo thư viện hàng đợi: Để sử dụng hàng đợi hai đầu ta phải khai báo thư viện queue: #include 2. Định nghĩa Hàng đợi hai đầu là một container cho phép thực hiện các thao tác sau: + Thêm một phần tử x vào cuối hàng đợi q: q.push_back(x). + Lấy ra một phần tử ở cuối hàng đợi q: q.pop_back(). + Thêm một phần tử xvào đầu hàng đợi q: q.push_front(x); 1 + Lấy ra một phần tử ở đầu hàng đợi q: q.pop_front(); Như vậy việc lấy ra và thêm vào diễn ra ở hai đầu hàng đợi + q.empty(): cho giá trị true nếu hàng đợi rỗng, giá trị false khi hàng đợi không rỗng. + q.front(): cho giá trị của phần tử đứng ở đầu hàng đợi. + q.back(): cho giá trị của phần tử đứng ở cuối hàng đơi. 3. Một số ví dụ về khai báo hàng đợi Ví dụ 1: Khai báo hàng đợi q có các phần tử kiểu int: deque q; Ví dụ 2: Khai báo hàng đợi q có các phần tử kiểu double: deque q; Ví dụ 3:Khai báo hàng đợi q có các phần tử kiểu long long: deque q; *Chú ý: Các phần tử trong hàng đợi đều phải cùng kiểu cũng có thể là một kiểu do người lập trình tự định nghĩa Ví dụ 1 : Hàng đợi có các phần tử là một cặp: typedef pair< int, int> II; deque q; Ví dụ 2:Hàng đợi có các phần tử là cặp ba số nguyên: typedef pair> III; deque q; 4. Bài tập Bài tập 1 (dqueue.cpp) Cho dãy số nguyên a1, a2, …,an và m truy vấn. Truy vấn trên dãy con này là một lệnh có dạng q(i,j) với ý nghĩa tìm phần tử nhỏ nhất trong dãy con ai, ai+1, …,aj (i≤j). Cho m truy vấn Q(i1,j1), Q(i2, j2), …, Q(im,jm) thỏa mãn 1.i1≤i2≤….≤im 2. j1≤j2≤….≤jm Hãy in ra các giá trị là câu trả lời cho các truy vấn tương ứng. Input: file dqueue.inp gồm có:  Dòng đầu tiên ghi hai số nguyên dương n, m (1≤n,m≤105)  Dòng thứ hai ghi n số nguyên a1, a2, …,an.  m dòng tiếp theo, dòng thứ k ghi hai số ik,jk thể hiện cho truy vấn thứ k (dữ liệu đảm bảo thỏa mãn điều kiện 1 và 2 ở trên) Output : file dqueue.out gồm m dòng, dòng thứ k ghi kết quả của truy vấn thứ k. Example : Dqueue.inp Dqueue.out 55 1 23145 1 13 1 23 1 34 4 35 45 Thuật toán: Dễ dàng ta có thể tìm được kết quả của m truy vấn bằng cách sử dụng 2 vòng lặp for như sau: 2 for (int k=1; k<=m; k++) { res=oo; for (int u=i[k]; u<=j[k]; u++) res=min(res, a[u]); printf(“%d\n”,res); } Với tiếp cận cách trên thì độ phức tạp O (m2). Cải tiến: Ta nhận thấy sau khi tìm được đoạn L=[i1,j1] ta xây dựng một danh sách các ứng cử viên cho chức “bé nhất” ql≤ql+1≤…..≤qr. + Nếu lấy ra một phần tử có giá trị =ql khi đó giá trị bé nhất sẽ là ql+1. + Khi thêm vào một phần tử x nếu x usingname space std; deque q; int m,n,a[100001],i[100001],j[100001] int main() { scanf(“%d%d\n”,&n,&m); for (int u=1; u<=n; u++) scanf(“%d”,&a[u]); for (int k=1; k<=m; k++) scanf(“%d%d\n”,&i[k],&j[k]); for (int k=1; k<=m; k++) { for (int u=j[k-1]; u<=j[k]; j++) { while (!q.empty() && q.back()>a[u]) q.pop_back(); q.push_back(a[u]); } for (int u=i[k-1]; u #include #define maxn 100001 using namespace std; deque q; int c[maxn],m,k,i[maxn],j[maxn]; long long f[maxn]; 4 void doc() { scanf("%d%d\n",&m,&k); for (int u=1; u<=m; u++) scanf("%d",&c[u]); } void xuli() { memset(f,sizeof(f),0); // để lưu số tiền nhỏ nhất cần phải trả 2 chiếc bánh mì trong mỗi ngày for (int u=1; u<=m; u++) { i[u]=max(1,u-k+1); j[u]=u; } for (int u=1; u<=m; u++) { for (int t=j[u-1]+1; t<=j[u]; t++) { while (!q.empty() && q.back()>c[t]) q.pop_back(); q.push_back(c[t]); } for (int t=i[u-1]; t 6 #define maxn 1000001 using namespace std; deque q; int n,a[maxn],x,b[maxn],c[maxn],u[maxn],i[maxn],j[maxn],v[maxn]; void doc() { scanf("%d%d",&n,&x); for (int k=1; k<=n; k++) scanf("%d",&a[k]); } void xuli() { for (int k=1; k<=n; k++) { i[k]=k; j[k]=k+x-1; } for (int k=1; k<=n-x+1; k++) { for (int u=j[k-1]+1; u<=j[k]; u++) { while (!q.empty() && q.back()>a[u]) q.pop_back(); q.push_back(a[u]); } for (int u=i[k-1]; um) for (int j=i-m; j #define maxn 1000001 using namespace std; deque q; int n,m,c[maxn]; long long f[maxn],g[maxn]; void doc() { scanf("%d%d",&n,&m); for (int k=1; k<=n; k++) scanf("%d",&c[k]); } void xuli() { f[0]=0; g[1]=c[1]; f[1]=c[1]; g[2]=f[1]+c[2]; q.push_back(g[1]); for (int i=2; i<=n; i++) { 9 while (!q.empty() && q.back()>g[i]) q.pop_back(); q.push_back(g[i]); if (i>m) if (q.front()==g[i-m]) q.pop_front(); f[i]=q.front(); g[i+1]=f[i]+c[i+1]; } printf("%I64d",f[n]); } int main() { freopen("nasa.inp","r",stdin); freopen("nasa.out","w",stdout); doc(); xuli(); return 0; } Bài 5 Dãy dài bậc k Cho dãy số nguyên a1, a2, ..,an. Một dãy con của dãy đã cho là dãy các phần tử liên tiếp nhau. Dãy con ai, ai+1, …,aj được gọi là dãy con đều bậc k nếu như chênh lệch giữa hai số bất kỳ trong dãy này không vượt quá k. Hãy tìm dãy con đều bậc k có độ dài lớn nhất Input: sequarek.inp  Dòng đầu tiên ghi hai số nguyên dương n, k (1≤n≤106,1≤k≤109)  Dòng thứ hai ghi n số nguyên a1, a2, …,an (│ai│≤ 109) Output: một số nguyên duy nhất là độ dài của dãy con tìm được Example: Sequarek.inp Sequarek.out 53 4 21345 Phân tích bài toán: Để tìm được dãy con đều bậc dài nhất ta tìm đoạn [u,v] mà (v-u+1) max thỏa mãn amax-amin≤k . Ta dễ dàng có được kết quả cần tìm thông qua đoạn chương trình : res=0; for( int v=1; v<=n; v++) { fmax=-oo; fmin=oo; for (int u=v; u>=1; u--) { fmax=max(fmax,a[u]); fmin=min(fmin,a[u]); if (fmax-fmin>k ) break; } res=max(res,v-u+1); } 10 Do 1≤n≤106 nên để cải tiến chương trình ta sử dụng hàng đợi sẽ giúp chương trình chạy nhanh với n lớn. Để tiết kiếm chi phí thời gian ta dùng hai hàng đợi q và p trong đó hàng đợi q có đặc điểm phần tử đứng trước có giá trị lớn hơn hoặc bằng giá trị của phần tử đứng sau. Còn hàng đợi p có đặc điểm phần tử đứng trước có giá trị nhỏ hơn hoặc bằng giá trị của phần tử đứng sau. Để kiểm tra xem a[v]-a[u]>k ta sử dụng q.front-p.front>k . Chương trình : #include #include #define maxn 1000001 #define oo 2000000009 using namespace std; deque q,p; int a[maxn],n,k,res; void doc() { scanf("%d%d",&n,&k); for (int i=1; i<=n; i++) scanf("%d",&a[i]); } void xuli() { int u=1; for (int v=1; v<=n;v++) { while (!q.empty() && q.back()a[v]) p.pop_back(); p.push_back(a[v]); while (q.front()-p.front()>k) { if (q.front()==a[u]) q.pop_front(); if (p.front()==a[u]) p.pop_front(); u++; } res=max(res,v-u+1); } printf("%d",res); } int main() { freopen("seqarek.inp","r",stdin); freopen("seqarek.out","w",stdout); 11 doc(); xuli(); return 0; } Bài tập 6. Ếch săn mồi Có m bậc thang đánh số từ 1 đến m từ trên xuống dưới. Mỗi bậc thang được chia đều thành n ô. Ô thứ j của bậc thang i được gọi là ô (i,j) và trên đó có lượng thức ăn aij. Một con ếch muốn đi săn mồi trên những bậc thang. Ếch được xuất phát từ một ô tùy ý trên bậc thang 1 và nhảy dần xuống bậc thang m. Khi nhảy tới ô nào thì ếch sẽ ăn hết thức ăn trong ô đó. Tuy nhiên có một hạn chế là từ ô (x,y) chú ếch chỉ được phép nhảy sang ô (x’,y’) nếu: Yêu cầu : Tìm một cách đi kiếm ăn cho chú ếch sao cho tổng lượng thức ăn kiếm được là lớn nhất. Input frog.inp gồm có: - Dòng 1 chứa ba số nguyên dương m, n, k ≤1000. - M dòng tiếp theo, dòng thứ i chứa n số nguyên dương , số thứ j là aij≤109. Output frog.out gồm có: - Dòng 1 ghi tổng lượng thức ăn kiếm được. - M dòng tiếp theo, dòng thứ i ghi một số nguyên là số hiệu ô đi qua trên bậc thang i. Example Frog.inp Frog.out 352 18 43211 3 43549 5 12375 4 Phân tích bài toán:Gọi f[i][j] là số lượng thức ăn lớn nhất mà ếch kiếm được khi di chuyển đến ô (i,j) ta có công thức quy hoạch động f[i][j]= a[i][j]+max{f[i-1][j+t],t=-k..k} Đáp số cần tìm chính là max{f[m][j], j=1..n}. Để tính f[i][j] ta phải sử dụng ba vòng lặp for dẫn đến chương trình chạy chậm tức là không hiệu quả. Để giảm chi phí thời gian ta sử dụng một hàng đợi hai đầu để tính f[i][j]. Hoạt động của hàng đợi q luôn đưa vào cuối hàng đợi phần tử có giá trị lớn hơn phần tử trước đó. Phần tử đầu hàng đợi được lấy để tính mảng f khi thỏa mãn không quá k. Chương trình : #include #define maxn 1001 using namespace std; deque q; int n, m,k,a[maxn][maxn],tr[maxn][maxn],x[maxn]; long long f[maxn][maxn],res; 12 void doc() { scanf("%d%d%d",&m,&n,&k); for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) scanf("%d",&a[i][j]); } void xuli() { for (int i=1; i<=n; i++) { f[1][i]=a[1][i]; tr[1][i]=0; } for (int i=2; i<=m; i++) { int u=0; int v=0; while (!q.empty()) q.pop_back(); for (int j=1; j<=n; j++) { while (v0) { x[++slx]=id; id=tr[u][id]; u--; } printf("%I64d\n",res); for (int i=m; i>=1; i--) printf("%d\n",x[i]); } int main() { freopen("frog.inp","r",stdin); freopen("frog.out","w",stdout); doc(); xuli(); } Bài tập 7: THỜI TRANG CỦA BÒ Tại hội diễn thời trang mới nhất. Mẫu thời trang đang thịnh hành của các con bò là có hai vệt trắng trên da của nó. Nông dân John đã mua một con bò như vậy. Thật không may, thời trang luôn thay đổi nhanh chóng và bây giờ mẫu thời trang thịnh hành lại là chỉ có một vệt trắng trên da(‼!). Nông dân John muốn tạo lại mẫu thời trang mới cho con bò của mình bằng cách trộn hai vệt trắng thành một. Da của con bò có thể mô tả như là một lưới n hàng, m cột (1≤n,m≤50) gồm các kí tự dạng: ……………. ..xxxx….xxx… …xxxx….xx… .xxxx……xxx.. ……..xxxxx… ………xxx…. 14 Ở đây, kí tự ‘X’ xác định một điểm trắng. hai điểm trắng ‘X’ cùng một vệt trắng nếu nó được nối với nhau bởi một dãy các điểm chung cạnh cùng màu trắng. Có đúng hai vệt trắng như vậy. Nông dân John dùng một cái bút vẽ nhỏ để thực hiện việc trộn hai vệt trắng thành một. Cụ thể anh ta sẽ tô một số ô thành màu trắng để sau khi tô trên tấm da chỉ còn một vệt. Trong ví dụ trên anh ta cần tô 3 ô thành màu trắng (được đánh dấu bởi ‘*’ trong hình dưới đây): ……………. ..xxxx….xxx… …xxxx*...xx… .xxxx..**..xxx.. ……..xxxxx… ………xxx…. Hãy giúp nông dân John xác định số lượng ô ít nhất cần tô thêm để có được mẫu thời trang mới. Input pageant.inp gồm có:  Dòng đầu tiên ghi hai số nguyên dương n, m .  Dòng 2 đến n+1 : Mỗi dòng chứa một xâu kí tự độ dài m chỉ gồm kí tự ‘X’ hoặc ‘.’ Mô tả hình dạng trên da con bò. Output : pageant.out: Một số nguyên duy nhất là số lượng ô ít nhất cần phải tô thành màu trắng. Example Pageant.inp Pageant.out 6 16 3 ................ ..xxxx....xxx... ...xxxx....xx... .xxxx......xxx.. ........xxxxx... .........xxx.... Hướng dẫn: Để giải Bài toán trên ta phải tiến hành qua hai bước: B1 : Tìm số thành phần liên thông B2: Tìm đường đi ngắn nhất giữa hai thành phần liên thông. xp kt Chương trình : #include using namespace std; typedef pair II; int m,n,kq,slt,color[55][55],cl[55][55],kc[55][55]; char a[55][55]; int dh[5]={0,0,-1,0,1}; int dc[5]={0,1,0,-1,0}; deque q; 15 void doc() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) scanf("%c",&a[i][j]); scanf("\n"); } } void bfs(int i, int j) { while (!q.empty()) q.pop_front(); q.push_back(II(i,j)); color[i][j]=slt; while (!q.empty()) { int u=q.front().first; int v=q.front().second; q.pop_front(); for(int k=1;k<=4;k++) { int u1=u+dh[k]; int v1=v+dc[k]; if(1<=u1 && u1<=n && 1<=v1 && v1<=m && a[u1][v1]=='x' && color[u1][v1]==0) { color[u1][v1]=slt; q.push_back(II(u1,v1)); } } } } void timtplt() { memset(color,0,sizeof(color)); slt=0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (a[i][j]=='x' &&color[i][j]==0) { slt++; bfs(i,j); } } 16 void bfs2() { while(!q.empty()) { int u= q.front().first; int v= q.front().second; q.pop_front(); for(int k=1;k<=4;k++) { int u1=u+dh[k]; int v1=v+dc[k]; if(1<=u1 && u1<=n && 1<=v1 && v1<=m && cl[u1][v1]==0) { cl[u1][v1]=1; kc[u1][v1]=kc[u][v]+1; q.push_back(II(u1,v1)); if(color[u1][v1]==2) {kq=kc[u1][v1]-1; return;}; } } } } void timduongdi() { timtplt(); while(!q.empty()) q.pop_front(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(color[i][j]==1) {q.push_back(II(i,j)); cl[i][j]=1;kc[i][j]=0;}; bfs2(); cout< 3. Các thao tác Hàng đợi ưu tiên (đống) là một container cho phép thực hiện các thao tác sau: + Thêm một phần tử x vào hàng đợi ưu tiên h: h.push(x). + Lấy ra khỏi hàng đợi ưu tiên phần tử có giá trị lớn nhất : h.pop(). ** Như vậy việc lấy ra và thêm vào diễn ra một đầu. + h.empty(): cho giá trị true nếu hàng đợiưu tiên không có phần tử nào, giá trị false khi hàng đợi ưu tiên không rỗng. + h.top(): cho giá trị lớn nhất của đống h. + h.size(): cho biết số lượng phần tử trong đống h. 4. Một số ví dụ về khai báo hàng đợi ưu tiên Ví dụ 1: khai báo hàng đợi ưu tiên q có các phần tử kiểu int. priority_queue q; Ví dụ 2: Khai báo hàng đợi ưu tiên q có các phần tử kiểu double; priority_ queue q; *Chú ý: Các phần tử trong hàng đợi đều phải cùng kiểu cũng có thể là một kiểu do người lập trình tự định nghĩa Ví dụ 1: Khai báo Hàng đợi ưu tiên q có các phần tử mà mỗi phần tử là một cặp dữ liệu typedef pair< int, int> II; priority_queue q; Ví dụ 2: Hàng đợi ưu tiên q có các phần tử mà mỗi phần tử là một cặp ba số nguyên: typedef pair> III; priority_queue q; 5. Bài tập áp dụng Để hiểu và vận dụng khai thác được hàng đợi ưu tiên vào giải các bài toán tôi thường cho học sinh làm một số bài tập từ đơn giản nhất đến khó dần để các em học sinh dễ tiếp thu. Bài tập 1. Hàng đợi ưu tiên Max Cho trước một danh sách rỗng. Người ta xét hai thao tác trên danh sách đo: 18 - Thao tác “+V” (ở đây V là một số tự nhiên≤109): Nếu danh sách đang có ít hơn 15000 phần tử thì thao tác này bổ sung thêm phần tử V vào danh sách , nếu không thao tác này không có hiệu lực. - Thao tác “- ”: Nếu danh sách đang không rỗng thì thao tác này loại bỏ tất cả các phần tử lớn nhất của danh sách . Nếu không thao tác này không có hiệu lực. Ví du: Với danh sách ban đầu rỗng: - Nếu ta thực hiện liên tiếp các thao tác : +1, +3, +2, +3 ta sẽ được danh sách (1,3,2,3) - Thực hiện thao tác -, ta sẽ được danh sách (1,2) - Thực hiện hai thao tác +4 ta sẽ được danh sách (1,2 ,4, 4) - Thực hiện thao tác – ta sẽ được danh sách (1,2) - Tiếp tục với các thao tác +2, +9, +7, +8 ta sẽ được danh sách (1, 2, 2, 9, 7, 8) - Cuối cùng ta thực hiện thao tác -, ta còn lại danh sách (1, 2, 2, 7, 8). Vấn đề đặt ra là cho trước một dãy không quá 100000 thao tác.Hãy xác định những giá trị số nào còn lại trong danh sách , mỗi giá trị chỉ được liệt kê một lần. Input io.inp gồm nhiều dòng, mỗi dòng ghi một thao tác . Thứ tự các thao tác trên các dòng liệt kê theo đúng thứ tự sẽ thực hiện. Output io.out gồm có 2 dòng: Dòng 1: Ghi số lượng những giá trị còn lại trong danh sách . Dòng 2: Liệt kê những giá trị đó theo thứ tự giảm dần. Example Io.inp Io.out +1 4 +3 8721 +2 +3 +4 +4 +2 +9 +7 +8 Hướng dẫn: Ta nhận thấy sau mỗi thao tác thêm vào thì danh sách mới luôn được sắp xếp theo thứ tự giảm dần, còn khi loại bỏ phần tử trong danh sách thì phần tử bị loại bỏ luôn có giá trị lớn nhất. Với bài toán trên theo cách làm thông thường thì sau khi thêm một phần tử vào danh sách ta lại phải sắp xếp lại danh sách đó theo thứ tự giảm dần. Việc đó mất nhiều thời gian vì ta phải duyệt lại cả danh sách. Ta nhận thấy dựa vào tính chất của hàng đợi ưu tiên việc đưa ra dãy số còn lại sau 100000 thao tác trở lên đơn giản nhiều. Đây chính là lợi thế của hàng đợi ưu tiên. Chương trình 19 #include #include using namespace std; int n, x[15001]; priority_queue h; char loai; void them() { scanf("%d",&n); if (h.size()<15000) h.push(n); } void bot() { scanf("\n"); if (!h.empty()) { int t=h.top(); while (t==h.top() && !h.empty()) h.pop(); } } void inkq() { int slx=0; while (!h.empty()) { x[++slx]=h.top(); while (!h.empty() && h.top()==x[slx]) h.pop(); } printf("%d\n",slx); for (int i=1; i<=slx; i++) printf("%d ",x[i]); } int main() { freopen("io.inp","r",stdin); freopen("io.out","w",stdout); while (scanf("%c",&loai)==1) { switch(loai){ case '+': them(); break; case '-':bot(); break; } } 20