-
Thông tin
-
Hỏi đáp
Bài tập về mảng - Nhập môn lập trình | Trường đại học Hồng Đức
Bài tập về mảng - Nhập môn lập trình | Trường đại học Hồng Đức được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Công nghệ thông tin(DHHD) 20 tài liệu
Trường: Đại học Hồng Đức 130 tài liệu
Thông tin:
Tác giả:
Preview text:
BÀI TẬP MẢNG
BÀI14. Tính tổng các phần tử lẻ của mảng. BÀI LÀM #include using namespace std; int sum =0; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; for(int i=0;i { if(a[i]%2==1) sum+=a[i]; }
cout << "ket qua la " << sum; return 0; }
BÀI15. Liệt kê các số nguyên tố của mảng n phần tử. BÀI LÀM #include using namespace std; bool check (int n) { if(n<2) return false;
for(int i=2;i<=sqrt(n);i++) if (n%i==0) return false; return true; } int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; for(int i=0;i {
if(check(a[i])==true) cout< } return 0; }
BÀI 16. Sắp xếp các số của mảng theo thứ tự tăng dần. BÀI LÀM #include using namespace std; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; sort(a,a+n); for(int i=0;i return 0; } Cach 2 #include using namespace std; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i];
for(int i=0;i { for(int j=i+1;j if(a[i]>a[j]) swap(a[i],a[j]); }
for(int i=0;i cout< return 0; }
BÀI18. Liệt kê phần tử khác nhau xuất hiện trong mảng.
Ví dụ: n=5 1 2 5 6 2. Xuất: 1 2 5 6 LÀM LÀM #include using namespace std; int check[10000]; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; for(int i=0;i<10000;i++) check[i]=0; for(int i=0;i check[a[i]]=1; for(int i=0;i<10000;i++) if(check[i]==1) cout << i <<" "; return 0; }
Cách2. Dùng mảng đánh dấu. Tất cả các phần tử trong mảng bằng 0 #include using namespace std; int check[10000]={0}; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i];
for(int i=0;i if(check[a[i]]==0){ cout< if(check[a[i]]=1); } } }
BÀI19. Tính tổng hai số nguyên lớn.( mà không tính được bằng int, loong loong, doudle). BÀI LÀM #include using namespace std; void tong(string a, string b) { string kq="";
while(a.size() while(a.size()>b.size()) b="0"+b; int du=0;
for(int i= a.size()-1;i>=0;i--) { int k=(a[i]-'0')+(b[i]-'0'); if(k+du>=10){ kq+=('0'+k+du-10); du=1; } else { kq+=('0'+k+du); du=0; } } if(du==1) kq+='1';
for(int i=kq.size()-1;i>=0;i--) cout<} int main(){ string a, b; cin>>a>>b; tong(a,b); return 0; }
BÀI20. Liệt kê các số chính phương của một mảng. BÀI LÀM #include using namespace std; bool scp(int n) { int m=sqrt(n); if(m*m==n)return true; return false; } int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i];
for(int i=0;i if(scp(a[i])==true) cout< return 0; }
Bài21. Người ta gọi cấp số cộng với công sai là m. Hãy kiểm tra xem trong mảng có bao
nhiêu số lập nên cấp số cộng với công sai m. Input Output 9 2 3 4 6 8 9 10 11 12 3 2
Giải thích: Cấp số cộng là: 4 6 8 (gồm 3 số với công sai m = 2) BÀI LÀM #include using namespace std; int a[100002]; int n, dem, res; int m; int main(){ cin>>n;
for(int i=0;i cin>> a[i]; cin>>m; res = 0; dem = 0;
for(int i = 0; i if(a[i+1]-a[i]==m) dem++; else dem = 0; if (res < dem) res = dem; }
if (res == 0) cout << 0; else cout << res+1; return 0; }
BÀI 27 . Cho mảng gồm n phần tử. Hãy tìm phần tử có tổng các chữ số lớn nhất là bao
nhiêu, đưa ra vị trí phần tử đó trong mảng.(n<10000) Input Output 9 23 55 28 999 12 45 26 18 54 27 4 BÀI LÀM #include using namespace std; int a[10002]; int cs, n; int main(){ cin>>n;
for(int i=0;i cin>>a[i]; int tongmax =0; int vt =0; for(int i=0;i int tong=0; int so=0; while(a[i]>0){ cs=a[i]%10; tong=tong +cs; a[i]=a[i]/10; if(tongmax< tong){ tongmax=tong; vt=i+1; } } }
cout << tongmax << " "< return 0; }
BÀI 28 . (Hai mảng bằng nhau). Cho mảng gồm các phần tử. Hãy tìm phần tử có tổng các
chữ số là lớn nhất, đưa ra vị trí phần tử đó trong mảng. (đưa ra phần tử lớn nhất đầu tiên trong dãy). Input Output 9 23 55 28 999 12 45 26 18 54 999 4 BÀI LÀM #include using namespace std; int a[10002], y[10002];
int cs, n, tongmax=0,ptmax=0,vt=0; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; y[i]=a[i]; } for(int i=1;i<=n;i++){ int tong=0; while(a[i]>0){ cs=a[i]%10; tong=tong +cs; a[i]=a[i]/10; if(tongmax< tong){ tongmax=tong; ptmax=y[i]; vt=i; } } }
cout << ptmax << " "< return 0; }
BÀI29. Cho một mảng gồm n phần tử. Đếm xem trong mảng có bao nhiêu số chia hết cho 3. BÀI LÀM #include using namespace std; int n, res = 0; string st; int s; int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//freopen("BAI2.INP","r", stdin);
//freopen("BAI2.OUT","w", stdout); cin >> n;
for(int i = 1; i<= n; i++){ cin >> st; s = 0;
for (int j =0; j< st.size(); j++) s = s+ st[j] - 48; if (s%3==0) res ++; } cout << res; return 0; }
BÀI 30. Hãy liệt kê tất cả các số nguyên tố trong khoảng [m, n]. Ví dụ m= 1, n=10 ta có kết quả là 2,3,5,7. Input: -
Dòng đầu tiên đưa vào số lượng test T -
Những dòng kế tiếp mỗi dòng đưa vào một bộ test. Mỗi bộ test là bộ m, n được
viết cách nhau một vài khoảng trống. -
T, m, n thỏa mãn ràng buộc: 1<=T<=100; 1<=m<=n<=10000; n-m<=10000. Input Output 2 2 3 5 7 1 10 3 5 3 5 BÀI LÀM Cách 1: #include using namespace std; bool check(int n) { if(n<2)return false;
for(int i=2;i<=sqrt(n);i++) { if(n%i==0) return false; } return true; } int main(){ int test; cin>>test; while(test--){ int m,n; cin>>m>>n; for(int i=m;i<=n;i++)
if(check(i)==true) cout < } cout< return 0; }
Cách 2. Sàng số nguyên tố. #include using namespace std; int main(){ int test; cin>>test; while(test--){ int m,n; cin>>m>>n; int a[10001]={0}; a[0]=1; a[1]=1; for(int i=2;i<=n;i++) { if(a[i]==0) { for(int j=i*i;j<=n;j+=i) { a[j]=1; } } } for(int i=m;i<=n;i++) { if(a[i]==0) cout< } cout< } return 0; } n −1
Bai31.Cho mảng gồm n phần tử. Tìm tổng ∑ Ai∗i để có giá trị lớn nhất(bằng cách sắp đặt i=0
lại các phần tử trong mảng). Chú ý kết quả có thể là rất lớn hãy đưa ra kết quả lấy modulo với 10 9 +7
Input: - dòng đầu tiên đưa vào số lượng bộ test T.
-Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm 2 dòng: dòng thứ nhất đưa vào số
phần tử của mảng N; dòng kế tiếp đưa vào N số Ai tương ứng với các phần tử của mảng; các số
được viết cách nhau một vài khoảng trống.
- Thỏa mãn 1<=T<=100; 1<=N, A[i]<=10 7 .
Output : đưa ra kết quả mỗi test theo từng dòng. Ví dụ: Input Output 2 5 5 3 2 4 1 40 3 1 3 2 8
Giải thích: Sắp sếp mảng theo thứ tự tăng dần: 1 2 3 4 5 rồi tính tổng: 0.1+1.2+2.3+3.4+4.5 =40 BÀI LÀM #include using namespace std; long module=10e9+7; void result() { long n, a[n+1]; cin >>n; for( long i=0;i>a[i]; sort(a,a+n); long sum=0; for(long i=0;i sum+=a[i]*i; sum=sum%module; } cout<} int main(){ int test; cin>>test; while(test--) { result(); } return 0; }
BÀI 32. Số hoàn thiện là số mà tổng các ước của nó bằng chính nó.Hãy đếm và in ra các
số hoàn thiện của mảng một chiều. Input Output 6 2 1 3 4 6 9 28 6 28 BÀI LÀM #include using namespace std; bool hoan_thien (int n) { int s=0; for(int i=1;i<=n-1;i++) { if (n%i==0) s=s+i; } if (s==n) return true; else return false; } int main()
{ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//freopen("BAI604.INP","r", stdin);
//freopen("BAI604.OUT","w", stdout); int a[1000], i, n, dem=0; cin>>n; for(i=0;i cin>>a[i];
for (i=0;i if(hoan_thien(a[i])==true) dem++;
cout<<"co "< for (i=0;i if(hoan_thien(a[i])==true) cout< cout< return 0; }
BÀI 37. Nhập vào một mảng N số nguyên a1, a2, a3, ...., aN (1<=N<=10 5 ). Hãy đếm số
lượng số không âm của dãy số trên và tính tổng các số không âm đó. BÀI LÀM #include const int N=100002; using namespace std; int a[N]; int n; long long res=0; long long s=0; int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//freopen("BAI603.INP","r", stdin);
//freopen("BAI603.OUT","w", stdout); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) if(a[i]>=0) res++; for(int i=1;i<=n;i++) if(a[i]>=0) s=s+a[i];
cout << res << endl; cout< return 0; }
BÀI 38. Nhập vào một mảng N số nguyên a1, a2, a3, ...., aN (1<=N<=10 5 ). Hãy đếm số
lượng số chẵn của dãy số trên và đếm số lượng số lẻ của dãy số trên. BÀI LÀM #include const int N=100002; using namespace std; int a[N]; int n; long long res=0; long long s=0; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) if(a[i]%2==0) res++; for(int i=1;i<=n;i++) if(a[i]%2==1) s++;
cout << res << endl; cout< return 0; }
BÀI 39. Nhập vào một mảng N số nguyên a1, a2, a3, ...., aN (1<=N<=10 5 ). Hãy đưa ra số
chẵnlớn nhất và số lẻ lớn nhất của dãy số trên. BÀI LÀM #include const int N=100002; using namespace std; int a[N]; int n; long long res=0; long long s=0; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++)
if(a[i]%2==0&res for(int i=1;i<=n;i++)
if(a[i]%2==1&s cout << res << endl; cout< return 0; }
BÀI40. Cho số nguyên dương n và cho dãy số nguyên a1, a2, a3, ..., an. Một đoạn con của
dãy là một dãy các phần tử liên tiếp al,..., ar. Trong đó 1<=L<=R<=n. Hãy tính xem trong
dãy đã cho có bao nhiêu đoạn con có tổng các phần tử bằng 0. -
Dòng đầu chưa số nguyên dương n. 1<=n<=10 5 -
Dòng thứ hai chưa n số nguyên a1, a2, a3, ..., an Input Output 4 2 3 4-7 3 BÀI LÀM #include const int N = 1e5+3; using namespace std; int a[N]; long long f[N]; int n; long long res = 0; map< long long, int> mp; int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//freopen("TONG.INP", "r", stdin);
//freopen("TONG.OUT", "w", stdout); cin >> n;
for(int i = 1; i<= n; i++) cin >> a[i]; f[0]= 0;
for(int i = 1; i<= n; i++) f[i] = f[i-1]+a[i]; mp[0]++;
for(int i = 1; i<= n; i++){ res = res + mp[f[i]]; mp[f[i]]++; } cout << res; return 0; }
BÀI 41. Cho dãy số nguyên a1, a2, a3, ..., an. Hãy tìm tích nhỏ nhất của hai số thuộc dãy
số trên. ( nghĩa là tìm tích của a i *a j nhỏ nhất với i#j) Dữ liệu: -
Dòng đầu tiên là số nguyên dương n. (2<=n <= 10 5 ) -
Dòng thứ 2 là dãy số nguyên a1, a2, a3, ..., an. ( |a 9 i| <=10 ) Input Output 8 1 3 5 -2 4 5 7 9 -18 BÀI LÀM #include using namespace std; const int N=100002; int main(){ int n; cin>>n; long long a[n];
for(long long i=0;i cin>>a[i];
for(long long i=0;i { for(long long j=i+1;j if(a[i]>a[j]) swap(a[i],a[j]); } if(a[0]<0&a[n-1]>0)
cout< else if( a[0]<0&a[n-1]<0)
cout< else cout< return 0; }
Cách 2. Sắp xếp theo sort() #include using namespace std; const int N=100002; int main(){ int n; cin>>n; long long a[n];
for(long long i=0;i cin>>a[i]; sort(a, a+n); if(a[0]<0&a[n-1]>0)
cout< else if( a[0]<0&a[n-1]<0)
cout< else cout< return 0; }
Bài 53 Cho dãy số nguyên A gồm n phần tử a1, a2, .., an.
Hãy đểm số cặp chỉ số i, j thỏa mãn a1 + a2+ …+ai = aj + aj+1+ …+anVới 1 ≤ i Dữ liệu: Vào từ file ESEQ.INP gồm:
+ Dòng đầu ghi số nguyên dương (2 ≤ n ≤ 10 n 5)
+ Dòng tiếp theo ghi n số nguyên a1, a2, ..., an
( | ai| <= 109 ) các số cách nhau bởi dấu cách
Kết quả: Ghi ra file văn bản
một số duy nhất là số cặp tìm được ESEQ.OUT Ví dụ: ESEQ.INP ESEQ.OUT 3 3 1 0 1 Ràng buộc:
+ Có 40% số điểm tương ứng với n <= 500;
+ Có 20% số điểm tương ứng với n <= 104;
+ Có 40% số điểm còn lại không có ràng buộc gì thêm. BÀI LÀM #include using namespace std; long long n,a[100005],dem =0; long long sl, sr; int main(){
ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
//freopen("BAI3.INP","r",stdin);
//freopen("BAI3.OUT","w",stdout); cin>>n; for (int i= 1; i<= n; i++) cin>>a[i]; for (int i=1; i< n; i++)
for (int j= i+1; j<= n; j++){ sl = sr = 0;
for(int k = 1; k<= i; k++) sl = sl+a[k];
for(int k = j; k<= n; k++) sr = sr+a[k]; if (sr == sl) dem++; } cout<} Bai lam #include const int maxn=1e5+6; using namespace std; int n; int a[maxn]; long long dem=0; int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//freopen("BAI1.INP","r", stdin);
//freopen("BAI1.OUT","w", stdout); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; long long tongtrai, tongphai;
for(int i=1;i for(int j=i+1;j<=n;j++){ tongtrai=0;
for(int k=1;k<=i;k++)tongtrai=tongtrai+a[k]; tongphai=0;
for(int k=j;k<=n;k++)tongphai=tongphai+a[k]; if(tongtrai==tongphai)dem++; } cout< return 0; }
BÀI 62. Cho một mảng gồm các phần tử là số nguyên dương. Hãy đưa phần tử lẻ lớn nhất
và vị trí của số đó trong mảng. Input Output 10 11 8 2 3 4 5 8 9 4 11 2 3 #include using namespace std; int a[10002]; int n; int ptmax; int vt=0; int le; int main(){
//freopen("bai6.inp","r",stdin);
// freopen("bai6.out","w",stdout); cin>>n;
for(int i=0;i cin>>a[i];
for(int i=0;i if(a[i]%2==1) le=a[i]; if(ptmax< le){ ptmax=le; vt=i+1; } }
cout << ptmax << " "< return 0; }
BÀI 67( bài 4 Cẩm Thủy). cho dãy số nguyên a1, a2,..., an. (|ai|<10 9 , n<10 5 ).
Một tập hợp khác rỗng các số hạng liên tiếp(ai, a i+1 ,... ak)(i<=k) gọi là đoạn con của dãy đó.
Với mỗi đoạn con ta tính tổng tất cả các số hạng của nó.(cách này chỉ đạt điểm tối n< 10 4 ).
Yêu cầu: tìm giá trị lớn nhất trong số các tổng của các đoạn con của dãy đã cho. Input Output 7 8 1 -2 -1 4 -1 5 -2 (4 -1+ 5=8) Bài làm #include using namespace std; long long n,a[100005]; long long sl; long long maxx=-1e9; int main(){ cin>>n; for (int i= 1; i<= n; i++) cin>>a[i]; for (int i=1; i< n; i++){ sl=0; sl = sl+a[i];
for (int j= i+1; j<= n; j++){ sl = sl+a[j]; if (maxx } } cout<}
Bài 69. Cho mảng gồm n phần tử . Hãy liệt kê các cặp phần tử có tổng bằng s. Input Output 10 12 4,8 4 5 6 7 8 9 10 12 11 15 5,7 BÀI LÀM #include using namespace std; long long n,a[100005]; long long s; long long dem=0; int main(){ cin>>n; cin>>s; for (int i= 1; i<= n; i++) cin>>a[i]; for (int i=1; i< n; i++)
for (int j= i+1; j<= n; j++){ if((a[i]+a[j])==s) dem++;
if((a[i]+a[j])==s) cout < }
if(dem!=0) cout< else cout<<"-1"; return 0; }
Bài 69.b. Cho mảng gồm n phần tử . Hãy đếm các cặp phần tử có tổng bằng s.
( trong dãy có tổng không bằng s thì đưa ra -1) Input Output 8 -1 10 234 55 66 88 99 12 18 11 (10 12 4 2 3 4 5 6 7 8 9 10 11) BÀI LÀM #include using namespace std; long long n,a[100005]; long long s, dem; int main(){ cin>>n; cin>>s; for (int i= 1; i<= n; i++) cin>>a[i]; for (int i=1; i< n; i++)
for (int j= i+1; j<= n; j++){ if((a[i]+a[j])==s) dem ++; }
if(dem> 0)cout< else cout<< "-1"; return 0; }
Bài 70 Cho dãy số gồm n số nguyên a1, a2, …, an và 2 số nguyên không âm L, R (L ≤ R).
Yêu c u: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai+…+aj| ≤ R .
Dữ liệu vào: Từ file văn bản BAI4.INP gồm:
- Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 104 ; 0 ≤ L ≤ R ≤ 109)
- Dòng thứ hai chứa n số nguyên a 9 1, a2,…, an (ai ≤ 10 )
Kết quả: Ghi ra file văn bản BAI4.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được. Ví dụ: BAI4.INP BAI4.OUT 3 0 1 4 1 -1 2 #include using namespace std; long long a[10008]; long long ttt[10008]; int main(){ long long n,r,l;
cin>>n>>l>>r; ttt[0]=0; for(int i=1;i<=n;i++){ cin>>a[i]; ttt[i]=ttt[i-1]+a[i]; // cout<} long long res=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){
if(abs(ttt[j]-ttt[i-1])<=r && abs(ttt[j]-ttt[i-1])>=l ){ res++; } } } cout< return 0; }
Bài 71.( dãy con tăng dài nhất và chia hết cho số trước nó không liên tiếp)
Một dãy gồm N số nguyên dương a1,a2,...,an được gọi là dãy con hoàn toàn nếu aj chia hết cho
ai với mọi j>i, ví dụ dãy 3, 15, 60, 720 là dãy con hoàn toàn.
Một dãy con của 1 dãy cho trước được thiết lập bằng cách xóa đi một số phần tử nào đó của dãy
(giữ nguyên thứ tự). ví dụ dãy gồm 9 phần tử: 2,3,7,9,14, 39 145 76,320 thì 3,7,14,76 là dãy
con nhưng 3,14,7 không phải dãy con.
Yêu cầu: Tìm dãy con hoàn toàn có độ dài lớn nhất.
Dữ liệu vào: Cho trong file BAI5.INP có cấu trúc: -
Dòng đầu tiên ghi số n (n<=103) -
Dòng tiếp theo ghi n số nguyên a1,a2,...,an. Mỗi số cách nhau một dấu cách.
Dữ liệu ra: ghi ra file BAI5.OUT một số nguyên M là độ dài dãy con hoàn toàn độ dài lớn nhất Ví dụ: BAI5.INP BAI5.OUT 10 4 2 3 4 8 9 27 145 81 320 5 (10 (5) 1 3 5 7 9 2 4 8 16 1) vì 1, 2, 4, 8, 16 Bài làm #include using namespace std; int a[105], l[105], n, dem; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1; i<=n;i++) l[i]=1; dem=0;
for(int i=1;i for(int j=i+1;j<=n;j++){
if(a[j]>a[i]&&a[j]%a[i]==0&&l[j] l[j]=l[i]+1; if(dem } cout << dem; return 0; }
Bài 72.Cho dãy gồm n số nguyên a1, a2, a3, ...., an. Hãy đếm và đưa ra số đặc biệt trong
dãy a. Số đặc biệt là số chỉ xuất hiện đúng 1 lần trong dãy số. N<=10 6 và |ai|<=10 9 BAI5.INP BAI5.OUT 10 4 2 3 4 8 9 7 5 8 3 5 2 4 9 7 BÀI LÀM #include using namespace std; mapma; long long a[10008], dem=0,n; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; ma[a[i]]++; if(ma[a[i]]==1) dem++; if(ma[a[i]]==2)dem--; }
cout< for(int i=1;i<=n;i++){ if(ma[a[i]]==1) cout< } return 0; }
Bài 72. ngọc lặc. Tổng các số. Em hãy viết chương trình nhập vào 1 dãy số nguyên rồi đếm
ra cặp 3 số mà tổng các số của 3 số có hàng đơn vị là các số 8, 9, 0. Nếu không có thì đưa ra -1.
(cách làm 3 for lồng nhau khi test đểm được ít điểm) BAI5.INP BAI5.OUT 10 34 3 4 5 6 2 4 7 8 9 3 #include using namespace std; long long n,a[100005]; long long tong=0; long long dem; int main(){ cin>>n; for (int i= 1; i<= n; i++) cin>>a[i]; for (int i=1; i<=n; i++){
for (int j= i+1; j<= n; j++)
for( int k= j+1; k<=n;k++) { tong=a[i]+a[j]+a[k];
if(tong%10==8||tong%10==9||tong%10==0) dem++; } }
if(dem!=0) cout< else cout<<"-1"; return 0; }
Bài 73. Tìm độ dài của dãy con tăng có độ dài lớn nhất ( dãy con không liên tiếp). BAI5.INP BAI5.OUT 6 4 1 2 5 4 6 2 (dãy con 1 2 5 6 hoặc 1 2 4 6) Bài làm #include using namespace std; int a[105], l[105], n, dem; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1; i<=n;i++) l[i]=1; dem=0;
for(int i=1;i for(int j=i+1;j<=n;j++){
if(a[j]>a[i]&&l[j] l[j]=l[i]+1; if(dem } cout < return 0; }
Bài 74. Cho một dãy gồm n phần tử. Hãy đếm xem trong dãy có bao nhiêu tập con có tổng
bằng s. ( dãy con có tổng bằng s). Nếu có dãy con trả về 1, nếu không có trả về 0. BAI5.INP BAI5.OUT 8 92 1 69 16 82 170 31 24 45 112 #include using namespace std; int n, s; int main(){ cin>>n>>s; vector a(n);
for(int i=0;i cin>>a[i]; vector dp(s+1,false); dp[0]=true;
for(int i=0;i for(int j=s;j>=a[i];j--){ if(dp[j-a[i]]==true){ dp[j]=true; } } }
if(dp[s]) cout<<1< else cout << 0 << endl; return 0; }
Bài 76. Tìm dãy con liên tiếp không giảm dài nhất của một dãy số. Yêu cầu in ra số phần
tử và dãy con liên tiếp dài nhất. BAI5.INP BAI5.OUT 6 3 3 2 5 7 4 6 2 5 7 8 7 2 1 3 4 4 4 5 6 2 9 1 3 4 4 4 5 6 BÀI LÀM #include using namespace std; int n, a[1005], b[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; b[i]=1; } for(int i=n-1; i>0;i--){
if(a[i]>=a[i-1]) b[i-1]+=b[i]; } int m=b[0]; for(int i=1;i if(m } cout< int vt=0;
for(int i=0;i if(b[i]==m) vt=i; } for(int i=vt;i cout< } return 0; }
Bài 77. ( kiểm tra lại sự đúng ).Tìm dãy con liên tiếp không giảm dài nhất của một dãy số
có tổng lớn nhất. Yêu cầu in ra tổngvà dãy các phần tử có tổnglớn nhất. BAI5.INP BAI5.OUT 6 14 3 2 5 7 4 6 2 5 7 BÀI LÀM #include using namespace std;
int n, a[1005], b[1005], c[1005], d[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; b[i]=1; } for(int i=n-1; i>0;i--){ if(a[i]>=a[i-1]) { b[i-1] += b[i]; } } int i=0; int k=0; int m=0; int index=0; int sl=0; while (i < n){ if(b[i]==1){ c[k]=a[i]; i++; if(m m=c[k]; index=i; sl=b[i]; } } else { c[k]=0; for(int j=i;j c[k] += a[j]; } if(m < c[k]){ m = c[k]; index = i; sl = b[i] +1; } i += b[i]; } k++; } for(int i=0;i if(m }
cout< for(int i=index;i cout< return 0; }
Bài 78. Tìm dãy con bằng nhau liên tiếp trong 1 dãy số. Yêu cầu : liệt kê các phần tử của dãy con bằng nhau. BAI5.INP BAI5.OUT 6 2 2 2 2 2 2 9 6 6 6 6 Bài làm #include using namespace std; int n, a[1005], b[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; b[i]=1; } for(int i=n-1; i>0;i--){ if(a[i]==a[i-1]) { b[i-1] += b[i]; } } int i=0; while (i < n){ if(b[i]!=1){ for(int j=i;j cout< } cout< i+=b[i]; } else i++; } return 0; }
Bài 79. Tìm dãy con bằng nhau liên tiếp dài nhất trong một dãy số. Yêu cầu: in ra tổng số
phần tử và liệt kê các phần tử của dãy con bằng nhau BAI5.INP BAI5.OUT 6 3 2 2 2 9 6 6 2 2 2 #include using namespace std; int n, a[1005], b[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; b[i]=1; } for(int i=n-1; i>0;i--){ if(a[i]==a[i-1]) { b[i-1] += b[i]; } } int m=b[0]; for(int i=1;i if(m } cout< int vt=0;
for(int i=0;i if(b[i]==m) vt=i; } for(int i=vt;i cout< } return 0; }
Bài 80. Cho dãy số n. Hãy in ra dãy số đảo ngược BAI5.INP BAI5.OUT 6 6 2 2 2 9 6 6 6 6 9 2 2 2 Bài làm #include using namespace std; int n, a[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i];
cout< for(int i=n-1; i>=0;i--){ cout< } return 0; }
BÀI 81. Đếm số lần xuất hiện xuất hiện của mỗi phần tử trong dãy số. BAI5.INP BAI5.OUT 10 2 4 2 2 2 3 3 5 5 9 9 2 3 2 5 2 9 2 Bài làm #include using namespace std; int n, a[1005], b[1005]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; b[i]=1; } for(int i=0;i int d=1; if(b[i]){ b[i]=0;
for(int j=i+1;j if(a[j]==a[i]){ d++; b[j]=0; } cout< } } return 0; }
Bài 82. Chèn x vào phần tử thứ k của dãy số a có n phần tử. Đưa ra số phần tử và dãy số a sau khi chèn. BAI5.INP BAI5.OUT 6 4 8 7 4 6 5 9 3 7 4 6 5 8 9 3 7
(6 là số phần tử của dảy, 4 là vị trí thứ 4 cần chèn,8 (7 là số phần tử của
là số cần chèn vào vị trí thứ 4) dãy số mới) Bài làm #include using namespace std;
void InserArr(int a[], int &n, int k, int x){ n++;
for(int i=n-1; i>=k-1;i--){ a[i+1]=a[i]; } a[k-1]=x; } int main(){ int n, k, x; int a[1005];
cin>>n>>k>>x;
for(int i=0; i cin>>a[i]; } InserArr(a,n,k,x);
cout< for(int i=0;i cout< } return 0; }
Bài 83. Xóa đi tất cả các phần tử chia hết cho k trong mảng có n phần tử. Đưa ra số phần
tử còn lại và mảng a sau khi xóa.( chú ý chỉ xóa các phần tử không liên tiếp nhau) Bài làm BAI5.INP BAI5.OUT 6 2 3 3 6 5 4 7 2 3 5 7 Bài làm #include using namespace std;
void xoa(int a[], int &n, int k){ for(int i=k+1; i a[i-1]=a[i]; } n--; }
void xoaarr(int a[], int &n, int k){ for(int i=0; i if(a[i]%k==0){ xoa(a,n,i); } } } int main(){ int n, k; int a[1005]; cin>>n>>k;
for(int i=0; i cin>>a[i]; } xoaarr(a,n,k);
cout< for(int i=0;i cout< } return 0; }
Bài 84. Xóa đi phần tử thứ k của mảng a gồm n phần tử. Đưa ra mảng a sau khi xóa. BAI5.INP BAI5.OUT 6 5 5
3 6 5 4 7 2 ( xóa đi phần tử 3 6 5 4 2 thứ 5 là 7) Bài làm #include using namespace std;
void xoa(int a[], int &n, int k){ for(int i=k; i a[i-1]=a[i]; } n--; } int main(){ int n, k; int a[1005]; cin>>n>>k;
for(int i=0; i cin>>a[i]; } xoa(a,n,k);
cout< for(int i=0;i cout< } return 0; }
Bài 85. Liệt kê các dãy con liên tiếp không giảm( có nhiều hơn 1 phần tử ) của dãy ban
đầu, mỗi dãy trên một dòng. BAI5.INP BAI5.OUT 10 1 2 3 4 1 2 3 4 1 5 6 47 8 9 1 5 6 47 8 9 Bài làm #include using namespace std; int n, a[1006]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; } int i=0; int d=0; while(i if(a[i] < a[i+1]){
//neu a[i]la gia tri dau tin cua day so if(d==0){ cout< d++; } else cout< } else { cout< d=0; } i++; } return 0; }
Bài 86. Cho dãy số nguyên n. Nhập vào giá trị x. Tìm vị trí x (nếu có) trong dãy số n phần tử.
Đếm số lượng phần tử có giá trị bằng phần tử vi trí x.Nếu không có thì in ra -1. BAI5.INP BAI5.OUT
6 2 (2 là vị trí phần tử)
2 3 6 ( các vị trí có phần tử bằng 3) 1 3 3 5 7 3 3 ( có 3 phần tử) Bài làm #include using namespace std; int n, x, a[1006]; int main(){ cin>>n>>x;
for(int i=0; i cin>>a[i]; } int tam=a[x-1]; int dem=0; for(int i=0;i if(a[i]==tam){ cout< dem++; } } if(dem==0) cout<<-1; else cout< return 0; }
Bài 87. Tìm dãy 3 phần tử liên tiếp có tổng lớn nhất trong một dãy số có n phần tử(n> 3). Đưa tổng ra màn hình. BAI5.INP BAI5.OUT 6 15 1 3 3 5 7 3 Bài làm #include using namespace std; int n, a[1006], s[1006]; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; }
for(int i=0;i s[i] = a[i]+ a[i+1] + a[i+2]; } int m=s[0]; for( int i=1;i if(m } cout< return 0; }
Bài 88. Tìm giá trị lớn thứ k của dãy số. Nhập vào số lượng phần tử n và vị trí lớn thứ k(1
dòng), dòng 2 là dãy số. Yêu cầu ghi ra vị trí lớn thứ k trong dãy số. BAI5.INP BAI5.OUT 6 3
20 ( số lớn thứ k= 3 của dãy là 20) 27 13 24 19 17 20
( bài tập chỉ đúng trong trường hợp trong dãy không có các số bằng nhau trong thứ k) Bài làm #include using namespace std; int n, k, a[1006], b[1006]; int main(){ cin>>n>>k;
for(int i=0; i cin>>a[i]; } for(int i=0;i b[i] = a[i]; } sort(b, b+n, greater());
if(b[k-1]==b[0]) cout<<-1; else cout< return 0; }
Bài 95. Sử dụng hàm sort để sắp xếp tăng hay sắp xếp giảm trong mảng BAI5.INP BAI5.OUT 9 2 3 3 4 4 5 7 9 9 2 4 3 5 3 7 9 4 9 9 9 7 5 4 4 3 3 2 Bài làm #include using namespace std; int main() { int n; int a[1000]; cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; } // sap xep tang: sort(a, a + n);
for (int i = 0; i < n; i++) {
cout << a[i] << " "; } cout << endl; // Sap xep giam: sort(a, a + n, greater());
for (int i = 0; i < n; i++) {
cout << a[i] << " "; } return 0; }
Bài 96. Tính tổng và tính trung bình cộng các phần tử của một dãy số. Yêu cầu đọc số
phần tử n và dãy số trong file DAYSO.INP, tính toán ghi vào file DAYSO.OUT vào hai dòng:
dòng thứ nhất ghi tổng, dòng thứ hai ghi giá trị trung bình cộng. BAI5.INP BAI5.OUT 6 96 11 21 15 17 13 19 16 Bài làm #include using namespace std; int n, a[1005]; int tong =0; int main() { cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; tong += a[i]; }
cout << tong << endl << (float)tong / n; return 0; }
Bài 96. Đếm xem có bao nhiêu phần tử có giá trị lớn hơn hoặc bằng trung bình cộng của
dãy số, liệt kê các phần tử này. BAI5.INP BAI5.OUT 6 21 17 19 11 21 15 17 13 19
3 16 ( 3 là đếm, 16 là giá trị trung bình) Bài làm #include using namespace std; int main () { int n, a[1000]; cin >> n; int tong = 0;
for (int i = 0; i < n; i++) { cin >> a[i]; tong += a[i]; } float tb = (float)tong / n; int dem = 0;
for (int i = 0; i < n; i++) { if (a[i] >= tb) { dem++;
cout << a[i] << " "; } }
cout << endl << dem << " " << tb; return 0; }
Bài 97. Tìm giá trị lớn nhất nhở nhất của dảy số ( trong 1 vòng lặp for) BAI5.INP BAI5.OUT 10 2 2 4 7 9 5 7 9 4 5 6 9 Bài làm #include using namespace std; int main () { int n, a[1000]; cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; } int min = a[0], max = a[0];
for (int i = 1; i < n; i++) { if(min > a[i]) min = a[i]; if(max < a[i]) max = a[i]; }
cout << min << endl << max; return 0; }
Bài 98. Tìm các vị trí phần tử đạt giá trị nhỏ nhất của dãy. BAI5.INP BAI5.OUT 10 2 5 7 6 3 4 5 3 9 3 6 8 10 Bài làm #include using namespace std; int main () { int n, a[1009]; cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; } int min = a[0];
for (int i = 1; i < n; i++) { if(min > a[i]) min = a[i]; }
for (int i = 0; i < n; i++) {
if (a[i] == min) cout << i + 1 << " "; } return 0; }
Bài 99. Tìm giá trị lớn thứ k của dãy số. Nhập vào số lượng phần tử n và vị trí lớn thứ k (1
dòng), dòng thứ 2 là dãy số. Yêu cầu: Ghi ra vị trí lớn thứ k trong dãy số. BAI5.INP BAI5.OUT 6 3
20 ( 20 lớn thứ 3 trong dãy) 27 13 24 19 17 20
(trường hợp các phần tử trong dãy đôi một khác nhau từ b[k-1] đến b[n-1]) Bài làm #include using namespace std; int main(){ int n, k, a[1000], b[1000]; cin >> n >> k;
for (int i = 0; i < n; i++) { cin >> a[i]; }
for (int i = 0; i < n; i++) { b[i] = a[i]; } sort(b, b+n, greater());
if (b[k-1] == b[0]) cout << -1; else cout << b[k-1]; return 0; }
Bài 100. Tìm dãy 3 phần tử liên tiếp có tổng lớn nhất trong một dãy số có n phần tử (n >
3). Đưa tổng ra màn hình. BAI5.INP BAI5.OUT 8 22 3 4 5 8 9 2 1 1 Bài làm #include using namespace std; int n, a[1006], s[1006]; int main(){ cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; }
for (int i = 0; i < n-2; i++) {
s[i] = a[i] + a[i+1] + a[i+2]; } int m = s[0];
for (int i = 1; i < n-2; i++) { if(m < s[i]) m = s[i]; } cout << m; return 0; }
Bài 101. Bài toán chia kẹo. Có n gói kẹo. Trong mỗi gói có m chiếc kẹo.. Không được bóc
các goi kẹo, hãy chia thành hai phần mà số kẹo hai phân bằng nhau hoặc chênh lệnh ít nhất. BAI5.INP BAI5.OUT 8 3 5 8 3 4 5 8 9 2 1 1 4 9 2 1 1 Bài làm. #include using namespace std; int n,t=0,f[10001],d[10001]; int main(){ cin>>n; int a[n+1]; for (int i=1;i<=n;i++) { cin>>a[i]; t=t+a[i]; } t=t/2; //QHD for (int i=1;i<=t;i++) { f[i]=INT_MAX; for (int j=1;j<=n;j++)
if (i>=a[j] && j>f[i-a[j]]) { f[i]=j; break; } } //Truyvet while (f[t] > n) t--; while (t > 0) { d[f[t]]=1; t=t-a[f[t]]; } for (int i=1;i<=n;i++)
if (d[i]==1) cout< cout<for (int i=1;i<=n;i++) if (d[i]!=1) cout<cout<}
Bài 102. (Bài 67. Cẩm thủy). Thuật toán Kadane Algo. Cho mảng các số nguyên. Tìm dãy
con liên tiếp có tổng các phần tử lớn nhất. Với n<=10000, -10 6<= ai<=10 6 BAI5.INP BAI5.OUT 7 8 1 -2 -1 4 -1 5 -2 Bài làm #include using namespace std; int a[10006]; int n; long long sum1=0, sum2=-1e18; int main(){ cin>>n;
for(int i=0; i cin>>a[i]; for(int i=0;i sum1+=a[i]; sum2=max(sum1,sum2); if(sum1<0)sum1=0; }
cout << sum2 << endl; return 0; }
Bài 102b, đếm và đưa ra dãy đầu tiên có tổng lớn nhất BAI5.INP BAI5.OUT 11 30 1 20 -100 1 2 27 -200 1 6 9 14 1 2 27 Bài làm #include using namespace std; int main() { int n; int a[n+2]; cin>>n;
for(int i=0;i cin>>a[i]; } int maxx = INT_MIN, sum = 0; int dau = 0, cuoi = 0,t = 0;
for (int i = 0; i < n; i++) { if (sum + a[i] < a[i]) { t = i; sum = a[i]; } else { sum += a[i]; } if (maxx< sum) { maxx = sum; dau = t; cuoi = i; } }
cout << maxx << endl;
for(int i=dau;i<=cuoi;i++){
cout << a[i] <<" "; } return 0; } Cach 2 #include using namespace std; int main(){ int n; cin>>n; int a[n];
for(int i=0;i cin >>a[i]; } int MAX=a[0]; int maxx=a[0]; int dau=0; int cuoi=0; int t=0;
for(int i=1;i if(a[i]>MAX+a[i]){ MAX=a[i]; t=i; }else{ MAX+=a[i]; } if(MAX>maxx){ maxx=MAX; dau=t; cuoi=i; } }
cout< for(int i=dau;i<=cuoi;i++) { cout< } return 0; }
Bài 102c, đếm và đưa ra dãy cuối có tổng lớn nhất BAI5.INP BAI5.OUT 11 30 1 20 -100 1 2 27 -200 1 6 9 14 1 6 9 14 Bài làm #include using namespace std; int main() { int n; int a[n+2]; cin>>n;
for(int i=0;i cin>>a[i]; } int maxx = INT_MIN, sum = 0;
int dau = 0, cuoi = 0,start = 0;
for (int i = 0; i < n; i++) { if (sum + a[i] < a[i]) { start = i; sum = a[i]; } else { sum += a[i]; } if (maxx<= sum) { maxx = sum; dau = start; cuoi = i; } }
cout << maxx << endl;
for(int i=dau;i<=cuoi;i++){
cout << a[i] <<" "; } return 0; }
Bài 103. (bài 81). Cho một dãy số nguyên. Hãy liệt kê và đếm số lần xuất hiện của các phần tử trong mảng. BAI5.INP BAI5.OUT 9 2 2 2 4 5 2 4 6 3 4 5 4 3 5 2 6 1 3 1 Bài làm #include using namespace std; int a[1000007]; map m; int n; int main() { cin>>n; for(int i=1; i<=n;i++) { cin>>a[i]; m[a[i]]++; } for(int i=1; i<=n; i++) if(m[a[i]]!=0){ cout< m[a[i]]=0;} return 0; }
b. liệt kê các số xuất hiện 1 lần #include using namespace std; int a[100006]; map m; int n; int main() { cin>>n; for(int i=1; i<=n;i++) { cin>>a[i]; m[a[i]]++; } for(int i=1; i<=n; i++) if(m[a[i]]==1){ cout< } return 0; }
c. tìm số có tần xuất xuất hiện nhiều nhất. In ra số đó và số lần xuất hiện. Nếu có nhiều số bằng
nhau thi in ra số đầu tiên của dãy. #include using namespace std; int a[1000007]; map m; int n; int main() { cin>>n; for(int i=1; i<=n;i++) { cin>>a[i]; m[a[i]]++; } int maxx=1; for(int i=1; i<=n; i++) if(m[a[i]]>maxx){ maxx=m[a[i]]; cout< m[a[i]]=0;} return 0; }
Bài 110. Tính n!. Với n<= 100. BAI5.INP BAI5.OUT 10 3628800 Bài làm #include using namespace std; int a[200]; int main(){ int i,n,nho,tam; cin>>n; a[1]=1;tam=n; for (int j=2;j<=200;j++); n=tam;nho=0; for (int i=1;i<=n;i++) for (int j=1;j<=190;j++) { tam=a[j]; if (a[j]*i+nho>=10) { a[j]=(a[j]*i+nho)%10; nho=(tam*i+nho)/10; } else { a[j]=a[j]*i+nho; nho=0; } } for (int i=190;i>=1;i--) if (a[i]!=0) {tam=i;break;} for (int i=tam;i>=1;i--) cout< return 0; } Cach 2. Đến n= 270 #include using namespace std; int a[400]; int n, nho, tam; int main() { cin>>n; a[1]=1;tam=n; for (int j=2;j<=n;j++); n=tam;nho=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ tam=a[j]; if (a[j]*i+nho>=100) { a[j]=(a[j]*i+nho)%100; nho=(tam*i+nho)/100; } else { a[j]=a[j]*i+nho; nho=0; } } for (int i=n;i>=1;i--) if (a[i]!=0) {tam=i;break;} for (int i=tam;i>=1;i--) {
if (a[i]>=10) cout << a[i]; else cout<< a[i]; } return 0; }
Bài . tìm dãy con liên tiếp có số lượng phần tử dài nhât và tổng bằng 0
Cách 1. Đưa ra số lượng phần tử của dãy con và dãy con #include using namespace std;
long long n,a[1000002],maxn=0,dau,cuoi; long long tong(int x,int y) {long long t=0; for(int i=x;i<=y;i++) t=t+a[i]; return t; } int main() {cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
if(tong(i,j)==0&&j-i+1>maxn) {maxn=j-i+1;dau=i;cuoi=j;}
cout < for(int i=dau;i<=cuoi;i++) cout< return 0; }
Cách 2. Đưa ra vị trí của dãy con. #include using namespace std; long long s; int n, len; int p=-1; int a[1009]; map m; int main() { cin >> n;
for (int i = 1;i <= n;i++) { cin >> a[i]; s += a[i]; if (s == 0) { p = 0; len = i; } if (m[s]) { if (i - m[s] > len) { len = i - m[s]; p = m[s]; } } else { m[s] = i; } } if (p != -1) {
cout << p + 1 << ' ' << p + len; } else { cout << -1; } return 0; }
Bai Sàng số nguyên tố trong đoạn từ m đến n. Với số lượng 10 6 phần tử đến 10 9 . #include using namespace std; int m,n; int main(){ cin>>m>>n; int a[10001]={0}; a[0]=1; a[1]=1; for(int i=2;i<=100;i++){ if(a[i]==0){
for(int j=i*i;j<=10000;j+=i){ a[j]=1; } } } for(int i=m;i<=n;i++){ if(a[i]==0) cout< } return 0; } Bộ test #include using namespace std; int m,n; int main(){ int test; cin>>test; while(test--){ cin>>m>>n; int a[10001]={0}; a[0]=1; a[1]=1; for(int i=2;i<=100;i++){ if(a[i]==0){
for(int j=i*i;j<=10000;j+=i){ a[j]=1; } } } for(int i=m;i<=n;i++){ if(a[i]==0) cout< } } return 0; }
Bài 1. Mảng cộng dồn.
Cho mảng các số nguyên, thực hiện tính toán tổng các phần tử trong đoạn từ vị trí L tới vị trí R trong mảng.
Input: - dòng đầu tiên là số lượng phần tử trong mảng n.(1<=n<=10 5 ). -
Dòng thứ 2 là các phần tử ai trong mảng. -10 9<=ai<=10 6 -
Dòng thứ 3 là số lượng truy vấn q. (1<=q<=1000)
q dòng tiếp theo, mỗi dòng là 2 vị trí L, R (1<=L<=R<=1000)
Output: in ra giá trị cho từng truy vấn. BAI5.INP BAI5.OUT 10 1 2 3 4 5 6 7 8 9 10 3 6 1 3 55 1 10 14 2 5 Bài Làm
Cach 1. Độ phức tạp ( nếu 3 truy vấn thì độ phức tạp là 3 vòng for O(n 3) #include using namespace std; int a[1001]; int n; int main(){ cin>>n;
for(int i=0;i cin>>a[i]; } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; long long sum=0;
for(int i=l-1; i<=r-1; i++){ sum+=a[i]; } cout< } return 0; }
Cách 2. Mảng cộng dồn có độ phức tạp là O(n). #include using namespace std; int main(){ int n; cin>>n; int a[n+1]; for(int i=1;i<=n; i++){ cin>>a[i]; } int prefix[n+1]={0}; for(int i=1;i<=n; i++){ prefix[i] = prefix[i-1]+a[i]; } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; cout< } return 0; }
Bài 2. Hai for tịnh tiến.Cho dãy gồm N số nguyên khác không: a1, a2, ..., an. Hãy tìm dãy con
gồm nhiều phần tử nhất có tính chất cùng dương hoặc cùng âm(nếu có) từ dãy đã cho. Biết rằng
: dãy con là một dãy các phần tử liên tiếp nhau nằm trong dãy ban đầu.
Dữ liệu vào: Cho tệp văn bản bai2.inp gồm hai dòng:
+ dòng 1: số nguyên dương N.( vói 1< N<=100)
+ dòng 2: N số nguyên dương khác 0.
Dữ liệu ra: ghi vào tệp văn bản bai2.out gồm một dòng: hai số L, D( nếu có), với L: là số lượng
phần tử của dãy con có tính chất cùng dương hoặc cùng âm, D: là vị trí bắt đầu của dãy con tìm
được. Nếu không có dãy con nào thỏa mãn điều kiện thì ghi kết quả là -1. BAI2.INP BAI2.OUT 10 5 1 1 2 3 4 5 -6 -7 8 9 10 BAI2.INP BAI2.OUT 10 -1 1 -2 3 -4 5 -6 7 -8 9 -10 #include using namespace std; int n, a[102]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>> a[i]; int ans = -1; int vt=0; for(int i = 1; i<=n; i++){ int L=0; for(int j=i;j<=n;j++){ if(a[i]<0){ if(a[j]<0) L++; else break ; } else if(a[i]>0){ if(a[j]>0) L++; else break; } } if((ans1) { ans =L; vt=i; } }
if(ans>0) cout< else cout< return 0; }
Bài 4.(Mảng map. Vì lớn đến a[i] =10 18 nên không dùng mảng đánh dấu mà dùng mảng
map.) cho mảng A[] gồm n phần tử. Hãy sắp đặt lại các phần tử của mảng sao cho A[i] =i, nếu
A[j] có giá trị khác j, hãy ghi vào -1. Ví dụ với mảng A[]={-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}. Ta có
kết quả A[]={-1, 1, 2, 3, 4, -1, 1, 1, -1, -1, 9} A[9] =9 vì 9 xuất hiện trong mảng A[].
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[]. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 7 . 1<=A[i]<=10 18
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 10 -1 1 2 3 4 -1 6 -1 -1 9 -1 -1 6 1 9 3 2 -1 4 -1 0 1 -1 3 -1 -1 6 0 -3 1 -2 3 -4 Bài làm #include using namespace std; using ll = long long; int main(){ int test; cin>>test; while (test--){ int n; cin>>n; mapmp;
for(int i=0;i ll x; cin>>x; mp[x]=true; } for(int i=0; i if(mp[i]){ cout< } else cout<<"-1 "; } cout< } return 0; }
Bài 5. Mảng đánh dấu (hoăc mảng map). Cho mảng A gồm n số nguyên bao gồm cả số 0. Tìm
số nguyên dương nhỏ nhất không có mặt trong mảng. Ví dụ A[5]= {5,8,3,7,9,1} ta có kết quả là số 2.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[]. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 6 . - 10 6<=A[i]<=10 6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 5 6 1 2 3 4 5 2 5 0 -10 1 3 -20 Bài làm #include using namespace std; int cnt[1000002]; int main(){ int test; cin>>test; while (test--){ int n; cin>>n; memset(cnt, 0,sizeof(cnt));
for(int i=0;i int x; cin>>x; if(x>0) cnt[x]=1; }
for(int i=1; i<=1000001; i++){ if(cnt[i]==0){ cout< break; } } } return 0; } Bài 6 Khoảng .
cách nhỏ nhất.Cho mảng A gồm n phần tử chưa được sắp xếp. Hãy tìm min(A[i]-A[j])
(không âm):i#j và i, j= 0,1, 2, ....,n-1. Ví dụ: A[] = {1,5,3,19,18,25] ta có kết quả là 1=19-18.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[]. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 3 . - 10 3<=A[i]<=10 3
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 5 1 2 4 5 7 9 6 10 87 32 99 75 56 43 21 10 68 49 Bài làm
Cách 1. Độ phức tạp là O(n 2 ) #include using namespace std; int main(){ int T; cin>>T; while (T--){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; } int res= INT_MAX;
for(int i=0; i for(int j=i+1; j res= min(res,max(a[i],a[j])-min(a[i],a[j])); } } cout< } return 0; }
Cách 2. Sắp xếp tăng dần có độ phức tạp là O(n.logn) #include using namespace std; int main(){ int T; cin>>T; while (T--){ int n; cin>>n; int a[n];
for(int i=0;i cin>>a[i]; } sort(a, a+n); int res= INT_MAX;
for(int i=1; i res= min(res, a[i]- a[i-1]); } cout<} return 0; }
Bài 7. Cho mảng A gồm n phần tử, liệt kê k phần tử lớn nhất.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[] và số k. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 6 . 1<=A[i]<=10 6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 12 10 9 5 3 12 9 10 7 9 12 6 6 2 9 7 12 8 6 5 Bài làm #include using namespace std; int main(){ int test; cin>>test; while (test--){
int n, k ; cin>>n>>k; int a[n]; for(int i=0;i>a[i]; sort(a, a+n,greater()); for(int i=0; i cout< } cout< } return 0; }
Bài 8. Cho mảng A gồm n phần tử, liệt kê k phần tử lớn nhất theo thứ tự tăng dần.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[] và số k. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 6 . 1<=A[i]<=10 6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 9 10 12 5 3 9 12 10 7 9 12 6 6 2 9 7 12 8 6 5 Bài làm #include using namespace std; int main(){ int test; cin>>test; while (test--){
int n, k ; cin>>n>>k; int a[n]; for(int i=0;i>a[i]; sort(a, a+n,greater()); for(int i=k-1; i>=0; i--){ cout< } cout< } return 0; }
Bài 9. Cho mảng A gồm n phần tử. hãy đếm số phần tử xuất hiện ít nhất 1 lần.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[] và số k. Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 6 . 1<=A[i]<=10 6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 2 2 5 4 4 5 12 1 6 10 20 30 30 20 5 Bài làm Cách 1. Mảng đếm #include using namespace std; int cnt[1000001]; int main(){ int test; cin>>test; while (test--){ int n ; cin>>n; int a[n]; memset(cnt, 0, sizeof(cnt));
for(int i=0;i cin>>a[i]; cnt[a[i]]++; } int dem=0;
for(int i=0; i if(cnt[a[i]]>=2) ++dem; } cout< } return 0; } Cách 2. Mảng map. #include using namespace std; int main(){ int test; cin>>test; while (test--){ int n ; cin>>n; int a[n]; mapmp;
for(int i=0;i cin>>a[i]; mp[a[i]]++; } int dem=0;
for(int i=0; i if(mp[a[i]]>=2) dem++; } cout < } return 0; }
Bài 10. Cho mảng A gồm n phần tử.Hãy tìm ước chung lớn nhất của hai phần tử bất kỳ trong mảng.
Dữ liệu vào: + dòng đầu tiên đưa ra số lượng bộ test T.
+ những dòng kế tiếp đưa vào T bộ test gồm hai dòng: dòng đầu tiên đưa vào n là số phần tử
của mảng A[] . Dòng kế tiếp đưa vào n số A[i] của mảng.
+ T, n, A[i] thỏa mãn ràng buộc : 1<=T<=100. 1<=n<=10 3 . 1<=A[i]<=10 6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng. BAI4.INP BAI4.OUT 1 10 7 2 3 1 4 5 7 14 3 5 10
Cach 1. Độ phức tạp là n 2 #include using namespace std; int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b); } const int maxn=1001; int a[maxn]; int main(){ int t; cin>>t; while(t--){ int n; cin>>n;
for(int i=0; i cin>>a[i]; int res =1;
for(int i=0; i for(int j=i+1; j res=max(res,gcd(a[i], a[j])); } } cout<< res< } return 0; }
Cách 2. Dùng mảng map để đếm tần suất xuất hiện của các ước trong mảng. Độ phức tạp là n.logn. #include using namespace std; const int maxn=1001; int a[maxn]; mapmp; void solve(int n){
for(int i=1;i<=sqrt(n);i++){ if(n%i==0){ mp[i]++; if( i!=n/i) mp[n/i]++; } } } int main(){ int t; cin>>t; while(t--){ int n; cin>>n;
for(int i=0; i cin>>a[i]; solve(a[i]); } int res =1; for( auto it:mp){ if(it.second>=2){ res=it.first; } } cout<< res< } return 0; }
Bài 15. Cho mảng gồm n phần tử. Đếm các số nguyên không phải là số nguyên tố trong
mảng. Với n<= 10 5 và 10<= ai <=20 . BAI4.INP BAI4.OUT 8 4 12 13 15 17 19 18 11 12 Bai lam #include using namespace std; int n, a[100005]; int main(){ bool f[21]; for(int i=10;i<=20;i++) f[i]=true; f[11]=false; f[13]=false; f[17]=false; f[19]=false; cin>>n; int kq=0; for(int i=1;i<=n;i++){ cin>>a[i]; if(f[a[i]]) kq++; } cout << kq; return 0; }
Bài 16. Mảng cộng dồn. Cho mảng A gồm n phần tử. Cho T cặp L, R. Hãy in ra tổng các
phần tử từ A L đến A R (L<=R). Bài làm
int A[n];( nhập mảng A gồm n phần tử)
int S[n];(khởi tạo mảng S[] có độ dài n) S[0] =A[0];
for(int i=1; i S[i]= S[i-1] + A[i];
Bài 17. Thuật toán sắp xếp nổi bọt. Đưa phần tử lớn nhất về cuối dãy.( bài toán sắp xếp lại
hàng rào). Độ phức tạp O 2. int arr[], n; bool check= true; for( int i=0; i{ check= false;
for( j =0 ; j if(arr[j]{ check = true; swap(arr[j], arr[j+1]); } }
Bài 18. Thuật toán sắp xếp chọn. Đưa phần tử nhỏ nhất về đầu dãy. Độ phức tạp là O 2 int arr[], n; int min_id; for(int i=0; i{ int min_id =i;
for(int j = i+1; j if(arr[j] < arr[min_id]) min_id = j; swap(arr[min_id], arr[i]); }
Bài 19. Cho mảng A gồm n số nguyên. Tính tổng chênh lệch của hai số nguyên liên tiếp
trong dãy số. Với q truy vấn. BAI4.INP BAI4.OUT 8 8 12 13 15 17 19 18 11 12 15 3 5 1 6 2 8 3 6 Bài làm #include using namespace std; int main(){ int n; cin>>n; int a[n+1]; for(int i=1;i<=n; i++){ cin>>a[i]; } int tongdu[n+1]={0}; for(int i=2;i<=n; i++){
tongdu[i] = tongdu[i-1]+ (max(a[i],a[i-1])- min(a[i],a[i-1])); } int q; cin>>q; while(q--){ int l, r; cin>>l>>r; cout< } return 0; }
Bài 20.(quy hoạch động). Cho tập A gôm n phần tử. Hãy kiểm tra xem ta có thể chia tập A
thành 2 tập con có tổng các phần tử bằng nhau hay không. Đưa ra yes nếu thực hiện được
, ngược lại đưa ra no.
Input – dòng đầu tiên đưa vào số lượng bộ test t -
Những dòng tiết theo đưa vào các bộ test t. Mỗi bộ test t gồm 2 phần: -
Phần thứ nhất đưa vào số n phần tử của dãy A. -
Dòng thứ hai đưa vào n phần tử của dãy số A. -
1<= t<=100, 1<=n<=100, 1<=A[i]<=100 Ouput BAI4.INP BAI4.OUT 2 Yes 4 No 1 5 11 5 3 1 3 5 Bài làm #include using namespace std; int main(){ int t; cin>>t; while(t--){ int n; int sum=0; cin>>n; int a[n+5];
for(int i=0; i cin>>a[i]; sum+=a[i]; }
if(sum%2==1) cout<<"no"; else { int s=sum/2; int dp[s+1]={0}; dp[0]=1;
for(int i=0;i for(int j=s; j>=a[i]; j--){ if(dp[j-a[i]]==1) dp[j]=1; } }
if( dp[s]==1) cout<<"yes"; else cout<<"no"; } cout< } return 0; }
Bài 21. (quy hoạch động).Cho mang A gồm n phần tử và số nguyên dương s. Hãy xác định
xem có thể tạo ra một tập con các phần tử trong mảng có tổng bằng s hay không. Chú ý
mỗi phần tử trong mảng chỉ được sử dụng 1 lần.
1<=n<=200. 1<=s<=50000. 1<=a[i]<=500.
In ra 1 nếu có tập co bằng s, ngược lại in ra 0. BAI4.INP BAI4.OUT 8 92 1 69 16 82 170 31 24 45 112 Cách 1 #include using namespace std; int main(){ int n, s; cin>>n>>s; vectora(n); for(int i=0; i>a[i]; vector dp(s+1, false); dp[0]=true;
for(int i=0;i for(int j=s; j>=a[i]; j--){
if(dp[j-a[i]]==true) dp[j]=true; } }
if( dp[s]==true) cout<< 1 < else cout<<0< return 0; } Cách 2. #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0; i>a[i]; bool dp[s+1]={0}; dp[0]=1;
for(int i=0;i for(int j=s; j>=a[i]; j--){ if(dp[j-a[i]]==1) dp[j]=1; } }
if( dp[s]==1) cout<< 1 < else cout<<0< return 0; } Cach 3. #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0; i>a[i]; int dp[s+1];
for(int i=0; i<=s;i++) dp[i]=0; dp[0]=1;
for(int i=0;i for(int j=s; j>=a[i]; j--){ if(dp[j-a[i]]==1) dp[j]=1; } } cout< return 0; }
Bài 22.(quay lui có cận). Cho mảng A gồm n phần tử. Hãy chia mảng A thành k tập con
khác rỗng sao cho tổng các phần tử của mỗi tập con đều bằng nhau. Mỗi phần tử thuộc tập con
xuất hiện duy nhất một lần trong tất cả các tập con. Ví dụ: A[]={2,1,4,5,6}, k=3. Ta có kết quả{2,4}, {1, 5}, {6}.
Input – dòng đầu tiên đưa vào số lượng bộ test t. -
Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai phần:
Phần thứ nhất là hai số n và k. Dòng tiếp theo đưa vào n số của mảng A.
1<=t<=100. 1<=n, k<=20. 1<=A[i]<=100 BAI4.INP BAI4.OUT 2 1 5 3 0 2 1 4 5 6 5 3 2 1 5 5 6 Bài làm #include using namespace std; int n, k; int a[101], s; int dem=0; bool ok[101]; bool check= false; void Try(int sum, int dem){ if(check == true) return; if( dem==k){ check=true; return; } for(int i=1; i<=n; i++){ if(ok[i]==false){ ok[i]=true; if(sum==s){ Try(0,dem+1); return; } if(sum>s) return; else Try(sum+a[i], dem); } ok[i]=false; } } int main(){ int t; cin>>t; while(t--){ s=0; check=false; cin>>n>>k; for(int i=1; i<=n; i++){ cin>>a[i]; ok[i]=false; s+=a[i]; } if(s%k!=0) cout<<0; else{ s/=k; Try(0,0);
if(check==true) cout<<1; else cout<<0; } cout< } return 0; }
Bài 23. (sàng số nguyên tố). Cho số nguyên dương n. Hãy đưa ra các số nguyên tố từ 1 đến n. Bài làm #include const int N=1e6+2; using namespace std; int kt[N]; int n; int main(){ cin>>n; for(int i=0; i<=n; i++){ kt[i]=true; kt[0]=kt[1]=false; }
for(int i=2;i<=sqrt(n); i++){ if(kt[i]){ for(int j=i*i; j<=n;j+=i){ kt[j]= false; } } } for(int i=0; i<=n; i++) { if(kt[i]==true) cout< } return 0; }
Bài 24. Dãy con liên tiếp có tổng bằng S, dãy con liên tiếp lồng nhau. BAI4.INP BAI4.OUT 10 7 2 5 2 5 3 4 1 2 4 6 1 2 3 4 4 1 2 1 2 4 6 1 Bài làm #include using namespace std; int n, s; int a[105]; int sl; int main(){ cin>>n; cin>>s;
for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i sl=0; sl=sl+a[i]; for(int j=i+1; j<=n; j++){ sl=sl+a[j]; for(int k=i; k<=j; k++){ if(sl==s) cout< } cout<} } return 0; } Cach 2. Tôi ưu hơn cách 1. #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0;i cin>>a[i]; } int prefixSum[n];
for (int i = 0; i prefixSum[i] = prefixSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) { for (int j = i; j int sum;
sum = prefixSum[j] - prefixSum[i-1]; if (sum == s) { int k=i ; int m=j; for(int i=k; i<=m; i++) cout< cout< } } } return 0; }
Bài 25. Đếm Dãy con liên tiếp có tổng bằng S, dãy con liên tiếp lồng nhau. BAI4.INP BAI4.OUT 10 7 5 2 5 3 4 1 2 4 6 1 2 Bài làm #include using namespace std; map ma; map :: iterator it;
int tong(int a[], int x, int y){ int sum=0; for(int i=x; i return sum; }
void kt(int a[], int n, int k){ for(int j=1; j<=n; j++)
for(int i=0; i ma[tong(a, i, j)]++;
for (it = ma.begin(); it != ma.end(); it++)
if(it->first == k) cout<second; } main(){ int n, k; cin>>n>>k; int a[n]; for(int i=0; i>a[i]; kt(a, n, k); return 0; } Cach 2 #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0;i cin>>a[i]; } int d = 0; int prefixSum[n];
for (int i = 0; i < n; i++) {
prefixSum[i] = prefixSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) { for (int j = i; j int sum;
sum = prefixSum[j] - prefixSum[i-1]; if (sum == s) { d++; } } } cout< return d; }
Bài 25. Tối ưu hơn 2 bài trên.Đưa ra và đếm: Dãy con liên tiếp có tổng bằng S, dãy con liên tiếp lồng nhau. BAI4.INP BAI4.OUT 15 15 2 3 10
2 3 10 7 8 6 5 2 8 9 17 -2 0 5 10 7 8 5 2 8 17 -2 17 -2 0 0 5 10 5 10 7 Bai lam #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0;i cin>>a[i]; } int d=0; int prefixSum[n];
for (int i = 0; i prefixSum[i] = prefixSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) { for (int j = i; j int sum;
sum = prefixSum[j] - prefixSum[i-1]; if (sum == s) { d++; int k=i ; int m=j; for(int i=k; i<=m; i++) cout< cout< } } } cout<< d; return 0; }
Bài 26. Dãy con liên tiếp có tổng lớn hơn hoặc bằng S.dãy con không lồng nhau. Đề
chuyên lam sơn năm 2023.Kiểm tra lại sự đúng. BAI4.INP BAI4.OUT 10 18 2 5 1 3 9 10 7 4 9 2 8 5 27 2 3 5 1 9 -1 Bài làm #include using namespace std; long long f[100009]; long long s; int n, a; bool check(int k){
for(int i=1; i<=n-k+1; i++){ if(f[i+k-1]-f[i-1]>=s){ return true; } } return false; } int main(){ cin>>n>>s; f[0]=0; for(int i=1; i<=n;i++){ cin>>a; f[i]=f[i-1]+a; } int ans=-1; int l=1; int r=n; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=mid; r=mid - 1; } else l=mid +1; } cout << ans; return 0; }
Bài 28. Sắp xếp lại hàng rào theo thư tự tăng dần sau khi bảo đã làm đổmột số thanh gỗ.
Mỗi lần hoán đổi vị trí hai thanh gỗ thì đếm tăng lên một. N<=1000và a[i]<=1000. BAI4.INP BAI4.OUT 5 1 2 5 3 3 5 5 2 (4 3 2 5 6--- 2 3 4 5 6) 6 3 2 5 4 Bài làm #include using namespace std; int n; int a[100]; int c=0; int main(){ cin>>n; for(int i=1;i<=n; i++){ cin>>a[i]; } for(int i=n;i>0;i--){ int max1=a[i], csmax=i; for(int j= i-1;j>0;j--){ if(max1<=a[j]) { max1=a[j]; csmax=j; } } if(a[i]!= a[csmax]){ int tmp=a[csmax]; a[csmax]=a[i]; a[i]=tmp; c++; } } cout< return 0; }
Bài30. Đếm số lượngphần tử của dãy con liên tiếp dài nhất có tổng chia hết cho k. BAI29.INP BAI29.OUT 18 8 16
1 2 3 4 5 6 7 8 8 8 9 4 4 3 3 8 8 8
3 4 5 6 7 8 8 8 9 4 4 3 3 8 8 8 Bài làm #include using namespace std;
long long n,a[1000002],maxn=0,k,dau,cuoi; long long tong(int x,int y) {long long t=0; for(int i=x;i<=y;i++) t=t+a[i]; return t; } int main() {cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
if(tong(i,j)%k==0&&j-i+1>maxn) {maxn=j-i+1;dau=i;cuoi=j;}
cout < for(int i=dau;i<=cuoi;i++) cout< return 0; } Cah 2. #include using namespace std;
long long n,a[1000002],maxn=0,k, dau,cuoi; long long tong=0; int main(){ cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ tong=a[i]; for(int j=i+1;j<=n;j++){ tong =tong +a[j];
if(tong%k==0&&j-i+1>maxn){ maxn=j-i+1;dau=i;cuoi=j; } } }
cout < for(int i=dau;i<=cuoi;i++) cout< return 0; }
Bài 32. đếm Dãy con liên tiếp có tổng bằng S, dãy con liên tiếp không lồng nhau. BAI4.INP BAI4.OUT 15 15 5
2 3 10 7 8 6 5 2 8 9 17 -2 0 5 10 Bai lam Cách 2, thu gọn #include using namespace std;
int a[1005], n, s, dem=0, tong=0; int main(){ cin>>n>>s; for(int i=1;i<=n;i++) cin>>a[i];
for (int i =1; i<=n; i++) { tong=a[i];
for (int j =i+1; j <=n; j++) { tong=tong+a[j]; if (tong == s) { dem++; tong=0; i=j; } } } cout<< dem; return 0; } Cách 3.10 10 1 2 3 4 10 4 10 5 10 9 #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0;i cin>>a[i]; } int d=0; int prefixSum[n];
for (int i = 0; i prefixSum[i] = prefixSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) { for (int j = i; j int sum=0;
sum = prefixSum[j] - prefixSum[i-1]; if (sum == s) { d++; sum=0; i=j; } } } cout<< d; return 0; } Cách 3. Tối ưu nhất #include using namespace std; int main(){ int n, s; cin>>n>>s; int a[n]; for(int i=0;i cin>>a[i]; } int d=0; int SSum[n];
for (int i = 0; i SSum[i] = SSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) { for (int j = i; j int sum=0; sum = SSum[j] - SSum[i-1]; if (sum == s) { d++; sum=0; i=j; } } } cout<< d; return 0; } Cách 4. Tối ưu nhất #include using namespace std;
int n, s, a[1008],SSum[1008],d=0,sum=0; int main(){ cin>>n>>s; for(int i=0;i cin>>a[i]; }
for (int i = 0; i SSum[i] = SSum[i-1] + a[i]; }
for (int i = 0; i < n; i++) {
for (int j = i; j sum = SSum[j] - SSum[i-1]; if (sum == s) { d++; sum=0; i=j; } } } cout<< d; return 0; }
Bài 33. Bạn An sắp xếp các số từ 1,2,3,...n một cách tùy ý vào n vị trí và được dãy số
P( hay còn gọi là một hoán vị của các số1 ,2 ,3..,n). Quan sát dãy số P, lấn lượt với mỗi giá trị
i(i=1,2 , 3...n)An thực hiện ghi lại số các số lớn hơn i và đứng trước bên trái i trong dãy P và
được dãy T gồm n số. An đưa dãy số T cho bạn thắng và yêu cầu thực hiện dãy số P ban đầu từ
dãy số T này. Em hãy lập trình giúp Thắng giải quyết bài toán này:
Dữ liệu vào: từ file DAYSO.INP gồm hai dòng:
- Dòng đầu chứa số tự nhiên N.(1- Dòng hai chứa N số tự nhiên của dãy T, các số cách nhau một dấu cách.
Dữ liệu ra: ghi ra file DAYSO.OUT là một dãy gồm N số mô tả dãy P ban đầu, các số ghi cách nhau một dấu cách. BAI4.INP BAI4.OUT 4 3 2 1 4 2 1 0 0 6 5 1 0 1 1 0 3 2 6 4 5 1 Bài làm #include #define N 110 using namespace std; int a[N],t[N],n,vt,dem=0; int main() { cin >>n; for(int i=1;i<=n;i++){ cin >>t[i]; a[i]=0; } for (int i=1;i<=n;i++){ vt=t[i]+1; for (int j=1;j<=n;j++){ if (a[j]==0){ dem++; if (dem==vt) a[j]=i; } } dem=0; }
for(int i=1;i<=n;i++) cout < return 0; }
Bài 39. Cho dãy số gồm n phần tử. Tìm đoạn con ngắn nhất các phần tử liên tiếp nhau sao
cho đoạn con đó chứa phần tử lớn nhất và phần tử bé nhất. 1<=n<=10 5 và |ai|<=2.109 BAI1.INP BAI1.OUT 10
3 (khoảng cách giữa phần tử lớn nhất và 1 2 3 4 9 2 2 1 6 9 bé nhất) Bài làm #include #define N 100005 using namespace std;
int a[N],n,kq=1e5+1,b[N],c[N],m=0,k=0; long long MIN=1e10,MAX=-1e10; int main(){ cin >>n; for (int i=1;i<=n;i++){ cin >>a[i]; } for (int i=1;i<=n;i++){ if (MIN>=a[i]) MIN=a[i]; if (MAX<=a[i]) MAX=a[i]; } for(int i=1;i<=n;i++){ if (a[i]==MIN){ k++; b[k]=i; } if (a[i]==MAX){ m++; c[m]=i; } } for (int i=1;i<=k;i++){ for (int j=1;j<=m;j++){ int minn=abs(b[i]-c[j])+1; if (minn kq=minn; } } } cout < return 0; }
Bài 50. Trong một cuộc thi ban giám khảo chuẩn bị một màn hình lớn, người ta cho lần
lượt xuất hiện các số của một dãy số nguyên dương a1, a2, ..., an. Và cứ lặp lại như thế không
ngừng(nghĩa là đầu tiên xuất hiện a1, rồi đến a2,....,an, a1, a2,.....)
Yêu cầu: bạn hãy giúp ban tổ chức tính tổng k số liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên xuất hiện thứ p.
Dữ liệu: dòng thứ nhất ghi các số nguyên dương n, k, p.
Dòng thứ hai ghi n số nguyên dương a1, a2,......an (1<=ai<=10 9 ) BAI1.INP BAI1.OUT 5 7 6 32
7 số nguyên liên tiếp xuất hiện trên 2 3 6 7 9
màn hình bắt đầu từ số xuất hiện thứ 6 là 2 3 6 7 9 2 3 Bài làm. #include using namespace std;
int tong(int a[], int n, int p, int k){ int sum = 0;
for(int i=p; i
if(i%n==0) sum += a[n]; sum += a[i%n]; } return sum; } int main(){ int n, k, p;
cin>>n>>k>>p; int a[n]; for(int i=1; i<=n;i++){ cin>>a[i]; } int sum = tong(a, n, p, k); cout << sum; return 0; }
Bài 52. Cho dãy số nguyên gồm n phần tử a1,a2,⋯,an ⋯
(|ai|≤ 10 9 ). Cho giá trị x và q câu
hỏi có dạng S(u,v). Với S(u,v) là tổng các giá trị của các phần tử từ u đến v. Yêu cầu: Đếm xem
trong q câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn x.
Input • Dòng đầu tiên chứa ba số nguyên dương n,x,q (x≤10 9 , q≤10 5 ).
• Dòng thứ hai chứa a1,a2,⋯,an(|ai|≤10 5 ).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,v(1≤u≤v≤n). Output • In ra một
số nguyên là số lượng câu hỏi có giá trị nhỏ hơn x BAI1.INP BAI1.OUT 5 6 3 2 7 2 1 6 5 2 3 3 4 5 5 Bài làm #include using namespace std; int n, x, q; int dem=0; int main(){
cin>>n>>x>>q; int a[n+1]; for(int i=1;i<=n; i++){ cin>>a[i]; } int prefix[n+1]={0}; for(int i=1;i<=n; i++){ prefix[i] = prefix[i-1]+a[i]; } while(q--){ int u, v; cin>>u>>v;
if((prefix[v]- prefix[u-1]) < x) dem++; }
cout<< dem<< endl; return 0; }
Bài 62. Cho dãy số nguyên dương n. Với n<=10 5 . ai<=10 9 . Tìm số nguyên tố lớn thứ 2 trong dãy số đó. BAI1.INP BAI1.OUT 10 7 2 3 4 7 2 11 7 5 11 10 Bài làm #include #define N 100005 using namespace std; bool check(int n){ if (n<2) return false; for (int i=2;i*i<=n;i++){ if (n%i==0) return false; } return true; } int main(){ int a[N],n,maxx1=-1, maxx2=0; cin >>n; for(int i=1;i<=n;i++){ cin >>a[i]; } for (int i=1;i<=n;i++){
if((check(a[i])==true)&&(a[i]>maxx1)){ maxx1=a[i]; } } for(int i=1;i<=n;i++){
if((check(a[i])==true)&&(a[i]!=maxx1)&&(a[i]>maxx2)){ maxx2=a[i]; } } cout< return 0; } Cách 2. #include #define N 100005 using namespace std; bool check(int n){ if (n<2) return false; for (int i=2;i*i<=n;i++){ if (n%i==0) return false; } return true; } int main() { int a[N],b[N],n,dem=0; cin >>n; for(int i=1;i<=n;i++){ cin >>a[i]; } for (int i=1;i<=n;i++){ if (check(a[i])==true){ dem++; b[dem]=a[i]; } } if (dem==0)cout <<0;
else if (dem==1) cout < else{ sort(b+1,b+dem+1,greater()); if (dem==2){ cout < return 0; } for (int i=2;i<=dem;i++){ if (b[1]!=b[i]) { cout < return 0; } } } return 0; }
Bài 65. Hà Tĩnh. Cho dãy A gồm N số nguyên dương a1, a2, a3,...an. Hãy thực hiện các yêu cầu sau:
- Tìm đoạn con có trọng số lớn nhất. Trọng số của đoạn con liên tiếp được tính bằng phần
nguyên trung bình cộng của đoạn con đó.
- tìm số xuất hiện nhiều lần nhất trong dãy, nếu có nhiều đáp án thì lấy số nhỏ nhất.
1<= N, ai <=105 . 1<=i<=N. BAI1.INP BAI1.OUT 5 4 2 3 3 4 4 3 Bài làm #include #define N 100005 using namespace std; int cnt[N]={0}; int n, a[N]; int dem=0, res; int tong=0, s=0; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; cnt[a[i]]++; }
for (int i =1; i<=n; i++) { tong=a[i];
for (int j =i+1; j <=n; j++) { tong=tong+a[j]; tong=tong/(j-i+1); if (tong > s) s=tong; } }
cout< for(int i=1;i<=n;i++){ if(cnt[a[i]]>dem){ dem=cnt[a[i]]; res=a[i]; } else if(cnt[a[i]]==dem){ if(res >a[i]) res=a[i]; } } cout< return 0; }
Bài 68. Cho một dãy A gồm N số nguyên a1,a2,...,aN đã được sắp xếp và Q truy vấn, mỗi
truy vấn gồm ba số l, r, k.
Yêu cầu: Tìm số nhỏ nhất lớn hơn hoặc bằng k trong đoạn l đến r.
Dữ liệu: Vào từ file văn bản MINQ.INP
• Dòng đầu tiên gồm hai số nguyên dương N, Q (1 ≤ N ≤ 10 5 , 1 ≤ Q ≤ 10 3 ).
• Dòng tiếp theo gồm N số nguyên a1,a2,...,aN, mỗi số có giá trị tuyệt đối không quá 10 9 .
• Q dòng tiếp theo, mỗi dòng gồm ba số nguyên thể hiện một truy vấn.
Kết quả: Ghi ra file văn bản MINQ.OUT
• In ra Q dòng, mỗi dòng gồm một số nguyên để trả lời các truy vấn. Nếu không có kết quả thì in ra -1. BAI1.INP BAI1.OUT 6 3 2 1 2 2 4 7 9 -1 1 3 2 4 1 4 5 3 6 4 Bài làm. #include #define N 10005 using namespace std;
int mang(int a[],int l,int r,int k){ int MIN =100000000; for (int i=l;i<=r;i++){
if (a[i]>=k&&a[i] MIN=a[i]; }
if (MIN==100000000) return -1; else return MIN; } int main(){ int n,a[N],q; cin >>n>>q; for (int i=1;i<=n;i++){ cin >>a[i]; } int l,r,k; for (int i=1;i<=q;i++){
cin >>l>>r>>k; cout < } return 0; }
Bài 76. Xét dãy số tự nhiên a0, a1, a2, ....an được xây dựng theo quy tắc sau:
- a0 là một số tự nhiên cho trước có tối đa 10 chữ số
- số ai được ghép vào từ các số ai-1 Ví dụ: a0 = 123 a1 = 123321 a2 = 123321123321 a3= 123321123321123321123321
với hai số tự nhiên n và m cho trước, hãy tìm chữ số thứ m của an. Dữ liệu vào: Dòng đầu chứa số a0
Dòng thứ 2 chứa hai số tự nhiên n và m. (1<=n<=25; 1<=m<=10 9 )
Nếu không tìm thấy được thì ghi ra -1 BAI1.INP BAI1.OUT 123 1 a3 = 123321123321123321123321 3 7
chữ số thứ 7 của a3 là 1 Bài làm #include using namespace std; string st; int n, m; int main(){ cin>>st; cin>>n>>m; int k= st.size(); int p=m%(2*k);
if(m>(pow(2,n)*k)) cout<<"-1"; else{ if(p==0) cout< if(p>k){ int h=p%k; cout< } else cout< } return 0; }
Bài 78. Cho dãy số tự nhiên từ 1 đến n. Nhiệm vụ của ban là tìm 1 số còn thiếu trong dãy số trên. BAI1.INP BAI1.OUT 5 2 3 1 5 4 2 2 1 Bài làm #include using namespace std; int n; int main(){ cin>>n; int a[n+2]; for(int i=1; i<=n-1; i++){ cin>>a[i]; } sort(a+1,a+n); if(a[1]==2) cout<<"1"; else for(int i=1; i<=n-1; i++){ if((a[i+1]-a[i])!=1){ cout < break; } } return 0; }
Bài 79. Cho một dãy số gồm N số nguyên: A1, A2, …, AN . Tìm M số liên tiếp trong dãy số
A1, A2, …, AN sao cho tổng M phần tử này lớn nhất (MYêu cầu: Viết chương trình xác định M số liên tiếp của dãy số có tổng lớn nhất.
Dữ liệu vào: từ file SUMMAX.INP gồm:
Dòng đầu chứa số 2 nguyên dương N , M cách nhau khoảng trắng và không vượt quá 10000 (M < N);
Dòng thứ hai chứa N số nguyên A1, A2, …, AN , mỗi số không vượt quá 1000 và cách nhau một khoảng trắng.
Kết quả ra:Ghi ra file SUMMAX.OUT một dòng gồm M số liên tiếp của dãy có tổng lớn
nhất, các số cách nhau một dấu cách. Nếu có nhiều dãy M số liên tiếp có cùng tổng lớn nhất thì
đưa ra một dãy M số liên tiếp bất kỳ. Ví dụ: SUMMAX.INP SUMMAX.OUT 11 5 33 2 4 6 7 8 3 8 7 5 6 6 7 8 3 8 7 Bài làm #include using namespace std;
long long a[10001],n,m,Max,dau,cuoi,sum; int main(){ cin>>n; cin>>m; for(int i=1;i<=n;i++) cin>>a[i]; Max=-1e18; for(int i=1;i<=n;i++){ sum=0;
for(int j=i;j<=m+i-1;j++)sum=sum+a[j]; if(Max }
cout< for(int i=dau;i<=cuoi;i++)cout< return 0; }
Bài 86. Cho dãy số hãy tìm tích lớn nhất của 3 số bất kỳ trong dãy. Sao cho giá trị tuyệt
đối |ai*aj*ak| là lớn nhất Với 3BAI1.INP BAI1.OUT 8 540 1 -10 9 -2 -6 2 3 2 6 10 Bài làm #include using namespace std; int main(){ int n, maxx; cin>>n; int a[n]; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ if(a[i]<0) a[i]=-a[i]; } sort(a+1,a+n+1); maxx=a[n]*a[n-1]*a[n-2]; cout< return 0; } Bài 1. Đề thành phố #include using namespace std; long long n, k, m; int x, y; int main(){
cin>>x>>y>>n; if(n%7==0){ k=n/7;
cout<<1ll*((2*k*y)+(n-(2*k)*x)); } else{ m=n/7;
cout <<1ll*((((2*m)+1)*y)+((n-(2*m)-1)*x)); } return 0; }
Bài 98. Hãy sắp xếp dãy số theo thứ tự tăng dần với n<=100000 và ai<=10 100 BAI1.INP BAI1.OUT 10 1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 1 2 10 Bài làm #include using namespace std; const int N = 100005; int n; string a[N]; bool cmp(string a, string b) { if (a.length() != b.length())
return a.length() < b.length(); return a < b; } int main() { cin >> n;
for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n, cmp);
for (int i = 0; i < n; i++) {
cout << a[i] <<" "; } return 0; }