Tôi : Võ Nhật Trường
CHÀO CÁC BẠN
LƯU Ý:
OFFICIAL COPY, DOWNLOAD ACTIVITIES PROHIBITED.
Dịch Google
Một số chủ đề BDHS giỏi tin.pdf
- 0 / 0
-
Nguồn:
Người gửi: Võ Nhật Trường (trang riêng)
Ngày gửi: 09h:40' 24-12-2025
Dung lượng: 4.5 MB
Số lượt tải: 0
Người gửi: Võ Nhật Trường (trang riêng)
Ngày gửi: 09h:40' 24-12-2025
Dung lượng: 4.5 MB
Số lượt tải: 0
Số lượt thích:
0 người
Gợi ý một số dạng bài HSG hay gặp
•
Số học: sàng nguyên tố, ước – bội, phân tích thừa số, modulo
•
Mảng & chuỗi: prefix sum, two pointers, sliding window
•
Quy hoạch động: dãy con, chia tiền, xâu con chung
•
Đồ thị: BFS/DFS, đường đi ngắn nhất, cây
•
Tổ hợp – đếm: hoán vị, chỉnh hợp, phân hoạch số
Bài HSG thường xoay quanh:
•
Sàng nguyên tố
•
Mảng cộng dồn
•
Hai con trỏ
•
Quy hoạch động cơ bản
•
Đệ quy + chia để trị
•
Đồ thị cơ bản (DFS/BFS)
#include
#define N 10000000
// Gộp toàn bộ thư viện STL
// Giới hạn tối đa cho mảng sàng nguyên tố
using namespace std;
int nt[N];
int l, r;
// Mảng đánh dấu số nguyên tố: nt[x] = 1 nếu x là số nguyên tố
// Khoảng cần xét
// Hàm sàng nguyên tố Eratosthenes
void sangnt(int n)
{
fill(nt + 2, nt + n + 1, 1); // Gán nt[2..n] = 1 (giả sử ban đầu tất cả đều là số nguyên tố)
for (int i = 2; i * i <= n; i++) // Duyệt đến sqrt(n)
if (nt[i] == 1)
// Nếu i là số nguyên tố
for (int j = i * i; j <= n; j += i)
nt[j] = 0;
// Đánh dấu các bội số của i không phải số nguyên tố
}
// Hàm tính tổng chữ số của x
int tongcs(int x)
{
int s = 0;
while (x > 0)
{
s += x % 10; // Lấy chữ số cuối
x /= 10;
// Bỏ chữ số cuối
}
return s;
}
int main()
{
freopen("password.inp", "r", stdin); // Đọc từ file
freopen("password.out", "w", stdout); // Ghi ra file
cin >> l >> r;
// Nhập khoảng [l, r]
sangnt(r);
// Sàng nguyên tố đến r
// Duyệt tất cả các số từ 1 đến r
{ nên for (int x = l; x <= r; x++)
if (nt[x] == 1 && nt[tongcs(x)] == 1)
cout << x << " "; }
for (int x = 1; x <= r; x++)
// Điều kiện mật khẩu:
// 1. x là số nguyên tố
// 2. Tổng chữ số của x cũng là số nguyên tố
if (nt[x] == 1 && nt[tongcs(x)] == 1)
cout << x << " ";
return 0;
}
//////////////////////////
1. #include là gì?
Đây là một header tổng hợp, chỉ có trên trình biên dịch GCC (g++), không phải chuẩn của C++.
Nó chứa gần như tất cả các thư viện STL:
•
… và rất nhiều nữa.
•
fill
là hàm có sẵn trong C++, nằm trong thư viện .
Nó không phải thủ tục bạn tự viết, mà là hàm chuẩn của STL.
fill(begin, end, value);
begin: con trỏ hoặc iterator bắt đầu
•
end: con trỏ hoặc iterator kết thúc (không bao gồm vị trí này)
•
value: giá trị muốn gán
#define N 10000000
Đây là macro trong C++.
Nó có nghĩa là:
•
Mỗi khi gặp chữ N, trình biên dịch sẽ thay bằng 10000000.
////////////////
Chương trình nhận vào một chuỗi ký tự, trong đó có thể chứa chữ cái và chữ số lẫn lộn, ví dụ:
ab12c3d12x7
Nhiệm vụ:
•
Tách tất cả các số xuất hiện trong chuỗi
•
Đánh dấu số nào đã xuất hiện
•
Đếm xem có bao nhiêu số khác nhau
for (; j < s.size() && ... ; j++)
Nghĩa là: không khởi tạo gì trong vòng for
→ vì biến j đã được khởi tạo từ trước: viết đầy đủ sẽ thành
for (int j = i; j < s.size() && ...; j++)
ios::sync_with_stdio(false);
cin.tie(nullptr);
1. ios::sync_with_stdio(false); — Tắt đồng bộ C và C++
Ý nghĩa:
C++ có hai hệ thống nhập/xuất:
•
cin, cout (C++)
•
scanf, printf (C)
Mặc định, C++ đồng bộ hai hệ thống này để tránh lỗi, nhưng điều đó làm chương trình chậm
hơn.
Khi bạn viết:
ios::sync_with_stdio(false);
Bạn tắt đồng bộ, nghĩa là:
•
cin và cout chạy độc lập
•
tốc độ tăng lên đáng kể (nhanh gấp 2–3 lần)
⚠ Lưu ý quan trọng:
Khi đã tắt đồng bộ:
•
KHÔNG được dùng lẫn lộn cin với printf, hoặc cout với scanf.
2. cin.tie(nullptr); — Bỏ buộc cin với cout
Mặc định:
•
cin bị “buộc” với cout
•
Mỗi lần gọi cin, hệ thống sẽ tự động flush (đẩy ra màn hình) cout
Điều này an toàn nhưng làm chậm.
Khi bạn viết:
cin.tie(nullptr);
Bạn tháo buộc này ra.
Kết quả:
•
cin không còn ép cout phải flush nữa
•
tốc độ nhập/xuất tăng lên
MỤC TIÊU CỦA CHƯƠNG TRÌNH
Chương trình nhận vào một chuỗi ký tự, trong đó có thể chứa chữ cái và chữ số lẫn lộn, ví dụ:
ab12c3d12x7
Nhiệm vụ:
•
Tách tất cả các số xuất hiện trong chuỗi
•
Đánh dấu số nào đã xuất hiện
•
Đếm xem có bao nhiêu số khác nhau
Ví dụ trên → các số xuất hiện:
12, 3, 7 → có 3 số khác nhau.
PHÂN TÍCH TỪNG DÒNG LỆNH
#include
Gộp tất cả thư viện STL vào một file (chỉ có trên g++).
Giúp code ngắn hơn.
const int MAXN = 1001;
Đặt giới hạn tối đa cho số có thể xuất hiện trong chuỗi.
→ Các số trong chuỗi được giả sử nhỏ hơn 1000.
string s;
Chuỗi đầu vào.
int imam[MAXN];
Mảng đánh dấu:
•
imam[x] = 1 nghĩa là số x đã xuất hiện trong chuỗi
•
imam[x] = 0 nghĩa là chưa xuất hiện
Tối ưu nhập xuất
ios::sync_with_stdio(false); cin.tie(nullptr);
Giúp chương trình chạy nhanh hơn (chuẩn competitive programming).
Đọc file nếu có
if (fopen("mm.inp", "r")) { freopen("mm.inp", "r", stdin); freopen("mm.out", "w", stdout); }
Nếu tồn tại file mm.inp, chương trình sẽ:
•
đọc từ file mm.inp
•
ghi ra file mm.out
Nếu không có file → đọc từ bàn phím bình thường.
Đọc chuỗi
cin >> s;
Lưu ý: chỉ đọc đến dấu cách đầu tiên.
(Đề bài có thể đảm bảo chuỗi không chứa khoảng trắng.)
VÒNG LẶP CHÍNH – TÁCH SỐ TRONG CHUỖI
for (int i = 0; i < (int)s.size(); i++)
Duyệt từng ký tự trong chuỗi.
Bỏ qua chữ cái
if (s[i] >= 'a' && s[i] <= 'z') continue;
Nếu là chữ thường → bỏ qua.
(Chỉ xử lý chữ số.)
Bắt đầu ghép số
int broj = 0; int j = i;
•
broj = số đang được ghép (tên tiếng Croatia, nghĩa là “number”)
•
j = vị trí chạy để ghép số
Ghép các chữ số liên tiếp thành một số nguyên
for (; j < (int)s.size() && s[j] >= '0' && s[j] <= '9'; j++) { broj *= 10; broj += s[j] - '0'; }
Ví dụ chuỗi: ab123cd
Khi gặp 1:
•
broj = 1
•
gặp 2 → broj = 12
•
gặp 3 → broj = 123
Vòng lặp dừng khi gặp ký tự không phải số.
Đánh dấu số đã xuất hiện
imam[broj] = 1;
Ví dụ: nếu số 123 xuất hiện → imam[123] = 1.
Nhảy i đến cuối số vừa đọc
i = j - 1;
Giúp tránh đọc lại các chữ số đã xử lý.
ĐẾM BAO NHIÊU SỐ KHÁC NHAU
int rj = 0; for (int i = 0; i < MAXN; i++) { rj += imam[i]; }
Vì mỗi số chỉ được đánh dấu 0 hoặc 1, nên tổng chính là số lượng số khác nhau.
🖨
In kết quả
cout << rj << endl;
TÓM TẮT NGẮN GỌN CHO GIÁO VIÊN
Chương trình:
1. Đọc chuỗi
2. Tách các số liên tiếp trong chuỗi
3. Đánh dấu số nào xuất hiện
4. Đếm số lượng số khác nhau
5. In kết quả
Thuật toán chạy rất nhanh, phù hợp bài HSG.
#include
// Gộp toàn bộ thư viện STL (chỉ có trên g++)
using namespace std;
const int MAXN = 1001;
string s;
// Giới hạn số tối đa có thể xuất hiện trong chuỗi
// Chuỗi đầu vào
int imam[MAXN];
// Mảng đánh dấu: imam[x] = 1 nghĩa là số x đã xuất hiện
int main()
{
ios::sync_with_stdio(false); // Tăng tốc độ nhập/xuất (tắt đồng bộ với stdio C)
cin.tie(nullptr);
// Không buộc cin phải flush cout → nhanh hơn
// Nếu tồn tại file mm.inp → đọc từ file, ghi ra file mm.out
if (fopen("mm.inp", "r"))
{
freopen("mm.inp", "r", stdin);
freopen("mm.out", "w", stdout);
}
cin >> s;
// Đọc chuỗi (không chứa khoảng trắng)
// Duyệt từng ký tự trong chuỗi
for (int i = 0; i < (int)s.size(); i++)
{
// Nếu ký tự là chữ cái thường → bỏ qua
if (s[i] >= 'a' && s[i] <= 'z')
continue;
int broj = 0;
int j = i;
// Biến để ghép số (broj = "number" theo tiếng Croatia)
// j bắt đầu từ vị trí i
// Ghép các chữ số liên tiếp thành một số nguyên
for (; j < (int)s.size() && s[j] >= '0' && s[j] <= '9'; j++)
{
broj *= 10;
// Dịch trái (nhân 10)
broj += s[j] - '0'; // Cộng chữ số hiện tại
}
imam[broj] = 1;
i = j - 1;
// Đánh dấu số này đã xuất hiện
// Nhảy i đến cuối dãy số vừa đọc
}
int rj = 0;
// rj = kết quả: số lượng số khác nhau
// Đếm xem có bao nhiêu số đã được đánh dấu
for (int i = 0; i < MAXN; i++)
{
rj += imam[i];
// imam[i] = 1 → số đó xuất hiện
}
cout << rj << endl;
// In kết quả
return 0;
}
Chương trình thực hiện:
1. Đọc chuỗi gồm chữ cái và chữ số lẫn lộn
2. Tách tất cả các số nguyên xuất hiện trong chuỗi
3. Đánh dấu số nào đã xuất hiện
4. Đếm số lượng số khác nhau
5. In kết quả
//////////////////////////////
getline(cin, str); dùng để làm gì?
Lệnh này đọc cả một dòng văn bản từ bàn phím (hoặc file) và lưu vào biến chuỗi str.
Khác với cin >> str, getline sẽ:
•
Đọc toàn bộ dòng, kể cả khoảng trắng
•
Dừng lại khi gặp ký tự xuống dòng (\n)
•
Không bỏ qua khoảng trắng
cin >> n;
cin.ignore(); // bỏ ký tự '\n' còn lại
getline(cin, s);
/////////////////////////////////////////
#include
#define K 200000
// Gộp toàn bộ thư viện STL (tiện cho bài thi)
// Giới hạn tối đa cho chỉ số Fibonacci cần tính
#define MOD 10000000007
#define ll long long
// Số modulo rất lớn để tránh tràn số
// Viết tắt kiểu long long
using namespace std;
ll F[K + 2], ans;
int n, k;
// Mảng Fibonacci và biến lưu tổng
// Hai số đầu vào
int main()
{
freopen("flashback.inp", "r", stdin); // Đọc từ file (nếu có)
freopen("flashback.out", "w", stdout); // Ghi ra file
cin >> n >> k;
// Nhập n và k
F[1] = F[2] = 1;
// Khởi tạo hai số Fibonacci đầu tiên
ans = 2;
// F[2] = 1 và F[0] không dùng → tổng ban đầu = 1 + 1 = 2
// Tính Fibonacci từ F[3] đến F[2*k]
for (int i = 3; i <= 2 * k; i++)
{
F[i] = (F[i - 1] + F[i - 2]) % MOD; // Công thức Fibonacci chuẩn
if (i % 2 == 0)
// Nếu chỉ số i là số chẵn
ans = (ans + F[i]) % MOD;
// Cộng vào tổng
}
// Kết quả cuối cùng là tổng Fibonacci chẵn nhân với n
cout << (ans * n) % MOD;
return 0;
}
///////////////
1. Tránh tràn số (integer overflow)
Khi nào bị tràn số?
Khi giá trị vượt quá giới hạn kiểu dữ liệu:
•
int tối đa khoảng 2 tỷ
•
long long tối đa khoảng 9×10¹⁸
•
Fibonacci, lũy thừa, nhân lớn… rất dễ vượt giới hạn
✔ Cách tránh tràn số
•
Dùng kiểu lớn hơn: long long, unsigned long long
•
Dùng modulo:
Ví dụ:
F[i] = (F[i-1] + F[i-2]) % MOD;
•
→ giữ số luôn nhỏ hơn MOD → không bao giờ tràn
•
Dùng thư viện big integer (nếu cần số cực lớn)
•
C++: boost::multiprecision::cpp_int
•
Python: tự động hỗ trợ số lớn
2. Tránh tràn bộ nhớ (memory overflow)
Khi nào bị tràn bộ nhớ?
•
Khai báo mảng quá lớn (ví dụ int a[10^9])
•
Dùng đệ quy quá sâu
•
Cấp phát động không kiểm soát
✔ Cách tránh
•
Dùng vector thay vì mảng tĩnh
vector a(n);
•
Chỉ cấp phát đúng kích thước cần thiết
•
Tránh đệ quy sâu → chuyển sang vòng lặp hoặc dùng stack tự quản lý
•
Không tạo mảng trong hàm quá lớn
(stack chỉ khoảng 1–8 MB)
3. Tránh quá tải CPU (chạy quá lâu)
Khi nào bị quá tải?
•
Vòng lặp quá lớn: O(n²), O(n³)
•
Thuật toán không tối ưu
•
Duyệt lại dữ liệu nhiều lần không cần thiết
✔ Cách tránh
•
Tối ưu thuật toán:
o
Dùng mảng cộng dồn
o
Dùng sàng nguyên tố
o
Dùng quy hoạch động
o
Dùng hai con trỏ
•
Giảm số vòng lặp lồng nhau
•
Dùng cấu trúc dữ liệu phù hợp
(set, map, priority_queue…)
4. Tránh quá tải I/O (nhập xuất quá chậm)
Khi nào bị chậm?
•
In/đọc hàng triệu dòng bằng cin/cout
✔ Cách tăng tốc
•
Dùng:
ios::sync_with_stdio(false); cin.tie(nullptr);
•
Hoặc dùng scanf/printf nếu cần tốc độ cao
🛡 5. Tránh lỗi logic gây crash chương trình
✔ Kiểm tra chỉ số mảng
if (i >= 0 && i < n)
✔ Tránh chia cho 0
if (b != 0) x = a / b;
✔ Kiểm tra dữ liệu đầu vào
•
Không đọc chuỗi rỗng
•
Không dùng biến chưa khởi tạo
Tóm tắt 1 câu dễ nhớ
Muốn tránh tràn số → dùng modulo.
Muốn tránh tràn bộ nhớ → dùng vector.
Muốn tránh quá tải CPU → tối ưu thuật toán.
Muốn tránh chậm I/O → bật sync off + tie nullptr.
//////////////////////////
1. Khi đã dùng freopen, bạn xử lý dữ liệu y như nhập từ bàn phím
Ví dụ:
freopen("password.inp","r",stdin); cin >> x;
Lúc này:
•
cin >> x; không đọc từ bàn phím
•
mà đọc giá trị từ file password.inp
•
và gán vào biến x đúng kiểu dữ liệu bạn khai báo (int, long long, string…)
Bạn xử lý biến x hoàn toàn bình thường, không khác gì nhập từ bàn phím.
2. Ví dụ minh họa
Giả sử file password.inp chứa:
10 50
Code:
int l, r; freopen("password.inp","r",stdin); cin >> l >> r;
Sau khi chạy:
•
l = 10
•
r = 50
Bạn xử lý tiếp:
for (int i = l; i <= r; i++) cout << i << " ";
3. Tóm lại
•
freopen("file.inp", "r", stdin); → thay nguồn nhập bằng file
•
cin >> x; → đọc dữ liệu từ file vào biến x
•
Bạn xử lý x như biến bình thường
•
Không cần lệnh đặc biệt nào khác
/////////////////
Not ! and && or ||
#include
using namespace std;
int main()
{
freopen("mm.inp","r",stdin);
freopen("mm.out","w",stdout);
string s;
getline(cin, s);
int dem = 0;
bool dang_trong_day_so = false;
for (char c : s)
{
if (isdigit(c))
{
if (!dang_trong_day_so)
{
dem++;
// bắt đầu dãy số mới
dang_trong_day_so = true; // đánh dấu đang trong dãy
}
}
else
{
dang_trong_day_so = false;
}
}
// kết thúc dãy số
cout << dem;
return 0;
}
//////////////////////////////
Tóm nhanh ý nghĩa thuật toán
•
Đề ngầm hiểu: cho dãy gồm n số nguyên.
•
Bài làm:
o
Đếm xem có bao nhiêu số khác nhau trong dãy (Q).
o
Tìm xem giá trị nào xuất hiện nhiều nhất, với tần suất bao nhiêu (P).
•
Về kỹ thuật lập trình:
•
Dùng unordered_map để đếm tần suất là rất chuẩn, rất hiện đại.
•
Duyệt bằng for (auto &p : cnt) là cách viết ngắn, rõ, nên khuyến khích.
#include
using namespace std;
int main() {
// Đọc từ file mm.inp, ghi ra file mm.out
freopen("mm.inp", "r", stdin);
freopen("mm.out", "w", stdout);
int n;
cin >> n; // đọc số lượng phần tử
unordered_map cnt; // cnt[x] = số lần xuất hiện của x
for (int i = 0; i < n; i++) { // chú ý: < n, không phải <= n
int x;
cin >> x;
cnt[x]++; // tăng số lần xuất hiện của giá trị x
}
int Q = cnt.size(); // số lượng giá trị khác nhau
int P = 0;
// tần suất lớn nhất
// duyệt qua từng cặp (key, value) trong cnt
for (auto &p : cnt) {
P = max(P, p.second); // p.second là số lần xuất hiện của p.first
}
cout << Q << "\n" << P;
return 0;
}
3. unordered_map cnt;
•
•
Đây là một cấu trúc dữ liệu ánh xạ (bản đồ) từ:
o
key: int (giá trị x trong dãy)
o
value: int (số lần x xuất hiện)
Ta dùng nó như một cái “từ điển”:
o
cnt[x] = số lần xuất hiện của giá trị x.
•
Vì là unordered_map nên:
•
Các phần tử không sắp xếp theo thứ tự tăng dần của key.
•
Tra cứu / thêm / tăng đếm thường rất nhanh (trung bình O(1)).
Ví dụ: nếu dãy là 5 7 5 5 9
thì sau vòng lặp:
•
cnt[5] = 3
•
cnt[7] = 1
•
cnt[9] = 1
2.4. Vòng lặp nhập và đếm:
for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }
•
for (int i = 0; i < n; i++): lặp đúng n lần, mỗi lần đọc 1 số.
•
•
cnt[x]++:
o
Nếu x chưa từng xuất hiện → cnt[x] tự động khởi tạo = 0, rồi tăng lên 1.
o
Nếu x đã xuất hiện → tăng số lần thêm 1.
Đây là mẫu rất chuẩn để đếm tần suất xuất hiện của các giá trị.
2.5. int Q = cnt.size();
•
cnt.size() trả về số lượng key khác nhau trong unordered_map.
•
Nghĩa là: có bao nhiêu giá trị phân biệt trong dãy.
•
Ví dụ:
•
Dãy: 5 7 5 5 9
•
Các key: 5, 7, 9 → cnt.size() = 3 → Q = 3.
2.6. Duyệt unordered_map bằng for (auto &p : cnt)
int P = 0; for (auto &p : cnt) P = max(P, p.second);
•
auto &p:
o
p là một cặp pair đại diện cho một phần tử trong cnt.
o
p.first là key (giá trị x).
o
p.second là value (số lần x xuất hiện).
o
Dùng auto để đỡ phải viết kiểu dài dòng.
•
P = max(P, p.second);
•
p.second là tần suất của một giá trị nào đó.
•
Lần lượt lấy giá trị lớn nhất trong tất cả các p.second.
→ Kết quả: P là số lần xuất hiện nhiều nhất của một giá trị trong dãy.
Ví dụ dãy 5 7 5 5 9:
•
cnt[5] = 3
•
cnt[7] = 1
•
cnt[9] = 1
Duyệt:
•
gặp 5 → P = max(0, 3) = 3
•
gặp 7 → P = max(3, 1) = 3
•
gặp 9 → P = max(3, 1) = 3
Kết quả: P = 3.
2.7. In kết quả
cout << Q << "\n" << P;
•
In:
•
Dòng 1: số lượng giá trị khác nhau.
•
Dòng 2: tần suất lớn nhất.
Vì sao kỹ thuật này mạnh?
1. Đếm nhanh như chớp (trung bình O(1) mỗi lần)
unordered_map dùng bảng băm, nên mỗi lần tăng đếm:
cnt[x]++;
gần như tức thì, không cần tìm kiếm tuyến tính hay nhị phân.
2. Không cần biết trước giá trị lớn hay nhỏ
Dãy có thể chứa:
•
số âm
•
số lớn hàng triệu
•
số lặp lại
•
số không theo thứ tự
→ unordered_map vẫn xử lý gọn.
3. Tự động tạo key mới khi gặp giá trị mới
Không cần kiểm tra tồn tại:
if (cnt.find(x) == cnt.end()) ...
Chỉ cần:
cnt[x]++;
Nếu x chưa có → tự tạo với giá trị 0 rồi tăng lên 1.
4. Duyệt tất cả giá trị phân biệt rất dễ
for (auto &p : cnt) { // p.first = giá trị // p.second = số lần xuất hiện }
Không cần mảng đánh dấu, không cần sort.
5. Giải được rất nhiều dạng bài
Kỹ thuật này xuất hiện trong:
•
đếm số khác nhau
•
tìm phần tử xuất hiện nhiều nhất
•
tìm mode
•
kiểm tra tần suất
•
phát hiện phần tử xuất hiện 1 lần
•
xử lý dãy lớn không thể sort
•
bài toán mật mã, tần suất ký tự
•
bài toán thống kê dữ liệu
Nói cách khác: đây là một trong những kỹ thuật “đinh” của lập trình thi đấu và xử lý dữ liệu.
Bạn dạy học sinh kỹ thuật này là cực kỳ tốt
Nhiều em chỉ biết sort rồi đếm, hoặc dùng mảng đánh dấu, nhưng khi gặp:
•
giá trị âm
•
giá trị lớn
•
giá trị không liên tục
→ là “tắc đường”.
unordered_map giúp vượt qua tất cả những hạn chế đó.
1. Google tìm ảnh gốc / ảnh tương tự hoạt động thế nào?
Google không so sánh từng pixel (quá chậm).
Thay vào đó, họ chuyển ảnh thành một tập các đặc trưng (features), ví dụ:
•
màu sắc chủ đạo
•
các cạnh (edges)
•
các điểm đặc biệt (keypoints)
•
mô tả đặc trưng (descriptors) như SIFT, SURF, ORB
•
fingerprint của ảnh
Sau đó họ đếm tần suất hoặc so khớp tần suất của các đặc trưng này.
Ví dụ:
•
Ảnh A có 120 điểm đặc trưng loại X
•
Ảnh B có 118 điểm đặc trưng loại X
→ Khả năng cao là ảnh giống nhau.
Đây chính là dạng đếm tần suất đặc trưng.
2. Liên hệ với unordered_map trong bài toán của bạn
Trong bài toán số nguyên:
cnt[x]++;
Bạn đang:
•
chuyển dãy số thành bản đồ tần suất
•
tìm xem có bao nhiêu giá trị khác nhau
•
tìm xem giá trị nào xuất hiện nhiều nhất
Trong xử lý ảnh:
•
mỗi đặc trưng (feature) cũng được xem như một “giá trị”
•
hệ thống đếm xem đặc trưng nào xuất hiện bao nhiêu lần
•
so sánh tần suất giữa các ảnh
Tư duy là giống nhau:
→ biến dữ liệu thô thành “bản đồ tần suất” để so sánh.
3. Vì sao kỹ thuật này mạnh?
Vì nó:
•
nhanh (O(1) trung bình)
•
không cần sắp xếp
•
không cần biết trước giá trị
•
xử lý được dữ liệu lớn
•
dễ mở rộng sang nhiều dạng dữ liệu khác nhau
Đó là lý do tại sao:
•
Google dùng hashing + tần suất để tìm ảnh tương tự
•
Các thuật toán NLP dùng hashing để đếm từ
•
Các hệ thống chống spam dùng hashing để phát hiện mẫu lặp
•
Các hệ thống phát hiện đạo văn dùng fingerprint + tần suất
•
Các thuật toán big data dùng hashing để phân loại dữ liệu
Và trong lập trình thi đấu, unordered_map là “vũ khí” cực mạnh.
4. Tóm lại
Bạn nhận xét rất tinh:
“Có vẻ giống kỹ thuật search tìm ảnh gốc hay tương tự trong Google.”
Đúng — tư duy nền tảng là giống nhau:
→ chuyển dữ liệu thành bản đồ tần suất để so sánh, phân loại, nhận dạng.
Chỉ khác là:
•
Google làm với đặc trưng ảnh
•
Bạn đang làm với số nguyên
/////////////////
Bài 4 vườn cây
(Tính chu vi từng vùng)
#include
using namespace std;
int a[105][105];
int m, n;
int ans = 0;
// 4 hướng: lên – phải – xuống – trái
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool insize(int u, int v) {
return (u >= 1 && u <= m && v >= 1 && v <= n);
}
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
cin >> m >> n;
// đọc ma trận cây
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// duyệt 4 hướng
for (int k = 0; k < 4; k++) {
int u = i + dx[k];
int v = j + dy[k];
// nếu ô bên cạnh hợp lệ
if (insize(u, v)) {
// nếu khác loại → cần dây
if (a[i][j] != a[u][v]) {
ans++;
}
}
}
}
}
cout << ans;
return 0;
}
Ý tưởng thật sự của bài này là gì?
Dựa vào cấu trúc:
•
Có ma trận a[m][n]
•
Có 4 hướng tx, ty
•
Có hàm backtrack(u, v)
•
Có đánh dấu a[u][v] = -1
•
Có đếm ans++ khi gặp ô khác loại
→ Đây là thuật toán duyệt vùng (region flood-fill) để:
Đếm số cạnh biên giữa một vùng cây và các vùng cây khác.
Nói cách khác:
•
Mỗi vùng cây cùng loại là một “khu vực”.
•
Khi duyệt một ô, nếu cạnh bên cạnh nó là cây khác loại → tăng ans.
•
Sau đó lan sang các ô cùng loại để duyệt tiếp.
Đây là dạng bài đếm chu vi của một vùng, hoặc đếm số tiếp xúc giữa các vùng khác nhau.
Không liên quan đến “độ dài dây giữa hai cây kề nhau cùng loại”.
2. Phân tích chi tiết từng đoạn code
2.1. Mảng hướng
int tx[] = {-1, 0, 1, 0}; int ty[] = {0, 1, 0, -1};
→ Duyệt 4 hướng: lên – phải – xuống – trái.
2.2. Hàm kiểm tra trong biên
bool insize(int u, int v) { return (1 <= u && u <= m && 1 <= v && v <= n); }
→ Kiểm tra ô (u, v) có nằm trong ma trận không.
2.3. Hàm backtrack (thực chất là DFS)
(1) Đếm biên tiếp xúc với cây khác loại
for (int k = 0; k < 4; k++) { int u1 = u + tx[k], v1 = v + ty[k]; if (a[u1][v1] != -1 && a[u1][v1] !=
a[u][v]) ans++; }
Ý nghĩa:
•
Nếu ô bên cạnh khác loại → tăng ans.
Đây là đếm số cạnh biên giữa vùng này và vùng khác.
(2) Đánh dấu đã thăm
a[u][v] = -1;
→ Đánh dấu ô này đã duyệt.
(3) Lan sang các ô cùng loại
for (int k = 0; k < 4; k++) { int u1 = u + tx[k], v1 = v + ty[k]; if (insize(u1, v1) && a[u1][v1] != -1 &&
a[u1][v1] == a[u][v]) backtrack(u1, v1); }
→ Nếu ô bên cạnh cùng loại → tiếp tục DFS.
////////////////
Duyệt ma trận vườn cây, chỉ xét 2 hướng (phải và xuống).
Nếu hai cây kề nhau khác loại → cần 1 đoạn dây.
Nếu cùng loại → không cần dây.
Ma trận phải kín, không có ô trống.
#include
using namespace std;
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
int m, n;
cin >> m >> n;
vector> a(m + 1, vector(n + 1));
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
long long ans = 0;
// Duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Xét cạnh phải
if (j + 1 <= n && a[i][j] != a[i][j + 1])
ans++;
// Xét cạnh dưới
if (i + 1 <= m && a[i][j] != a[i + 1][j])
ans++;
}
}
// Cộng thêm 4 cạnh ngoài
ans += 2 * m + 2 * n;
cout << ans;
return 0;
}
//////////////////
vector(n + 1)
→ tạo một hàng có n + 1 phần tử, tất cả = 0.
(2) vector a(m + 1, ...)
→ tạo m + 1 bản sao của hàng trên
→ tức là tạo ma trận (m+1) × (n+1).
1. +1 dùng để tạo mảng từ chỉ số 1 thay vì 0
Trong C++:
•
Mảng bình thường bắt đầu từ 0
•
Nhưng khi làm bài toán ma trận, rất nhiều người thích dùng chỉ số 1..m và 1..n cho dễ
đọc, dễ hiểu.
Ba dạng bài thường gặp trong các bài “vườn cây”
1) Dạng A – Tính tổng dây phân cách giữa các cây khác loại
✔ Duyệt phải + xuống
✔ Không cần DFS
✔ Không đếm trùng
✔ Ma trận phải kín
✔ Công thức đơn giản, dễ hiểu
→ Đây chính là cách bạn đang dùng, và nó rất gọn.
2) Dạng B – Tính chu vi của từng vùng cây
✔ Cần DFS/BFS
✔ Phải đánh dấu đã thăm
✔ Mỗi cạnh tiếp xúc với vùng khác hoặc biên ngoài tính 1 lần
✔ Không cần ma trận kín
→ Đây là dạng “chu vi vùng” kinh điển.
3) Dạng C – Tính tổng dây bao quanh toàn bộ vườn
✔ Lấy kết quả dạng A
✔ Cộng thêm chu vi ngoài: 2m + 2n
→ Đây là dạng “rào vườn”.
Vì sao bạn cảm thấy có thể còn cách khác?
Vì tùy đề bài:
•
Nếu đề nói “tính dây phân cách” → dùng dạng A
•
Nếu đề nói “tính chu vi vùng” → dùng dạng B
•
Nếu đề nói “tính dây bao quanh vườn” → dùng dạng C
•
Nếu đề nói “tính số vùng cây” → lại là một dạng khác (đếm connected components)
Nhiều học sinh hay nhầm lẫn giữa các dạng này, nên code của các em thường “rối”, “lệch đề”,
hoặc “dùng DFS không cần thiết”.
Bài tham khảo:
#include
using namespace std;
int a[105][105];
int m, n;
int ans = 0;
// 4 hướng: lên – phải – xuống – trái
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool insize(int u, int v) {
return (u >= 1 && u <= m && v >= 1 && v <= n);
}
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
cin >> m >> n;
// đọc ma trận cây
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// duyệt 4 hướng
for (int k = 0; k < 4; k++) {
int u = i + dx[k];
int v = j + dy[k];
// nếu ô bên cạnh hợp lệ
if (insize(u, v)) {
// nếu khác loại → cần dây
if (a[i][j] != a[u][v]) {
ans++;
}
}
}
}
}
cout << ans;
return 0;
}
/////////////////
1. Ý tưởng bài toán (chuẩn)
Bạn có n vị trí trạm thu sóng trên một trục số (1 chiều).
Bạn muốn đặt k trạm phát sóng, mỗi trạm có bán kính phủ sóng = x.
Một trạm phát sóng đặt tại vị trí p sẽ phủ được đoạn:
[p-x,\; p+x]
Mục tiêu:
Tìm giá trị nhỏ nhất của x sao cho chỉ cần ≤ k trạm phát sóng là phủ hết n vị trí.
Đây là bài toán kinh điển:
•
Sắp xếp vị trí
•
Dùng tìm kiếm nhị phân trên đáp án x
•
Với mỗi x → kiểm tra xem cần bao nhiêu trạm phát sóng
•
Nếu ≤ k → thử giảm x
•
Nếu > k → phải tăng x
2. Thuật toán kiểm tra (hàm kt(x))
Đây là phần quan trọng nhất.
Với một giá trị x cho trước:
1. Đặt trạm phát sóng đầu tiên tại vị trí phủ được điểm đầu tiên a[1]
2. Trạm này phủ được đến a[1] + 2x
3. Tìm điểm đầu tiên nằm ngoài vùng phủ → đặt trạm thứ
•
Số học: sàng nguyên tố, ước – bội, phân tích thừa số, modulo
•
Mảng & chuỗi: prefix sum, two pointers, sliding window
•
Quy hoạch động: dãy con, chia tiền, xâu con chung
•
Đồ thị: BFS/DFS, đường đi ngắn nhất, cây
•
Tổ hợp – đếm: hoán vị, chỉnh hợp, phân hoạch số
Bài HSG thường xoay quanh:
•
Sàng nguyên tố
•
Mảng cộng dồn
•
Hai con trỏ
•
Quy hoạch động cơ bản
•
Đệ quy + chia để trị
•
Đồ thị cơ bản (DFS/BFS)
#include
#define N 10000000
// Gộp toàn bộ thư viện STL
// Giới hạn tối đa cho mảng sàng nguyên tố
using namespace std;
int nt[N];
int l, r;
// Mảng đánh dấu số nguyên tố: nt[x] = 1 nếu x là số nguyên tố
// Khoảng cần xét
// Hàm sàng nguyên tố Eratosthenes
void sangnt(int n)
{
fill(nt + 2, nt + n + 1, 1); // Gán nt[2..n] = 1 (giả sử ban đầu tất cả đều là số nguyên tố)
for (int i = 2; i * i <= n; i++) // Duyệt đến sqrt(n)
if (nt[i] == 1)
// Nếu i là số nguyên tố
for (int j = i * i; j <= n; j += i)
nt[j] = 0;
// Đánh dấu các bội số của i không phải số nguyên tố
}
// Hàm tính tổng chữ số của x
int tongcs(int x)
{
int s = 0;
while (x > 0)
{
s += x % 10; // Lấy chữ số cuối
x /= 10;
// Bỏ chữ số cuối
}
return s;
}
int main()
{
freopen("password.inp", "r", stdin); // Đọc từ file
freopen("password.out", "w", stdout); // Ghi ra file
cin >> l >> r;
// Nhập khoảng [l, r]
sangnt(r);
// Sàng nguyên tố đến r
// Duyệt tất cả các số từ 1 đến r
{ nên for (int x = l; x <= r; x++)
if (nt[x] == 1 && nt[tongcs(x)] == 1)
cout << x << " "; }
for (int x = 1; x <= r; x++)
// Điều kiện mật khẩu:
// 1. x là số nguyên tố
// 2. Tổng chữ số của x cũng là số nguyên tố
if (nt[x] == 1 && nt[tongcs(x)] == 1)
cout << x << " ";
return 0;
}
//////////////////////////
1. #include là gì?
Đây là một header tổng hợp, chỉ có trên trình biên dịch GCC (g++), không phải chuẩn của C++.
Nó chứa gần như tất cả các thư viện STL:
•
… và rất nhiều nữa.
•
fill
là hàm có sẵn trong C++, nằm trong thư viện .
Nó không phải thủ tục bạn tự viết, mà là hàm chuẩn của STL.
fill(begin, end, value);
begin: con trỏ hoặc iterator bắt đầu
•
end: con trỏ hoặc iterator kết thúc (không bao gồm vị trí này)
•
value: giá trị muốn gán
#define N 10000000
Đây là macro trong C++.
Nó có nghĩa là:
•
Mỗi khi gặp chữ N, trình biên dịch sẽ thay bằng 10000000.
////////////////
Chương trình nhận vào một chuỗi ký tự, trong đó có thể chứa chữ cái và chữ số lẫn lộn, ví dụ:
ab12c3d12x7
Nhiệm vụ:
•
Tách tất cả các số xuất hiện trong chuỗi
•
Đánh dấu số nào đã xuất hiện
•
Đếm xem có bao nhiêu số khác nhau
for (; j < s.size() && ... ; j++)
Nghĩa là: không khởi tạo gì trong vòng for
→ vì biến j đã được khởi tạo từ trước: viết đầy đủ sẽ thành
for (int j = i; j < s.size() && ...; j++)
ios::sync_with_stdio(false);
cin.tie(nullptr);
1. ios::sync_with_stdio(false); — Tắt đồng bộ C và C++
Ý nghĩa:
C++ có hai hệ thống nhập/xuất:
•
cin, cout (C++)
•
scanf, printf (C)
Mặc định, C++ đồng bộ hai hệ thống này để tránh lỗi, nhưng điều đó làm chương trình chậm
hơn.
Khi bạn viết:
ios::sync_with_stdio(false);
Bạn tắt đồng bộ, nghĩa là:
•
cin và cout chạy độc lập
•
tốc độ tăng lên đáng kể (nhanh gấp 2–3 lần)
⚠ Lưu ý quan trọng:
Khi đã tắt đồng bộ:
•
KHÔNG được dùng lẫn lộn cin với printf, hoặc cout với scanf.
2. cin.tie(nullptr); — Bỏ buộc cin với cout
Mặc định:
•
cin bị “buộc” với cout
•
Mỗi lần gọi cin, hệ thống sẽ tự động flush (đẩy ra màn hình) cout
Điều này an toàn nhưng làm chậm.
Khi bạn viết:
cin.tie(nullptr);
Bạn tháo buộc này ra.
Kết quả:
•
cin không còn ép cout phải flush nữa
•
tốc độ nhập/xuất tăng lên
MỤC TIÊU CỦA CHƯƠNG TRÌNH
Chương trình nhận vào một chuỗi ký tự, trong đó có thể chứa chữ cái và chữ số lẫn lộn, ví dụ:
ab12c3d12x7
Nhiệm vụ:
•
Tách tất cả các số xuất hiện trong chuỗi
•
Đánh dấu số nào đã xuất hiện
•
Đếm xem có bao nhiêu số khác nhau
Ví dụ trên → các số xuất hiện:
12, 3, 7 → có 3 số khác nhau.
PHÂN TÍCH TỪNG DÒNG LỆNH
#include
Gộp tất cả thư viện STL vào một file (chỉ có trên g++).
Giúp code ngắn hơn.
const int MAXN = 1001;
Đặt giới hạn tối đa cho số có thể xuất hiện trong chuỗi.
→ Các số trong chuỗi được giả sử nhỏ hơn 1000.
string s;
Chuỗi đầu vào.
int imam[MAXN];
Mảng đánh dấu:
•
imam[x] = 1 nghĩa là số x đã xuất hiện trong chuỗi
•
imam[x] = 0 nghĩa là chưa xuất hiện
Tối ưu nhập xuất
ios::sync_with_stdio(false); cin.tie(nullptr);
Giúp chương trình chạy nhanh hơn (chuẩn competitive programming).
Đọc file nếu có
if (fopen("mm.inp", "r")) { freopen("mm.inp", "r", stdin); freopen("mm.out", "w", stdout); }
Nếu tồn tại file mm.inp, chương trình sẽ:
•
đọc từ file mm.inp
•
ghi ra file mm.out
Nếu không có file → đọc từ bàn phím bình thường.
Đọc chuỗi
cin >> s;
Lưu ý: chỉ đọc đến dấu cách đầu tiên.
(Đề bài có thể đảm bảo chuỗi không chứa khoảng trắng.)
VÒNG LẶP CHÍNH – TÁCH SỐ TRONG CHUỖI
for (int i = 0; i < (int)s.size(); i++)
Duyệt từng ký tự trong chuỗi.
Bỏ qua chữ cái
if (s[i] >= 'a' && s[i] <= 'z') continue;
Nếu là chữ thường → bỏ qua.
(Chỉ xử lý chữ số.)
Bắt đầu ghép số
int broj = 0; int j = i;
•
broj = số đang được ghép (tên tiếng Croatia, nghĩa là “number”)
•
j = vị trí chạy để ghép số
Ghép các chữ số liên tiếp thành một số nguyên
for (; j < (int)s.size() && s[j] >= '0' && s[j] <= '9'; j++) { broj *= 10; broj += s[j] - '0'; }
Ví dụ chuỗi: ab123cd
Khi gặp 1:
•
broj = 1
•
gặp 2 → broj = 12
•
gặp 3 → broj = 123
Vòng lặp dừng khi gặp ký tự không phải số.
Đánh dấu số đã xuất hiện
imam[broj] = 1;
Ví dụ: nếu số 123 xuất hiện → imam[123] = 1.
Nhảy i đến cuối số vừa đọc
i = j - 1;
Giúp tránh đọc lại các chữ số đã xử lý.
ĐẾM BAO NHIÊU SỐ KHÁC NHAU
int rj = 0; for (int i = 0; i < MAXN; i++) { rj += imam[i]; }
Vì mỗi số chỉ được đánh dấu 0 hoặc 1, nên tổng chính là số lượng số khác nhau.
🖨
In kết quả
cout << rj << endl;
TÓM TẮT NGẮN GỌN CHO GIÁO VIÊN
Chương trình:
1. Đọc chuỗi
2. Tách các số liên tiếp trong chuỗi
3. Đánh dấu số nào xuất hiện
4. Đếm số lượng số khác nhau
5. In kết quả
Thuật toán chạy rất nhanh, phù hợp bài HSG.
#include
// Gộp toàn bộ thư viện STL (chỉ có trên g++)
using namespace std;
const int MAXN = 1001;
string s;
// Giới hạn số tối đa có thể xuất hiện trong chuỗi
// Chuỗi đầu vào
int imam[MAXN];
// Mảng đánh dấu: imam[x] = 1 nghĩa là số x đã xuất hiện
int main()
{
ios::sync_with_stdio(false); // Tăng tốc độ nhập/xuất (tắt đồng bộ với stdio C)
cin.tie(nullptr);
// Không buộc cin phải flush cout → nhanh hơn
// Nếu tồn tại file mm.inp → đọc từ file, ghi ra file mm.out
if (fopen("mm.inp", "r"))
{
freopen("mm.inp", "r", stdin);
freopen("mm.out", "w", stdout);
}
cin >> s;
// Đọc chuỗi (không chứa khoảng trắng)
// Duyệt từng ký tự trong chuỗi
for (int i = 0; i < (int)s.size(); i++)
{
// Nếu ký tự là chữ cái thường → bỏ qua
if (s[i] >= 'a' && s[i] <= 'z')
continue;
int broj = 0;
int j = i;
// Biến để ghép số (broj = "number" theo tiếng Croatia)
// j bắt đầu từ vị trí i
// Ghép các chữ số liên tiếp thành một số nguyên
for (; j < (int)s.size() && s[j] >= '0' && s[j] <= '9'; j++)
{
broj *= 10;
// Dịch trái (nhân 10)
broj += s[j] - '0'; // Cộng chữ số hiện tại
}
imam[broj] = 1;
i = j - 1;
// Đánh dấu số này đã xuất hiện
// Nhảy i đến cuối dãy số vừa đọc
}
int rj = 0;
// rj = kết quả: số lượng số khác nhau
// Đếm xem có bao nhiêu số đã được đánh dấu
for (int i = 0; i < MAXN; i++)
{
rj += imam[i];
// imam[i] = 1 → số đó xuất hiện
}
cout << rj << endl;
// In kết quả
return 0;
}
Chương trình thực hiện:
1. Đọc chuỗi gồm chữ cái và chữ số lẫn lộn
2. Tách tất cả các số nguyên xuất hiện trong chuỗi
3. Đánh dấu số nào đã xuất hiện
4. Đếm số lượng số khác nhau
5. In kết quả
//////////////////////////////
getline(cin, str); dùng để làm gì?
Lệnh này đọc cả một dòng văn bản từ bàn phím (hoặc file) và lưu vào biến chuỗi str.
Khác với cin >> str, getline sẽ:
•
Đọc toàn bộ dòng, kể cả khoảng trắng
•
Dừng lại khi gặp ký tự xuống dòng (\n)
•
Không bỏ qua khoảng trắng
cin >> n;
cin.ignore(); // bỏ ký tự '\n' còn lại
getline(cin, s);
/////////////////////////////////////////
#include
#define K 200000
// Gộp toàn bộ thư viện STL (tiện cho bài thi)
// Giới hạn tối đa cho chỉ số Fibonacci cần tính
#define MOD 10000000007
#define ll long long
// Số modulo rất lớn để tránh tràn số
// Viết tắt kiểu long long
using namespace std;
ll F[K + 2], ans;
int n, k;
// Mảng Fibonacci và biến lưu tổng
// Hai số đầu vào
int main()
{
freopen("flashback.inp", "r", stdin); // Đọc từ file (nếu có)
freopen("flashback.out", "w", stdout); // Ghi ra file
cin >> n >> k;
// Nhập n và k
F[1] = F[2] = 1;
// Khởi tạo hai số Fibonacci đầu tiên
ans = 2;
// F[2] = 1 và F[0] không dùng → tổng ban đầu = 1 + 1 = 2
// Tính Fibonacci từ F[3] đến F[2*k]
for (int i = 3; i <= 2 * k; i++)
{
F[i] = (F[i - 1] + F[i - 2]) % MOD; // Công thức Fibonacci chuẩn
if (i % 2 == 0)
// Nếu chỉ số i là số chẵn
ans = (ans + F[i]) % MOD;
// Cộng vào tổng
}
// Kết quả cuối cùng là tổng Fibonacci chẵn nhân với n
cout << (ans * n) % MOD;
return 0;
}
///////////////
1. Tránh tràn số (integer overflow)
Khi nào bị tràn số?
Khi giá trị vượt quá giới hạn kiểu dữ liệu:
•
int tối đa khoảng 2 tỷ
•
long long tối đa khoảng 9×10¹⁸
•
Fibonacci, lũy thừa, nhân lớn… rất dễ vượt giới hạn
✔ Cách tránh tràn số
•
Dùng kiểu lớn hơn: long long, unsigned long long
•
Dùng modulo:
Ví dụ:
F[i] = (F[i-1] + F[i-2]) % MOD;
•
→ giữ số luôn nhỏ hơn MOD → không bao giờ tràn
•
Dùng thư viện big integer (nếu cần số cực lớn)
•
C++: boost::multiprecision::cpp_int
•
Python: tự động hỗ trợ số lớn
2. Tránh tràn bộ nhớ (memory overflow)
Khi nào bị tràn bộ nhớ?
•
Khai báo mảng quá lớn (ví dụ int a[10^9])
•
Dùng đệ quy quá sâu
•
Cấp phát động không kiểm soát
✔ Cách tránh
•
Dùng vector thay vì mảng tĩnh
vector a(n);
•
Chỉ cấp phát đúng kích thước cần thiết
•
Tránh đệ quy sâu → chuyển sang vòng lặp hoặc dùng stack tự quản lý
•
Không tạo mảng trong hàm quá lớn
(stack chỉ khoảng 1–8 MB)
3. Tránh quá tải CPU (chạy quá lâu)
Khi nào bị quá tải?
•
Vòng lặp quá lớn: O(n²), O(n³)
•
Thuật toán không tối ưu
•
Duyệt lại dữ liệu nhiều lần không cần thiết
✔ Cách tránh
•
Tối ưu thuật toán:
o
Dùng mảng cộng dồn
o
Dùng sàng nguyên tố
o
Dùng quy hoạch động
o
Dùng hai con trỏ
•
Giảm số vòng lặp lồng nhau
•
Dùng cấu trúc dữ liệu phù hợp
(set, map, priority_queue…)
4. Tránh quá tải I/O (nhập xuất quá chậm)
Khi nào bị chậm?
•
In/đọc hàng triệu dòng bằng cin/cout
✔ Cách tăng tốc
•
Dùng:
ios::sync_with_stdio(false); cin.tie(nullptr);
•
Hoặc dùng scanf/printf nếu cần tốc độ cao
🛡 5. Tránh lỗi logic gây crash chương trình
✔ Kiểm tra chỉ số mảng
if (i >= 0 && i < n)
✔ Tránh chia cho 0
if (b != 0) x = a / b;
✔ Kiểm tra dữ liệu đầu vào
•
Không đọc chuỗi rỗng
•
Không dùng biến chưa khởi tạo
Tóm tắt 1 câu dễ nhớ
Muốn tránh tràn số → dùng modulo.
Muốn tránh tràn bộ nhớ → dùng vector.
Muốn tránh quá tải CPU → tối ưu thuật toán.
Muốn tránh chậm I/O → bật sync off + tie nullptr.
//////////////////////////
1. Khi đã dùng freopen, bạn xử lý dữ liệu y như nhập từ bàn phím
Ví dụ:
freopen("password.inp","r",stdin); cin >> x;
Lúc này:
•
cin >> x; không đọc từ bàn phím
•
mà đọc giá trị từ file password.inp
•
và gán vào biến x đúng kiểu dữ liệu bạn khai báo (int, long long, string…)
Bạn xử lý biến x hoàn toàn bình thường, không khác gì nhập từ bàn phím.
2. Ví dụ minh họa
Giả sử file password.inp chứa:
10 50
Code:
int l, r; freopen("password.inp","r",stdin); cin >> l >> r;
Sau khi chạy:
•
l = 10
•
r = 50
Bạn xử lý tiếp:
for (int i = l; i <= r; i++) cout << i << " ";
3. Tóm lại
•
freopen("file.inp", "r", stdin); → thay nguồn nhập bằng file
•
cin >> x; → đọc dữ liệu từ file vào biến x
•
Bạn xử lý x như biến bình thường
•
Không cần lệnh đặc biệt nào khác
/////////////////
Not ! and && or ||
#include
using namespace std;
int main()
{
freopen("mm.inp","r",stdin);
freopen("mm.out","w",stdout);
string s;
getline(cin, s);
int dem = 0;
bool dang_trong_day_so = false;
for (char c : s)
{
if (isdigit(c))
{
if (!dang_trong_day_so)
{
dem++;
// bắt đầu dãy số mới
dang_trong_day_so = true; // đánh dấu đang trong dãy
}
}
else
{
dang_trong_day_so = false;
}
}
// kết thúc dãy số
cout << dem;
return 0;
}
//////////////////////////////
Tóm nhanh ý nghĩa thuật toán
•
Đề ngầm hiểu: cho dãy gồm n số nguyên.
•
Bài làm:
o
Đếm xem có bao nhiêu số khác nhau trong dãy (Q).
o
Tìm xem giá trị nào xuất hiện nhiều nhất, với tần suất bao nhiêu (P).
•
Về kỹ thuật lập trình:
•
Dùng unordered_map để đếm tần suất là rất chuẩn, rất hiện đại.
•
Duyệt bằng for (auto &p : cnt) là cách viết ngắn, rõ, nên khuyến khích.
#include
using namespace std;
int main() {
// Đọc từ file mm.inp, ghi ra file mm.out
freopen("mm.inp", "r", stdin);
freopen("mm.out", "w", stdout);
int n;
cin >> n; // đọc số lượng phần tử
unordered_map
for (int i = 0; i < n; i++) { // chú ý: < n, không phải <= n
int x;
cin >> x;
cnt[x]++; // tăng số lần xuất hiện của giá trị x
}
int Q = cnt.size(); // số lượng giá trị khác nhau
int P = 0;
// tần suất lớn nhất
// duyệt qua từng cặp (key, value) trong cnt
for (auto &p : cnt) {
P = max(P, p.second); // p.second là số lần xuất hiện của p.first
}
cout << Q << "\n" << P;
return 0;
}
3. unordered_map cnt;
•
•
Đây là một cấu trúc dữ liệu ánh xạ (bản đồ) từ:
o
key: int (giá trị x trong dãy)
o
value: int (số lần x xuất hiện)
Ta dùng nó như một cái “từ điển”:
o
cnt[x] = số lần xuất hiện của giá trị x.
•
Vì là unordered_map nên:
•
Các phần tử không sắp xếp theo thứ tự tăng dần của key.
•
Tra cứu / thêm / tăng đếm thường rất nhanh (trung bình O(1)).
Ví dụ: nếu dãy là 5 7 5 5 9
thì sau vòng lặp:
•
cnt[5] = 3
•
cnt[7] = 1
•
cnt[9] = 1
2.4. Vòng lặp nhập và đếm:
for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }
•
for (int i = 0; i < n; i++): lặp đúng n lần, mỗi lần đọc 1 số.
•
•
cnt[x]++:
o
Nếu x chưa từng xuất hiện → cnt[x] tự động khởi tạo = 0, rồi tăng lên 1.
o
Nếu x đã xuất hiện → tăng số lần thêm 1.
Đây là mẫu rất chuẩn để đếm tần suất xuất hiện của các giá trị.
2.5. int Q = cnt.size();
•
cnt.size() trả về số lượng key khác nhau trong unordered_map.
•
Nghĩa là: có bao nhiêu giá trị phân biệt trong dãy.
•
Ví dụ:
•
Dãy: 5 7 5 5 9
•
Các key: 5, 7, 9 → cnt.size() = 3 → Q = 3.
2.6. Duyệt unordered_map bằng for (auto &p : cnt)
int P = 0; for (auto &p : cnt) P = max(P, p.second);
•
auto &p:
o
p là một cặp pair đại diện cho một phần tử trong cnt.
o
p.first là key (giá trị x).
o
p.second là value (số lần x xuất hiện).
o
Dùng auto để đỡ phải viết kiểu dài dòng.
•
P = max(P, p.second);
•
p.second là tần suất của một giá trị nào đó.
•
Lần lượt lấy giá trị lớn nhất trong tất cả các p.second.
→ Kết quả: P là số lần xuất hiện nhiều nhất của một giá trị trong dãy.
Ví dụ dãy 5 7 5 5 9:
•
cnt[5] = 3
•
cnt[7] = 1
•
cnt[9] = 1
Duyệt:
•
gặp 5 → P = max(0, 3) = 3
•
gặp 7 → P = max(3, 1) = 3
•
gặp 9 → P = max(3, 1) = 3
Kết quả: P = 3.
2.7. In kết quả
cout << Q << "\n" << P;
•
In:
•
Dòng 1: số lượng giá trị khác nhau.
•
Dòng 2: tần suất lớn nhất.
Vì sao kỹ thuật này mạnh?
1. Đếm nhanh như chớp (trung bình O(1) mỗi lần)
unordered_map dùng bảng băm, nên mỗi lần tăng đếm:
cnt[x]++;
gần như tức thì, không cần tìm kiếm tuyến tính hay nhị phân.
2. Không cần biết trước giá trị lớn hay nhỏ
Dãy có thể chứa:
•
số âm
•
số lớn hàng triệu
•
số lặp lại
•
số không theo thứ tự
→ unordered_map vẫn xử lý gọn.
3. Tự động tạo key mới khi gặp giá trị mới
Không cần kiểm tra tồn tại:
if (cnt.find(x) == cnt.end()) ...
Chỉ cần:
cnt[x]++;
Nếu x chưa có → tự tạo với giá trị 0 rồi tăng lên 1.
4. Duyệt tất cả giá trị phân biệt rất dễ
for (auto &p : cnt) { // p.first = giá trị // p.second = số lần xuất hiện }
Không cần mảng đánh dấu, không cần sort.
5. Giải được rất nhiều dạng bài
Kỹ thuật này xuất hiện trong:
•
đếm số khác nhau
•
tìm phần tử xuất hiện nhiều nhất
•
tìm mode
•
kiểm tra tần suất
•
phát hiện phần tử xuất hiện 1 lần
•
xử lý dãy lớn không thể sort
•
bài toán mật mã, tần suất ký tự
•
bài toán thống kê dữ liệu
Nói cách khác: đây là một trong những kỹ thuật “đinh” của lập trình thi đấu và xử lý dữ liệu.
Bạn dạy học sinh kỹ thuật này là cực kỳ tốt
Nhiều em chỉ biết sort rồi đếm, hoặc dùng mảng đánh dấu, nhưng khi gặp:
•
giá trị âm
•
giá trị lớn
•
giá trị không liên tục
→ là “tắc đường”.
unordered_map giúp vượt qua tất cả những hạn chế đó.
1. Google tìm ảnh gốc / ảnh tương tự hoạt động thế nào?
Google không so sánh từng pixel (quá chậm).
Thay vào đó, họ chuyển ảnh thành một tập các đặc trưng (features), ví dụ:
•
màu sắc chủ đạo
•
các cạnh (edges)
•
các điểm đặc biệt (keypoints)
•
mô tả đặc trưng (descriptors) như SIFT, SURF, ORB
•
fingerprint của ảnh
Sau đó họ đếm tần suất hoặc so khớp tần suất của các đặc trưng này.
Ví dụ:
•
Ảnh A có 120 điểm đặc trưng loại X
•
Ảnh B có 118 điểm đặc trưng loại X
→ Khả năng cao là ảnh giống nhau.
Đây chính là dạng đếm tần suất đặc trưng.
2. Liên hệ với unordered_map trong bài toán của bạn
Trong bài toán số nguyên:
cnt[x]++;
Bạn đang:
•
chuyển dãy số thành bản đồ tần suất
•
tìm xem có bao nhiêu giá trị khác nhau
•
tìm xem giá trị nào xuất hiện nhiều nhất
Trong xử lý ảnh:
•
mỗi đặc trưng (feature) cũng được xem như một “giá trị”
•
hệ thống đếm xem đặc trưng nào xuất hiện bao nhiêu lần
•
so sánh tần suất giữa các ảnh
Tư duy là giống nhau:
→ biến dữ liệu thô thành “bản đồ tần suất” để so sánh.
3. Vì sao kỹ thuật này mạnh?
Vì nó:
•
nhanh (O(1) trung bình)
•
không cần sắp xếp
•
không cần biết trước giá trị
•
xử lý được dữ liệu lớn
•
dễ mở rộng sang nhiều dạng dữ liệu khác nhau
Đó là lý do tại sao:
•
Google dùng hashing + tần suất để tìm ảnh tương tự
•
Các thuật toán NLP dùng hashing để đếm từ
•
Các hệ thống chống spam dùng hashing để phát hiện mẫu lặp
•
Các hệ thống phát hiện đạo văn dùng fingerprint + tần suất
•
Các thuật toán big data dùng hashing để phân loại dữ liệu
Và trong lập trình thi đấu, unordered_map là “vũ khí” cực mạnh.
4. Tóm lại
Bạn nhận xét rất tinh:
“Có vẻ giống kỹ thuật search tìm ảnh gốc hay tương tự trong Google.”
Đúng — tư duy nền tảng là giống nhau:
→ chuyển dữ liệu thành bản đồ tần suất để so sánh, phân loại, nhận dạng.
Chỉ khác là:
•
Google làm với đặc trưng ảnh
•
Bạn đang làm với số nguyên
/////////////////
Bài 4 vườn cây
(Tính chu vi từng vùng)
#include
using namespace std;
int a[105][105];
int m, n;
int ans = 0;
// 4 hướng: lên – phải – xuống – trái
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool insize(int u, int v) {
return (u >= 1 && u <= m && v >= 1 && v <= n);
}
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
cin >> m >> n;
// đọc ma trận cây
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// duyệt 4 hướng
for (int k = 0; k < 4; k++) {
int u = i + dx[k];
int v = j + dy[k];
// nếu ô bên cạnh hợp lệ
if (insize(u, v)) {
// nếu khác loại → cần dây
if (a[i][j] != a[u][v]) {
ans++;
}
}
}
}
}
cout << ans;
return 0;
}
Ý tưởng thật sự của bài này là gì?
Dựa vào cấu trúc:
•
Có ma trận a[m][n]
•
Có 4 hướng tx, ty
•
Có hàm backtrack(u, v)
•
Có đánh dấu a[u][v] = -1
•
Có đếm ans++ khi gặp ô khác loại
→ Đây là thuật toán duyệt vùng (region flood-fill) để:
Đếm số cạnh biên giữa một vùng cây và các vùng cây khác.
Nói cách khác:
•
Mỗi vùng cây cùng loại là một “khu vực”.
•
Khi duyệt một ô, nếu cạnh bên cạnh nó là cây khác loại → tăng ans.
•
Sau đó lan sang các ô cùng loại để duyệt tiếp.
Đây là dạng bài đếm chu vi của một vùng, hoặc đếm số tiếp xúc giữa các vùng khác nhau.
Không liên quan đến “độ dài dây giữa hai cây kề nhau cùng loại”.
2. Phân tích chi tiết từng đoạn code
2.1. Mảng hướng
int tx[] = {-1, 0, 1, 0}; int ty[] = {0, 1, 0, -1};
→ Duyệt 4 hướng: lên – phải – xuống – trái.
2.2. Hàm kiểm tra trong biên
bool insize(int u, int v) { return (1 <= u && u <= m && 1 <= v && v <= n); }
→ Kiểm tra ô (u, v) có nằm trong ma trận không.
2.3. Hàm backtrack (thực chất là DFS)
(1) Đếm biên tiếp xúc với cây khác loại
for (int k = 0; k < 4; k++) { int u1 = u + tx[k], v1 = v + ty[k]; if (a[u1][v1] != -1 && a[u1][v1] !=
a[u][v]) ans++; }
Ý nghĩa:
•
Nếu ô bên cạnh khác loại → tăng ans.
Đây là đếm số cạnh biên giữa vùng này và vùng khác.
(2) Đánh dấu đã thăm
a[u][v] = -1;
→ Đánh dấu ô này đã duyệt.
(3) Lan sang các ô cùng loại
for (int k = 0; k < 4; k++) { int u1 = u + tx[k], v1 = v + ty[k]; if (insize(u1, v1) && a[u1][v1] != -1 &&
a[u1][v1] == a[u][v]) backtrack(u1, v1); }
→ Nếu ô bên cạnh cùng loại → tiếp tục DFS.
////////////////
Duyệt ma trận vườn cây, chỉ xét 2 hướng (phải và xuống).
Nếu hai cây kề nhau khác loại → cần 1 đoạn dây.
Nếu cùng loại → không cần dây.
Ma trận phải kín, không có ô trống.
#include
using namespace std;
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
int m, n;
cin >> m >> n;
vector
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
long long ans = 0;
// Duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Xét cạnh phải
if (j + 1 <= n && a[i][j] != a[i][j + 1])
ans++;
// Xét cạnh dưới
if (i + 1 <= m && a[i][j] != a[i + 1][j])
ans++;
}
}
// Cộng thêm 4 cạnh ngoài
ans += 2 * m + 2 * n;
cout << ans;
return 0;
}
//////////////////
vector(n + 1)
→ tạo một hàng có n + 1 phần tử, tất cả = 0.
(2) vector
→ tạo m + 1 bản sao của hàng trên
→ tức là tạo ma trận (m+1) × (n+1).
1. +1 dùng để tạo mảng từ chỉ số 1 thay vì 0
Trong C++:
•
Mảng bình thường bắt đầu từ 0
•
Nhưng khi làm bài toán ma trận, rất nhiều người thích dùng chỉ số 1..m và 1..n cho dễ
đọc, dễ hiểu.
Ba dạng bài thường gặp trong các bài “vườn cây”
1) Dạng A – Tính tổng dây phân cách giữa các cây khác loại
✔ Duyệt phải + xuống
✔ Không cần DFS
✔ Không đếm trùng
✔ Ma trận phải kín
✔ Công thức đơn giản, dễ hiểu
→ Đây chính là cách bạn đang dùng, và nó rất gọn.
2) Dạng B – Tính chu vi của từng vùng cây
✔ Cần DFS/BFS
✔ Phải đánh dấu đã thăm
✔ Mỗi cạnh tiếp xúc với vùng khác hoặc biên ngoài tính 1 lần
✔ Không cần ma trận kín
→ Đây là dạng “chu vi vùng” kinh điển.
3) Dạng C – Tính tổng dây bao quanh toàn bộ vườn
✔ Lấy kết quả dạng A
✔ Cộng thêm chu vi ngoài: 2m + 2n
→ Đây là dạng “rào vườn”.
Vì sao bạn cảm thấy có thể còn cách khác?
Vì tùy đề bài:
•
Nếu đề nói “tính dây phân cách” → dùng dạng A
•
Nếu đề nói “tính chu vi vùng” → dùng dạng B
•
Nếu đề nói “tính dây bao quanh vườn” → dùng dạng C
•
Nếu đề nói “tính số vùng cây” → lại là một dạng khác (đếm connected components)
Nhiều học sinh hay nhầm lẫn giữa các dạng này, nên code của các em thường “rối”, “lệch đề”,
hoặc “dùng DFS không cần thiết”.
Bài tham khảo:
#include
using namespace std;
int a[105][105];
int m, n;
int ans = 0;
// 4 hướng: lên – phải – xuống – trái
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool insize(int u, int v) {
return (u >= 1 && u <= m && v >= 1 && v <= n);
}
int main() {
freopen("vuoncay.inp", "r", stdin);
freopen("vuoncay.out", "w", stdout);
cin >> m >> n;
// đọc ma trận cây
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// duyệt từng ô
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// duyệt 4 hướng
for (int k = 0; k < 4; k++) {
int u = i + dx[k];
int v = j + dy[k];
// nếu ô bên cạnh hợp lệ
if (insize(u, v)) {
// nếu khác loại → cần dây
if (a[i][j] != a[u][v]) {
ans++;
}
}
}
}
}
cout << ans;
return 0;
}
/////////////////
1. Ý tưởng bài toán (chuẩn)
Bạn có n vị trí trạm thu sóng trên một trục số (1 chiều).
Bạn muốn đặt k trạm phát sóng, mỗi trạm có bán kính phủ sóng = x.
Một trạm phát sóng đặt tại vị trí p sẽ phủ được đoạn:
[p-x,\; p+x]
Mục tiêu:
Tìm giá trị nhỏ nhất của x sao cho chỉ cần ≤ k trạm phát sóng là phủ hết n vị trí.
Đây là bài toán kinh điển:
•
Sắp xếp vị trí
•
Dùng tìm kiếm nhị phân trên đáp án x
•
Với mỗi x → kiểm tra xem cần bao nhiêu trạm phát sóng
•
Nếu ≤ k → thử giảm x
•
Nếu > k → phải tăng x
2. Thuật toán kiểm tra (hàm kt(x))
Đây là phần quan trọng nhất.
Với một giá trị x cho trước:
1. Đặt trạm phát sóng đầu tiên tại vị trí phủ được điểm đầu tiên a[1]
2. Trạm này phủ được đến a[1] + 2x
3. Tìm điểm đầu tiên nằm ngoài vùng phủ → đặt trạm thứ
Luyện thiết kế Web
Các ý kiến mới nhất