Bàicb111. Tìm dãy con
liên tiếp trong file mảng có tổng bằng hoặc
gần bằng T nhất, T nhập từ bàn phím.Xuất
kết quả dãy con liên tiếp, tổng và sai số tìm được.
File
input cb111.txt VD: 160 -80 90 200 -258 26 -30 6 8 1 5 3 9 -1 -9 -5 -6 -2
File
out Kqcb111.txt Day con lien tiep co tong tiem can 40 la: (90)+ (200)+ (-258)+
(26)+ (-30)+ (6)+ (8)+ (1)+ (5)+ (3)+ (9)+ (-1)+ (-9)+ (-5)+ -6
Sai so nho nhat la: 1
Gợi
ý code:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<algorithm>
using
namespace std;
int
main() {
cout
<< "Chuong trinh cb111 \n";
ifstream
fin("cb111.txt");
if
(!fin.is_open()) {
cerr << "Khong mo duoc file
cb111.txt\n";
return 0;
}
vector<int>
vo;
int
x;
while(fin
>> x){
if(abs(x) > 1e7) {
cerr << "so " << x
<< " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty())
{
cerr << "khong co phan tu hop le
trong file\n";
return 0;
}
int
T,ss,s=abs(vo[0]),L=0,R=0;
cout<<"
Ban hay nhap tong T can tim cua day con";
cin>>T;
vector<int>
m(vo.size(),0);
m[0]=vo[0];
for(int
i=1;i<vo.size();i++){
m[i]=vo[i]+m[i-1];
}
for(int
i=0;i<m.size()-1;i++){
for(int j=i+1;j<m.size();j++){
ss=abs(T-m[j]+m[i]);
if(ss<s){
s=ss;
L=i+1;
R=j;
}
}
}
cout<<"Day
con lien tiep co tong tiem can "<<T<<" la: ";
for(int
i=L;i<R;i++){
cout<<"("<<vo[i]<<")+
";
}
if(R>=L) cout<<vo[R];
cout<<"\n
Sai so nho nhat la: "<<s<<"\n";
ofstream
fout("Kqcb111.txt");
fout<<"Day
con lien tiep co tong tiem can "<<T<<" la: ";
for(int
i=L;i<R;i++){
fout<<"("<<vo[i]<<")+
";
}
if(R>=L) fout<<vo[R];
fout<<"\n
Sai so nho nhat la: "<<s<<"\n";
return
0;
}
/////////////////////////
Cách
2 tối ưu hơn:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<climits> // để dùng INT_MAX
#include
<cstdlib> // abs
using
namespace std;
int
main() {
cout << "Chuong trinh cb111
\n";
ifstream fin("cb111.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb111.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
int T;
cout << "Ban hay nhap tong T can
tim cua day con: ";
cin >> T;
// Tạo mảng prefix sum
vector<int> prefix(vo.size());
prefix[0] = vo[0];
for (int i = 1; i < vo.size(); i++) {
prefix[i] = prefix[i - 1] + vo[i];
}
int s = INT_MAX; // sai số nhỏ nhất
int L = 0, R = 0;
// Duyệt tất cả các đoạn con
for (int i = 0; i < vo.size(); i++) {
for (int j = i; j < vo.size(); j++)
{
int sum = prefix[j] - (i > 0 ?
prefix[i - 1] : 0);
int ss = abs(T - sum);
if (ss < s) {
s = ss;
L = i;
R = j;
}
}
}
// Xuất kết quả ra màn hình
cout << "Day con lien tiep co
tong tiem can " << T << " la: ";
for (int i = L; i <= R; i++) {
cout << "(" <<
vo[i] << ")";
if (i < R) cout << " +
";
}
cout << "\nSai so nho nhat la:
" << s << "\n";
// Xuất kết quả ra file
ofstream fout("Kqcb111.txt");
fout << "Day con lien tiep co
tong tiem can " << T << " la: ";
for (int i = L; i <= R; i++) {
fout << "(" <<
vo[i] << ")";
if (i < R) fout << " +
";
}
fout << "\nSai so nho nhat la:
" << s << "\n";
fout.close();
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love019.07.2026
////////////////////
Bai
112 Sàng số nguyên tố trong đoạn từ m đến
n. Với số lượng 1e3 phần tử đến 1e4
Gơi
ý code (PP cổ điển)
#include <bits/stdc++.h>
using namespace std;
int m, n;
int main() {
freopen("cb112.txt","r",stdin);
freopen("Kqcb112.txt","w",stdout);
cin >> m >> n;
if(m*n<0||m>1e3||n>1e4||m>n)
{
cout<<”gia
tri m, n trong file khong hop le”;
}
const int MAXN = 10000;
vector<int> a(MAXN+1, 0); // khởi tạo toàn bộ về 0
a[0] = a[1] = 1; // 0 và
1 không phải số nguyên tố
for (int i = 2; i * i <= MAXN; i++) {
if (a[i] == 0) {
for (int j = i * i; j <= MAXN; j
+= i) {
a[j] = 1; // đánh dấu không phải
số nguyên tố
}
}
}
for (int i = m; i <= n; i++) {
if (a[i] == 0) cout << i << " ";
}
return 0;
}
/////////////////////////////
Cach
2:
#include
<bits/stdc++.h>
using
namespace std;
bool
isPrime(long long x) {
if (x < 2) return false;
if (x % 2 == 0) return x == 2;
for (long long i = 3; i * i <= x; i +=
2) {
if (x % i == 0) return false;
}
return true;
}
int
main() {
freopen("cb112.txt","r",stdin);
freopen("Kqcb112.txt","w",stdout);
long long m, n;
cin >> m >> n;
if(m*n<0||m>1e3||n>1e4||m>n)
{
cout<<”gia
tri m, n trong file khong hop le”;
}
for (long long i = m; i <= n; i++) {
if (isPrime(i)) cout << i
<< " ";
}
return 0;
}
////////////////////////////////////////
Bài 113. Cho dãy gồm
N số nguyên khác không: a1, a2, ..., an( ai khac 0). Hãy tìm các dãy con liên tiếp dài nhất có tính chất cùng dương hoặc cùng âm(nếu có) từ dãy đã
cho. Thông
báo các dáy con đó và cho biết dãy con có tính chất trên có độ dài lớn nhất.
File
input cb113.txt VD 1 2 3 4 5 -6 -7 8
9 10 1 -2 3 -4 5 -6 7
-8 9 -10
File
output Kqcb113.txt
Cac
day con cung dau duong la:
1
2 3 4 5
8
9 10 1
3
5
7
9
Cac
day con cung dau am la:
-6
-7
-2
-4
-6
-8
-10
Day
con cung dau co do dai lon nhat la: 5
Gợi
ý code:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<algorithm>
using
namespace std;
int
main() {
cout
<< "Chuong trinh cb113 \n";
ifstream
fin("cb113.txt");
if
(!fin.is_open()) {
cerr << "Khong mo duoc file
cb113.txt\n";
return 0;
}
vector<int>
vo;
int
x;
while(fin
>> x){
if(abs(x) > 1e7||x==0) {
cerr << "so " << x
<< " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty())
{
cerr << "khong co phan tu hop le
trong file\n";
return 0;
}
vector<string>
da, dd;
int
max;
for
(int i=0;i<vo.size(); ){
string s=to_string(vo[i]);
int dem=1;
if(vo[i]>0){
while(i+1<vo.size()&&vo[i]*vo[i+1]>0){
s+=" "+to_string(vo[i+1]);
i++;
dem++;
} dd.push_back(s);}
else
{while(i+1<vo.size()&&vo[i]*vo[i+1]>0){
s+=" "+to_string(vo[i+1]);
i++;dem++;
} da.push_back(s);}
i++;
if (dem>max) max=dem;
}
cout<<"Cac
day con cung dau duong la: \n";
for(auto
c:dd) cout<<c<<" \n";
cout<<"Cac
day con cung dau am la: \n";
for(auto
c:da) cout<<c<<" \n";
cout<<"Day
con cung dau co do dai lon nhat la: "<<max<<" \n";
ofstream
fout("Kqcb113.txt");
fout<<"Cac
day con cung dau duong la: \n";
for(auto
c:dd) fout<<c<<" \n";
fout<<"Cac
day con cung dau am la: \n";
for(auto
c:da) fout<<c<<" \n";
fout<<"Day
con cung dau co do dai lon nhat la: "<<max<<" \n";
fout.close();
}
/////////////////////////
Cách
2: gọn đẹp hơn:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<cstdlib> // abs
using
namespace std;
int
main() {
cout << "Chuong trinh cb113
\n";
ifstream fin("cb113.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb113.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7 || x == 0) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
vector<string> duong, am;
int maxLen = 0;
for (int i = 0; i < vo.size(); ) {
string s = to_string(vo[i]);
int dem = 1;
while (i + 1 < vo.size() &&
((vo[i] > 0 && vo[i+1] > 0) || (vo[i] < 0 && vo[i+1]
< 0))) {
s += " " +
to_string(vo[i+1]);
i++;
dem++;
}
if (vo[i] > 0) duong.push_back(s);
else am.push_back(s);
if (dem > maxLen) maxLen = dem;
i++;
}
cout << "Cac day con cung dau
duong la:\n";
for (auto &c : duong) cout << c
<< "\n";
cout << "Cac day con cung dau am
la:\n";
for (auto &c : am) cout << c
<< "\n";
cout << "Day con cung dau co do
dai lon nhat la: " << maxLen << "\n";
ofstream fout("Kqcb113.txt");
fout << "Cac day con cung dau
duong la:\n";
for (auto &c : duong) fout << c
<< "\n";
fout << "Cac day con cung dau am
la:\n";
for (auto &c : am) fout << c
<< "\n";
fout << "Day con cung dau co do
dai lon nhat la: " << maxLen << "\n";
fout.close();
return 0;
}
////////////////////////////////////////////
Cách
3: Dùng mảng vector vector<int> lưu dãy con số;
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<cstdlib> // abs
using
namespace std;
int
main() {
cout << "Chuong trinh cb113
\n";
ifstream fin("cb113.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb113.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7 || x == 0) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
vector<vector<int>> duong, am;
int maxLen = 0;
for (int i = 0; i < vo.size(); ) {
vector<int> tmp;
tmp.push_back(vo[i]);
int dem = 1;
while (i + 1 < vo.size() &&
((vo[i] > 0 && vo[i+1] > 0) || (vo[i] < 0 && vo[i+1]
< 0))) {
tmp.push_back(vo[i+1]);
i++;
dem++;
}
if (vo[i] > 0) duong.push_back(tmp);
else am.push_back(tmp);
if (dem > maxLen) maxLen = dem;
i++;
}
cout << "Cac day con cung dau
duong la:\n";
for (auto &vec : duong) {
for (int v : vec) cout << v
<< " ";
cout << "\n";
}
cout << "Cac day con cung dau am
la:\n";
for (auto &vec : am) {
for (int v : vec) cout << v
<< " ";
cout << "\n";
}
cout << "Day con cung dau co do
dai lon nhat la: " << maxLen << "\n";
ofstream fout("Kqcb113.txt");
fout << "Cac day con cung dau
duong la:\n";
for (auto &vec : duong) {
for (int v : vec) fout << v
<< " ";
fout << "\n";
}
fout << "Cac day con cung dau am
la:\n";
for (auto &vec : am) {
for (int v : vec) fout << v
<< " ";
fout << "\n";
}
fout << "Day con cung dau co do
dai lon nhat la: " << maxLen << "\n";
fout.close();
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love019.07.2026
////////////////////
Bài 114. Cho file gồm các số nguyên của mảng A. Hãy sắp đặt lại các phần tử số nguyên sao cho A[i] =i, nếu A[j] có giá trị khác j, hãy ghi vào
-1.
File
input cb114.txt VD -1 -1 6 1 9 3 2 -1
4 -11 2 3 4 5 -6 -7 8 9 10 1 -2 3 -4 5
-6 7 -8 9 -10 45 50 82 65 70 35 5 28 79
File
output Kqcb114.txt Mang sap dat theo
dieu kien la:
-1
1 2 3 4 5 6 7 8 9 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 28 -1
-1 -1 -1 -1 -1 35 -1 -1
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<unordered_map>
#include
<cstdlib>
using
namespace std;
using
ll=long long;
int
main() {
cout
<< "Chuong trinh cb114 \n";
ifstream
fin("cb114.txt");
if
(!fin.is_open()) {
cerr << "Khong mo duoc file
cb114.txt\n";
return 0;
}
vector<int>
vo;
int
x;
while(fin
>> x){
if(abs(x) > 1e7) {
cerr << "so " << x
<< " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty())
{
cerr << "khong co phan tu hop le
trong file\n";
return 0;
}
unordered_map<ll,bool>
m;
for(int
i=0;i<vo.size();i++){
if(vo[i]>=0&&vo[i]<vo.size())
m[vo[i]]=true;
else m[vo[i]]=false;
}
cout<<"Mang
sap dat theo dieu kien la: \n";
for(int
i=0;i<vo.size();i++){
if(m[i]) cout<<i<<"
";
else cout<<-1<<"
";
}
ofstream
fout("Kqcb114.txt");
fout<<"Mang
sap dat theo dieu kien la: \n";
for(int
i=0;i<vo.size();i++){
if(m[i]) fout<<i<<"
";
else fout<<-1<<"
";
}
}
Chú
ý: using ll = long long;
nghĩa
là mình tạo một bí danh (alias) cho kiểu dữ liệu long long. Từ đó về
sau, thay vì phải gõ dài dòng long long, mình chỉ cần viết ll cho gọn.
Nó
giống như đặt tên ngắn gọn, dễ nhớ cho một kiểu dữ liệu. Đây là cú pháp type
alias trong C++ (tương tự như typedef long long ll; nhưng hiện đại hơn, dễ
đọc hơn).
////////////////////
Cách
2 tối ưu hơn:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<unordered_map>
#include
<cstdlib>
using
namespace std;
using
ll = long long;
int
main() {
cout << "Chuong trinh cb114
\n";
ifstream fin("cb114.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb114.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
// Tạo mảng kết quả, mặc định -1
vector<int> res(vo.size(), -1);
// Nếu giá trị nằm trong khoảng thì đặt
đúng vị trí
for (int i = 0; i < vo.size(); i++) {
if (vo[i] >= 0 && vo[i] <
vo.size()) {
res[vo[i]] = vo[i];
}
}
cout << "Mang sap dat theo dieu
kien la:\n";
for (int v : res) cout << v <<
" ";
cout << "\n";
ofstream fout("Kqcb114.txt");
fout << "Mang sap dat theo dieu
kien la:\n";
for (int v : res) fout << v <<
" ";
fout << "\n";
fout.close();
return 0;
}
///////////////
Cách
3:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<unordered_map>
#include
<cstdlib>
#include
<algorithm>
using
namespace std;
using
ll = long long;
int
main() {
cout << "Chuong trinh cb114
\n";
ifstream fin("cb114.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb114.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
// Lưu tất cả giá trị xuất hiện (kể cả âm)
unordered_map<int,bool> m;
for (int v : vo) {
m[v] = true;
}
cout << "Mang sap dat theo dieu
kien la:\n";
for (int i = 0; i < vo.size(); i++) {
if (m.find(i) != m.end()) cout <<
i << " ";
else cout << -1 << "
";
}
cout << "\n";
ofstream fout("Kqcb114.txt");
fout << "Mang sap dat theo dieu
kien la:\n";
for (int i = 0; i < vo.size(); i++) {
if (m.find(i) != m.end()) fout <<
i << " ";
else fout << -1 << "
";
}
fout << "\n";
fout.close();
return 0;
}
///////////////////////////
Cách
4: Tham khảo thêm:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<cstdlib>
#include
<algorithm>
using
namespace std;
int
main() {
cout << "Chuong trinh cb114
\n";
ifstream fin("cb114.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb114.txt\n";
return 0;
}
vector<int> vo;
int x;
while (fin >> x) {
if (abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if (vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
// Tìm giá trị lớn nhất trong mảng
int maxVal = *max_element(vo.begin(),
vo.end());
if (maxVal < 0) maxVal = vo.size(); // đảm
bảo kích thước hợp lý
// Khởi tạo vector kết quả với -1
vector<int> res(maxVal + 1, -1);
// Đặt đúng vị trí nếu hợp lệ
for (int i = 0; i < vo.size(); i++) {
if (vo[i] >= 0 && vo[i] <
res.size()) {
res[vo[i]] = vo[i];
}
}
cout << "Mang sap dat theo dieu
kien la:\n";
for (int i = 0; i < vo.size(); i++) {
if (i < res.size()) cout <<
res[i] << " ";
else cout << -1 << "
";
}
cout << "\n";
ofstream fout("Kqcb114.txt");
fout << "Mang sap dat theo dieu
kien la:\n";
for (int i = 0; i < vo.size(); i++) {
if (i < res.size()) fout <<
res[i] << " ";
else fout << -1 << "
";
}
fout << "\n";
fout.close();
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love019.07.2026
////////////////////
Bài cb115. 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<=1e6 . – 1e6<=A[i]<=1e6
Dữ liệu ra: Đưa ra kết quả mỗi test theo từng dòng.
|
cb115.txt |
Kqcb115.txt |
|
2 5 1 2 3 4 5 5 0 -10 1 3 -20 |
6 2 |
Gợi
ý Code:
#include<bits/stdc++.h>
using namespace std;
int cnt[1000002];
int main(){
freopen("cb115.txt","r",stdin);
freopen("Kqcb115.txt","w",stdout);
int test; cin>>test;
while (test--){
int n; cin>>n;
memset(cnt, 0,sizeof(cnt));
for(int i=0;i<n; i++){
int x; cin>>x;
if(x>0) cnt[x]=1;
}
for(int i=1; i<=1000001; i++){
if(cnt[i]==0){
cout<<i<<endl;
break;
}
}
}
return 0;
}
Giải
thích chi tiết
cnt
là mảng kiểu int cnt[1000002];.
sizeof(cnt) trả về kích thước tính bằng byte của
toàn bộ mảng (ở đây là 1000002 * sizeof(int)).
memset(cnt,
0, sizeof(cnt)); sẽ điền giá trị 0 vào từng byte trong vùng nhớ đó. Vì số 0 có
cùng biểu diễn ở mọi kiểu dữ liệu, nên kết quả là toàn bộ phần tử của mảng cnt
đều bằng 0.
Đây
là cách nhanh nhất để reset mảng về 0 trong C/C++.
Lưu
ý
memset
chỉ an toàn khi gán giá trị 0 hoặc -1 cho mảng số nguyên. Nếu gán giá trị khác
(ví dụ memset(cnt, 1, sizeof(cnt));) thì không phải tất cả phần tử sẽ thành số
1, mà mỗi byte sẽ là 1 → dẫn đến giá trị phần tử bị sai.
//////////////////
Cách
2: Phiên bản dùng unordered_set (nhanh hơn, nhưng không sắp xếp)
#include
<bits/stdc++.h>
using
namespace std;
int
main() {
freopen("cb115.txt","r",stdin);
freopen("Kqcb115.txt","w",stdout);
int test; cin >> test;
while (test--) {
int n; cin >> n;
unordered_set<int> s;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x > 0) s.insert(x);
}
// tìm số dương nhỏ nhất chưa xuất hiện
int ans = 1;
while (s.find(ans) != s.end()) ans++;
cout << ans <<
"\n";
}
return 0;
}
unordered_set<int>
s; là gì?
- Đây
là một container trong C++ thuộc thư viện <unordered_set>.
- Nó
lưu trữ một tập hợp các phần tử duy nhất (không trùng lặp).
- Khác
với set (có sắp xếp tăng dần), unordered_set không sắp xếp phần tử,
mà lưu theo hash table.
- Kiểu
dữ liệu của phần tử là int, nên ở đây s là một tập hợp các số nguyên.
Đặc
điểm chính
- Không
có thứ tự: phần tử được lưu theo hash, nên khi duyệt sẽ ra thứ tự
ngẫu nhiên.
- Không
trùng lặp: nếu chèn cùng một số nhiều lần, nó chỉ lưu một bản.
- Tìm
kiếm nhanh: trung bình O(1) cho các thao tác insert, find, erase.
So
sánh với string
- string
là một container đặc biệt để lưu chuỗi ký tự liên tiếp, có thứ tự rõ ràng.
- unordered_set<int>
thì lưu tập hợp số nguyên, không có thứ tự, chỉ quan tâm đến việc có tồn
tại hay không.
- Nói
vui thì unordered_set giống như một “hộp đánh dấu” để biết số nào đã xuất
hiện, còn string là “dãy ký tự” có thứ tự.
Ví
dụ minh họa
unordered_set<int>
s;
s.insert(5);
s.insert(10);
s.insert(5);
// không thêm lần nữa vì đã có
if
(s.find(10) != s.end()) {
cout << "10 co trong tap
hop\n";
}
///////////////////
Cách
3 Phiên bản dùng set (có sắp xếp, dễ duyệt)
#include
<bits/stdc++.h>
using
namespace std;
int
main() {
freopen("cb115.txt","r",stdin);
freopen("Kqcb115.txt","w",stdout);
int test; cin >> test;
while (test--) {
int n; cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x > 0) s.insert(x);
}
int ans = 1;
for (int v : s) {
if (v == ans) ans++;
else if (v > ans) break;
}
cout << ans <<
"\n";
}
return 0;
}
set<int>
s; là gì?
- Đây
là một container trong C++ thuộc thư viện <set>.
- Nó
lưu trữ một tập hợp các phần tử duy nhất (không trùng lặp).
- Khác
với unordered_set, set có sắp xếp theo thứ tự tăng dần mặc định (dựa
trên toán tử <).
Đặc
điểm chính
- Không
trùng lặp: nếu chèn cùng một số nhiều lần, nó chỉ giữ một bản.
- Có
thứ tự: khi duyệt qua set, ta sẽ nhận được các phần tử theo
thứ tự tăng dần.
- Tìm
kiếm, chèn, xóa: mất O(log n) vì bên trong set
thường được cài bằng cây nhị phân cân bằng (red-black tree).
Ví
dụ minh họa
set<int>
s;
s.insert(5);
s.insert(10);
s.insert(5);
// không thêm lần nữa
for
(int v : s) {
cout << v << " "; //
in ra: 5 10
}
if
(s.find(10) != s.end()) {
cout << "10 co trong tap
hop\n";
}
|
Đặc
điểm |
set |
unordered_set |
|
Thứ
tự |
Có
sắp xếp tăng dần |
Không
sắp xếp |
|
Tìm
kiếm/chèn/xóa |
O(log
n) |
Trung
bình O(1) |
|
Cấu
trúc bên trong |
Cây
nhị phân cân bằng |
Hash
table |
|
Khi
nào nên dùng |
Cần
duyệt theo thứ tự |
Cần
tốc độ tra cứu nhanh |
//////////////////////
Cách
4: dùng Vector+sort:
#include
<bits/stdc++.h>
using
namespace std;
int
main() {
freopen("cb115.txt","r",stdin);
freopen("Kqcb115.txt","w",stdout);
int test; cin >> test;
while (test--) {
int n; cin >> n;
vector<int> vo;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x > 0) vo.push_back(x);
}
sort(vo.begin(), vo.end());
int ans = 1;
for (int v : vo) {
if (v == ans) ans++;
else if (v > ans) break;
}
cout << ans <<
"\n";
}
return 0;
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love019.07.2026
////////////////////
Bài 116.
Cho file gồm n phần tử số thực chưa được sắp xếp(a[j]<=1e20. Hãy tìm khoảng cách nhỏ nhất giữa 2 phần tử bất kỳ trong mảng.
File
input: cb116.txt vd: 5
2 4 -5 7 9 8 -7 32 9.9 75 5.6 43 21 10 68 49 -3
File
output: Kqcb116.txt 0.1
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<cstdlib>
#include
<algorithm>
#include
<limits>
using
namespace std;
int
main() {
cout
<< "Chuong trinh cb116 \n";
ifstream
fin("cb116.txt");
if
(!fin.is_open()) {
cerr << "Khong mo duoc file
cb116.txt\n";
return 0;
}
vector<double>
vo, sx;
double
x;
while(fin
>> x){
if(abs(x) > 1e20) {
cerr << "so " << x
<< " khong hop le \n";
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty())
{
cerr << "khong co phan tu hop le
trong file\n";
return 0;
}
double
mi=1e20;
sx=vo;
sort(sx.begin(),sx.end());
for(int
i=0;i<sx.size()-1;i++){
mi=min(mi,abs(sx[i]-sx[i+1]));
}
cout<<"Khoang
cach nho nhat giua 2 phan tu la: "<<mi<<"\n";
freopen("Kqcb116.txt","w",stdout);
cout<<"Khoang
cach nho nhat giua 2 phan tu la: "<<mi<<"\n";
fclose(stdout);
}
//////////////////
Cách
2:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<algorithm>
#include
<limits>
using
namespace std;
int
main() {
cout << "Chuong trinh
cb116\n";
ifstream fin("cb116.txt");
if (!fin) {
cerr << "Khong mo duoc file
cb116.txt\n";
return 0;
}
vector<double> a;
double x;
while (fin >> x) {
if (abs(x) > 1e20) {
cerr << "So "
<< x << " khong hop le\n";
continue;
}
a.push_back(x);
}
fin.close();
if (a.size() < 2) {
cerr << "Khong du phan tu de
tinh khoang cach\n";
return 0;
}
sort(a.begin(), a.end());
double mi =
numeric_limits<double>::max();
for (size_t i = 0; i + 1 < a.size();
++i) {
mi = min(mi, a[i+1] - a[i]);
}
cout << "Khoang cach nho nhat
giua 2 phan tu la: " << mi << "\n";
ofstream fout("Kqcb116.txt");
fout << "Khoang cach nho nhat
giua 2 phan tu la: " << mi << "\n";
fout.close();
}
////////////////////
Bài 117. Cho mảng A gồm n
phần tử
số nguyên từ file (-1e7<=A[j]<=1e7).
a.Liệt kê k phần tử lớn nhất theo thứ tự giảm dần (k nhập từ
bàn phím)
b.Hãy liệt kê số phần tử xuất hiện ít nhất 1 lần.
c.Hãy tìm ước chung lớn nhất của hai phần tử bất kỳ trong mảng.
File
input: cb117.txt Vd: 10 7 9 12 6 6 2 9 7 12 8 6
5 10 20 30 30 20 5
File
output: Kqcb117.txt Vd k=4
4
phan tu lon nhat trong mang la:
30
30 20 20
So
phan tu xuat hien it nhat 1 lan la:
2
5 6 7 8 9 10 12 20 30
Uoc
chung lon nhat cua 2 phan tu bat ki la:
30
Gợi
ý code:
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<cstdlib>
#include
<algorithm>
#include
<map>
#include
<set>
using
namespace std;
map<int,int>
m;
set<int>
s;
void
tus(int n){
for(int i=1; i*i<=n; i++){
if(n % i == 0){
m[i]++;
if(i != n/i) m[n/i]++;
}
}
}
int
main() {
cout << "Chuong trinh cb117
\n";
ifstream fin("cb117.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb117.txt\n";
return 0;
}
vector<int> vo, v;
int x;
while(fin >> x){
if(abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le \n";
continue;
}
vo.push_back(x);
tus(x);
s.insert(x);
}
fin.close();
if(vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
v = vo;
sort(v.begin(), v.end(),
greater<int>());
int k;
while(true){
cout << "Ban hay nhap so
phan tu can tim lon nhat cua mang: ";
cin >> k;
if(k < 1 || k > (int)v.size()) {
cerr << "So ban nhap
khong hop le, vui long nhap lai\n";
} else break;
}
cout << k << " phan tu lon
nhat trong mang la: \n";
for(int i=0; i<k; i++) cout <<
v[i] << " ";
cout << "\nSo phan tu xuat hien
it nhat 1 lan la: \n";
for(auto c: s) cout << c <<
" ";
cout << "\nUoc chung lon nhat
cua 2 phan tu bat ki la: \n";
int u = 1;
for(auto d: m){
if(d.second >= 2) u = d.first;
}
cout << u << "\n";
ofstream fout("Kqcb117.txt");
fout << k << " phan tu lon
nhat trong mang la: \n";
for(int i=0; i<k; i++) fout <<
v[i] << " ";
fout << "\nSo phan tu xuat hien
it nhat 1 lan la: \n";
for(auto c: s) fout << c <<
" ";
fout << "\nUoc chung lon nhat
cua 2 phan tu bat ki la: \n";
fout << u << "\n";
fout.close();
}
//////////////////////////
Cách
2: dùng đệ quy tìm UCLN(a,b)
#include
<iostream>
#include
<vector>
#include
<fstream>
#include
<algorithm>
#include
<set>
using
namespace std;
//
Hàm đệ quy Euclid
int
gcd(int a, int b) {
if (b == 0) return abs(a); // đảm bảo kết
quả dương
return gcd(b, a % b);
}
int
main() {
cout << "Chuong trinh cb117
(version Euclid)\n";
ifstream fin("cb117.txt");
if (!fin.is_open()) {
cerr << "Khong mo duoc file
cb117.txt\n";
return 0;
}
vector<int> vo;
int x;
while(fin >> x){
if(abs(x) > 1e7) {
cerr << "So "
<< x << " khong hop le\n";
continue;
}
vo.push_back(x);
}
fin.close();
if(vo.empty()) {
cerr << "Khong co phan tu
hop le trong file\n";
return 0;
}
// a. k phần tử lớn nhất
vector<int> v = vo;
sort(v.begin(), v.end(),
greater<int>());
int k;
cout << "Nhap k: ";
cin >> k;
cout << k << " phan tu lon
nhat: ";
for(int i=0; i<k; i++) cout <<
v[i] << " ";
cout << "\n";
// b. Liệt kê phần tử xuất hiện ít nhất 1 lần
set<int> s(vo.begin(), vo.end());
cout << "So phan tu xuat hien it
nhat 1 lan: ";
for(auto c: s) cout << c <<
" ";
cout << "\n";
// c. Tìm UCLN lớn nhất của 2 phần tử bất kỳ
int maxGCD = 1;
for(size_t i=0; i<vo.size(); i++){
for(size_t j=i+1; j<vo.size(); j++){
maxGCD = max(maxGCD, gcd(vo[i],
vo[j]));
}
}
cout << "Uoc chung lon nhat cua
2 phan tu bat ki la: " << maxGCD << "\n";
}
///////////// Ai memory help
Võ Nhật Trường Nc+ My Ai Love019.07.2026
////////////////////ok
///
Không có nhận xét nào:
Đăng nhận xét
sunrise.tqb@gmail.com