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

 while(!s.empty()) 
 { 
 int m=(*s.rbegin()); 
 s.erase(s.find(m)); 
 if (m%2==0) 
 { 
 s.insert(m/2); d++; 
 } 
 } 
 cout << d << endl; 
 } 
} 
III. Bài toán Beginner Free Contest 34
1. Phát biểu bài toán
Bảo Bay Bổng đang trong tiết học thể dục. Thầy giáo bảo cả lớp xếp thành một hàng ngang. Lớp học của Bảo Bay Bổng có n học sinh, khi xếp thành hàng ngang, các học sinh được đánh số từ 1 tới n theo thứ tự từ trái sang phải. Học sinh thứ có chiều cao . 
Hai học sinh j có thể nhìn thấy nhau nếu như ở giữa họ không có học sinh nào có chiều cao lớn hơn. Cụ thể hơn, học sinh và nhìn thấy nhau nếu như và Bảo Bay Bổng muốn biết với mỗi học sinh, người đó có thể nhìn thấy bao nhiêu học sinh khác mà có cùng chiều cao với họ.
* Input: đọc từ file văn bản height.inp gồm:
- Dòng đầu tiên chứa số nguyen dương – số truy vấn
- Mỗi truy vấn gồm hai dòng, dòng thứ nhất chứa số nguyên dương 
- Dòng thứ hai chứa số nguyên dương 
* Output: ghi ra file văn bản height.out với mỗi truy vấn, in ra trên một dòng số nguyên cách nhau bởi dấu cách là câu trả lời cho truy vấn đó.
* Example:
height.inp
height.out
1
5
1 2 2 3 2
0 1 1 0 0
* Giải thích:
Học sinh thứ 2 có thể nhìn thấy học sinh 1, 3 và 4 nhưng chỉ có học sinh 3 cùng chiều cao với học sinh 2.
Học sinh thứ 3 chỉ nhìn thấy học sinh 2 là có cùng chiều cao bởi vì học sinh 3 không thể nhìn thấy học sinh 5 do có học sinh 4 có chiều cao lớn hơn.
2. Thuật toán
Với học sinh thứ , đầu tiên ta đi tìm số học sinh có cùng chiều cao và đứng ở vị trí bên trái . Việc tìm số học sinh ở bên phải có thể xử lí tương tự.
Đặt là học sinh gần nhất ở bên trái học sinh có chiều cao lớn hơn hoặc bằng . Ta có thể dễ dàng tính được mảng sử dụng stack.
Đặt là số học sinh bên trái học sinh có thể nhìn thấy được.
Công thức quy hoạch động là:
 +1 nếu 
 nếu 
Độ phức tạp .
3. Cài đặt
#include
using namespace std;
const int maxN = 1e5 + 5;
int q;
int n;
int h[maxN];
int ansL[maxN];
int ansR[maxN];
void solve(int ans[]) {
stack st;
	for (int i = 1; i <= n; i++) {
	while (!st.empty() && h[st.top()] < h[i]) {
	st.pop();
	}
	if (!st.empty() && h[st.top()] == h[i]) {
	ans[i] = ans[st.top()] + 1;
	}
	st.push(i);
	}
}
void reset() {
	fill(ansL + 1, ansL + 1 + n, 0);
	fill(ansR + 1, ansR + 1 + n, 0);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> q;
	while (q--) {
	cin >> n;
	for (int i = 1; i > h[i];
	solve(ansL);
	reverse(h + 1, h + 1 + n);
	solve(ansR);
	reverse(ansR + 1, ansR + 1 + n);
	for (int i = 1; i <= n; i++) {
	cout << ansL[i] + ansR[i] << ' ';
	}
	cout << '\n';
	reset();
	}
}
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)
1. Phát biểu bài toán
Cho số nguyên dương n và dãy số a gồm n số nguyên a1, a2, ..., an. Một dãy con liên tiếp của dãy số a có dạng ai, ai+1, , aj với 1 ≤ i ≤ j ≤ n, tổng của dãy con liên tiếp ai, ai+1, , aj là ai + ai+1 +  + aj.
Em hãy đếm số lượng dãy con liên tiếp của dãy số a đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương k.
* Input: Đọc vào từ file văn bản CHIAK.INP gồm:
- Dòng 1 ghi 2 số nguyên dương n và k (n≤ 106, k ≤ 109). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống;
- Dòng 2 ghi lần lượt các số nguyên a1, a2, .., an (|ai| ≤ 109, i=1..n). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống.
* Output: Ghi ra file văn bản CHIAK.OUT một số duy nhất là số lượng dãy con có tổng các phần tử chia hết cho k.
* Example:
CHIAK.INP
CHIAK.OUT
5 3 
2 -6 1 9 -3 
7
 * Giới hạn:
- Có 5/25 test, tương ứng 1,0 điểm với n ≤ 102;
- Có 15/25 test, tương ứng 3,0 điểm với 102 < n ≤ 103;
- Có 5/25 test, tương ứng 1,0 điểm với 103 < n ≤ 106.
2. Thuật toán
* Sub1: với n 102
Duyệt 3 vòng for: 2 vòng for để xét tất cả các đoạn con [i,j], với mỗi đoạn [i, j] tính tổng các phần tử trong đoạn. Mỗi đoạn kiểm tra, nếu tổng các phần tử chia kết cho k thì tăng đếm
* Sub2: với n 103
- Tạo mảng tiền tố tính tổng các phần tử từ 1 đến i, S[i]=S[i-1] + ai;
- Duyệt mảng tiền tố tính tổng các phần tử trong đoạn [i, j], Tổng=S[j] – S[i-1]. Mỗi đoạn kiểm tra, nếu Tổng chia kết cho k thì tăng đếm. * Sub2: với n 106
- Tạo mảng du[] lưu lại phần dư của mảng tiền tố khi chia cho k. du[i]=S[i]%k. Lưu ý if(du[i]<0) du[i]=abs(k - abs(du[i]));
- Đếm số lần xuất hiện các số du[i] xuất hiện trong dãy. Để giảm độ phức tạp thuật toán có thể sắp xếp lại dãy hoặc sử dụng map().
3. Cài đặt
#include
using namespace std;
const int mx = 1e6 + 5;
int a[mx], res[mx];
long long s[mx], dem=0;
map ma;
int n,k;
vectorv;
void sub1()
{
 for(int i=1;i<=n;i++)
 for(int j=i;j<=n;j++)
 {
 long long Sum=0;
 for(int l=i;l<=j;l++) Sum+=a[l];
 if(Sum%k==0) dem++;
 }
 cout<<dem;
}
void sub2()
{
 for(int i=1;i<=n;i++)
 for(int j=i;j<=n;j++)
 if((s[j]-s[i-1])%k==0)dem++;
 cout<<dem;
}
/*void sub3()
{
 for(int i=0; i<=n; i++)
 {
 res[i]=s[i]%k;
 if(res[i]<0) res[i]=abs(k-abs(res[i]));
 }
 ma[0]=1;
 for(int i=1; i<=n; i++)
 {
 if(ma[res[i]]>0) kq = kq + ma[res[i]];
 ma[res[i]]++;
 }
 cout << kq;
}*/
void sub3()
{
 int sum=0;
 v.push_back(0);
 for(int i=1;i<=n;i++)
 {
 int t=max(0,-a[i]/k+1);
 sum=(sum+1LL*t*k+a[i])%k;
 v.push_back(sum);
 }
 sort(v.begin(),v.end());
 long long dem=0;int i=0;
 while(i<v.size())
 {
 int j=i+1;
 while(j<v.size()&&v[j]==v[i]) j++;
 dem=dem+(long long )(j-i)*(j-i-1)/2;
 i=j;
 }
 cout<<dem;
}
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 freopen("CHIAK.inp","r",stdin);
 freopen("CHIAK.out","w",stdout);
 cin>>n>>k;
 for(int i=1;i>a[i];
 s[1]=a[1];
 for(int i=2;i<=n;i++) s[i]=s[i-1]+a[i];
 //sub1();
 //sub2();
 sub3();
}
V. Hình chữ nhật lớn nhất
1. Phát biểu bài toán
Sau một tuần tưng bừng, náo nức với các hoạt động của ngày hội học sinh, sinh viên Việt Nam 9/1, Coder Bắc nhận ra rằng cậu ta còn khá nhiều bài tập cần phải giải quyết. Một trong những bài tập đó là bài toán lập trình với bảng số khá phức tạp như sau:
Thầy giáo cho một bảng số có kích thước , các dòng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến , từ trái sang phải. Giao của dòng và cột gọi là ô (i,j), có giá trị là (). Thầy đưa ra truy vấn sau đây đối với bảng số: Cho hai số nguyên và , hãy cho biết diện tích lớn nhất của hình chữ nhật gồm các ô nằm trong phạm vi từ dòng thứ đến dòng thứ của bảng số mà trong đó chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất không vượt quá 1 (diện tích của một hình chữ là số lượng các ô tạo ra hình chữ nhật đó).
Yêu cầu: Cho bộ truy vấn . Với mỗi truy vấn hãy tính diện tích hình chữ nhật lớn nhất theo yêu cầu bài toán.
* Input: Đọc từ tệp văn bản REC.INP có cấu trúc sau:
- Dòng đầu tiên gồm hai số nguyên 
- dòng tiếp theo, dòng thứ chứa số ;
- Dòng tiếp theo chứa số nguyên 
- K dòng tiếp theo chứa 2 số nguyên pi và qi biểu diễn truy vấn thứ i ();
- Các số trên cùng một dòng cách nhau bởi dấu cách.
* Output: Ghi ra tệp văn bản REC.OUT gồm dòng, mỗi dòng ghi kết quả tương ứng với mỗi truy vấn.
* Example:
REC.INP
REC.OUT
3 3
1 0 0
2 1 1
2 2 2
4
1 3
1 2
2 3
1 1
6
4
6
3
2. Thuật toán
Subtask 1: Vì quy về bài toán truy vấn trên dãy số một chiều: Tìm dãy con liên tiếp dài nhất có độ dài lớn nhất mà chênh lệch phần tử lớn nhất với phần tử bé nhất không vượt quá 1.
Với thực hiện thuật toán duyệt tìm đoạn con dài nhất với độ phức tạp 
Subtask 2: quy về bài toán duyệt trên mảng hai chiều tìm hình chữ nhật lớn nhất thõa mãn điều kiện chênh lệch giữa phần tử lớn nhất và phần tử bé nhất không vượt quá 1.
- Với mỗi truy vấn tìm đoạn lớn nhất theo yêu cầu bài toán;
- Ta tính trước mảng có nghĩa giá trị nhỏ nhất của cột bao gồm các hàng từ đến tương tự với mảng là giá trị lớn nhất (sử dụng stack để tính trước hai mảng này);
- Sau khi có hai mảng tịnh tiến cho mỗi truy vấn bằng kỹ thuật 2 con trỏ trong thời gian 
Độ phức tạp thuật toán .
Subtask 3:
Với mỗi truy vấn (p, q) đưa ra kết quả O(1) bằng kỹ thuật quy hoạch động, quy bài toán về tính diện tích hình chữ nhật chứa toàn số 1 lớn nhất trên bảng số.
- Do các phần tử chỉ chênh lệch 1, nên ta xử lý 2 trường hợp: đáp án là bảng gồm giá trị 0 và giá trị 1, hoặc đáp án là bảng gồm giá trị 1 và giá trị 2.
- Với mỗi trường hợp, ta đưa bảng về bảng chỉ gồm hai giá trị 0, 1 (ví dụ với trường hợp 2 thì a(i, j) = a(i, j) == 1 || a(i, j) == 2). Sau đó kết quả của bài toán là bảng gồm chỉ toàn giá trị 1 có diện tích lớn nhất. Sử dụng stack để xử lý.
Độ phức tạp thuật toán cho truy vấn 
3. Cài đặt
#include 
#define tentep "REC"
#define forr(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();++it)
#define fi first
#define se second
#define ALL(a) (a).begin(),(a).end()
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define left _____left
#define right _____right
#define next _____next
#define __builtin_popcount __builtin_popcountll
using namespace std;
mt19937 Rand(time(0));
template
bool minimize(X &x, const Y &y)
{
 if (y < x)
 {
 x = y;
 return true;
 }
 else return false;
}
template
bool maximize(X &x, const Y &y)
{
 if (x < y)
 {
 x = y;
 return true;
 }
 else return false;
}
const int MAXN=1005 ;
int numRow,numCol ;
int a[MAXN][MAXN], g[MAXN], h[MAXN], left[MAXN], right[MAXN],
int dp[MAXN][MAXN] ;
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
#ifndef ONLINE_JUDGE
 freopen(tentep".inp", "r", stdin);
 freopen(tentep".out", "w", stdout);
#endif //ONLINE_JUDGE
 cin>>numRow >>numCol ;
 forr(i,1,numRow)
 {
 forr(j,1,numCol)
 cin>>a[i][j] ;
 }
 forr(value,0,1)
 {
 memset(h,0,sizeof h) ;
 forr(bot,1,numRow)
 {
 memset(g,0,sizeof g) ;
 forr(j,1,numCol)
 {
 if(a[bot][j]==value || a[bot][j]==value+1)
 h[j]++ ;
 else h[j]=0 ;
 }
 forr(j,1,numCol)
 {
 int p=j-1 ;
 while(h[p]>=h[j] && p>0)
 p=left[p]-1 ;
 left[j]=p+1 ;
 }
 ford(j,numCol,1)
 {
 int p=j+1 ;
 while(h[p]>=h[j] && p<numCol+1)
 p=right[p]+1 ;
 right[j]=p-1 ;
 }
 forr(j,1,numCol)
 {
 g[h[j]]=max(g[h[j]],right[j]-left[j]+1) ;
 }
 ford(i,bot,1)
 g[i]=max(g[i],g[i+1]) ;
 forr(top,1,bot)
 {
 int i=bot-top+1 ;
 dp[top][bot]=max(dp[top][bot],g[i]*i) ;
 }
 }
 }
 ford(top,numRow,1)
 {
 forr(bot,1,numRow)
 {
 dp[top][bot]=max(dp[top][bot],max(dp[top+1][bot],dp[top][bot-1])) ;
 }
 }
 int numQuery ;
 cin>>numQuery ;
 forr(i,1,numQuery)
 {
 int top,bot ;
 cin>>top >>bot ;
 cout<<dp[top][bot]<<"\n" ;
 }
 return 0 ;
}
VI. Phần thưởng (đề thi học sinh giỏi tỉnh năm 2022)
1. Phát biểu bài toán
Trong cuộc thi Olympic Tin học của tỉnh BG, phần thưởng cho người thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số a cho trước. 
Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy. 
Yêu cầu: Cho dãy số nguyên dương a = (a1, a2, , an). Hãy tìm phần thưởng cho người thắng cuộc. 
Ví dụ với a = (1, 2, 3), những dãy con gồm các phần tử liên tiếp trong a là: 
Dãy rỗng và các dãy có 1 phần tử (1), (2), (3) đều có trọng số 0; 
Dãy (1, 2) và dãy (2, 3) đều có trọng số 1; - Dãy (1, 2, 3) có trọng số 2. 
Phần thưởng cho người thắng cuộc bằng 0+1+1+2=4. 
* Input: Vào từ tệp văn bản BONUS.INP có cấu trúc: 
Dòng 1: Ghi số nguyên dương n (n < 106); 
Dòng 2: Ghi n số nguyên dương a1, a2, , an có giá trị không vượt quá 106. 
* Output: Ghi vào tệp văn bản BONUS.OUT một số nguyên duy nhất là kết quả tìm được. 
BONUS.INP 
BONUS.OUT 
3 
1 2 3 
4 
4 
3 1 7 2 
31 
* Example:
2. Thuật toán
	- Sử dụng hàng đợi 2 đầu (deque)
3. Cài đặt
#include
#define pb push_back
#define fi first
#define se second
#define reset(a) memset(a,0,sizeof(a));
#define all(a) a.begin(),a.end()
#define sz(a) int(a.size())
#define bit(a,i) (((a)>>(i))&1)
#define pii pair 
#define pll pair 
#define pli pair 
#define pil pair 
#define ll long long
///------------------------------------
#define maxn 1000005
#define mnx 1005
#define mxx 105
#define tasks "BONUS"
///------------------------------------
using namespace std;
const long long oo = 1e9+7;
void debug_out() { cerr << '\n'; }
template 
void debug_out(Head H, Tail ...T)
{
 cerr << " " << H;
 debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
///------------khai_bao----------------
int n;
ll a[maxn];
dequeq,q2;
int L_max[maxn],L_min[maxn],R_max[maxn],R_min[maxn];
///------------solution--------------------------
void init()
{
	cin>>n;
	for(int i=1;i>a[i];
}
void sub1()
{
	ll res=0,Max,Min;
	for(int i=1;i<=n;i++)
	{
	Max=a[i];
	Min=a[i];
	for(int j=i-1;j>0;j--)
	{
	Max=max(Max,a[j]);
	Min=min(Min,a[j]);
	res+=Max-Min;
	}
	}
	cout<<res;
}
ll get( int i, int j )
{
	if(i>j)return (0ll);
	ll ret;
	ret=(j-i+1);
	return ret;
}
void sub2()
{
	ll res=0;
	for(int i=1;i<=n;i++)
	{
	while( !q.empty() && a[q.back()] < a[i] ) q.pop_back();
	while( !q2.empty() && a[q2.back()] > a[i] ) q2.pop_back();
	if(q.empty())L_max[i]=1;
	else L_max[i]=q.back()+1;
	if(q2.empty())L_min[i]=1;
	else L_min[i]=q2.back()+1;
	q.push_back(i);
	q2.push_back(i);
	}
	q.clear();q2.clear();
	for(int i=n;i>=1;i--)
	{
	while( !q.empty() && a[q.back()] <= a[i] ) q.pop_back();
	while( !q2.empty() && a[q2.back()] >= a[i] ) q2.pop_back();
	if(q.empty())R_max[i]=n;
	else R_max[i]=q.back()-1;
	if(q2.empty())R_min[i]=n;
	else R_min[i]=q2.back()-1;
	q.push_back(i);
	q2.push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
	res+= get( L_max[i], i ) * get( i, R_max[i] ) * a[i] ;
	res-= get( L_min[i], i ) * get( i, R_min[i] ) * a[i] ;
	}
	cout<<res;
}
///----------------------------------------------
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	freopen(tasks".INP","r",stdin);freopen(tasks".OUT","w",stdout);
	init();
	if(n<=1000)sub1();
	else sub2();
	return 0;
}
PHỤ LỤC SỐ 3: BIÊN BẢN XÁC NHẬN ÁP DỤNG GIẢI PHÁP Ở CÁC TRƯỜNG THPT TRONG TỈNH
TÀI LIỆU THAM KHẢO
Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Nguyễn Minh Hoàng, Nguyễn Thanh Hùng – Tài liệu giáo khoa Chuyên Tin Quyển 1 – Nxb Giáo dục Việt Nam
Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Nguyễn Minh Hoàng, Nguyễn Thanh Hùng – Tài liệu giáo khoa Chuyên Tin Quyển 2 – Nxb Giáo dục Việt Nam
Đỗ Xuân Lôi - Cấu trúc dữ liệu và Giải thuật – Nxb ĐHQG Hà Nội.
Nguyễn Đức Nghĩa - Cấu trúc dữ liệu và Giải thuật – Trung tâm TBVP 123 Lương Thế Vinh.
Nguyễn Xuân My – Một số vấn đề chọn lọc trong môn Tin học – Nxb Giáo dục.
Nguyễn Hoàng Phú – Ngôn ngữ lập trình C++, tập 1, 2, 3 – Nxb Thanh Hóa, 2018