MỞ ĐẦU
Xin chào các bạn, chào mừng các bạn quay trở lại với series "Lên trình Thuật toán - Lập trình thi đấu 🏆".
Mình là Trần Minh Sáng (a.k.a Tờ Mờ Sáng học Lập trình), hiện tại mình cũng đang là admin của facebook page CLB Lập trình - THPT Ngọc Tảo
Nếu có duyên thì có thể các bạn đã từng đọc được những bài viết của mình trên đó 👋
Trong bài viết này, mình sẽ chia sẻ với các bạn 8 kỹ thuật phổ biến được nhiều anh em sử dụng trong các cuộc thi Lập trình thi đấu.
Bài viết không chỉ là liệt kê, mà mình sẽ phân tích chi tiết từng kỹ thuật, để các bạn có thể hiểu rõ những thứ mà trước giờ chúng ta đều thường xuyên sử dụng khi làm các contest trên các trang VNOI, Codeforces, SPOJ, ...
Các bạn có thể xem phiên bản video của bài viết này tại đây:
Khi xem solution của các bạn tham gia lập trình thi đấu, chắc hẳn các bạn sẽ thường xuyên nhìn thấy template điển hình như sau:
#include <bits/stdc++.h>
using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // Do something return 0;
}
1. #include <bits/stdc++.h>
-
Nếu bạn còn nhớ cảm giác khi được khai sáng với thư viện
<bits/stdc++.h>
, thì chắc hẳn đó là một cảm giác rất tuyệt vời. -
Khi mà không còn phải nhớ chi tiết việc cần include thư viện nào trong C++ Standard Library, khi muốn sử dụng các hàm trong đó nữa (nhưng khi đi làm thì có thể sẽ có cảm xúc ngược lại khi dùng
<bits/stdc++.h>
đó nha)
-
Chữ "
bits/
" chính là tên thư mục chứa file "stdc++.h
". Khi xem source code của filestdc++.h
, bạn sẽ thấy trong này gồm rất nhiều những câu lệnh#include
các thư viện chuẩn trong C++ nhưiostream
,string
,vector
,stack
,queue
, ... -
Điều này đồng nghĩa với việc, chỉ với 1 dòng
#include <bits/stdc++.h>
, bạn sẽ không còn phải nhớ và khai báo nhiều thư viện khi muốn sử dụng các hàm khác nhau nữa. -
Việc này đặc biệt hữu ích khi chúng ta đang tham gia các cuộc thi lập trình thi đấu, nơi mà mọi người cần tập trung nhiều hơn vào việc tìm ra thuật toán để giải quyết vấn đề một cách hiệu quả, thì rõ ràng
<bits/stdc++.h>
sẽ giúp anh em tiết kiệm được rất nhiều thời gian và hạn chế lỗi thiếu thư viện khi code ✅ -
Tuy nhiên, bước ra khỏi những cuộc thi này, đặc biệt là đến khi đi làm, việc sử dụng
<bits/stdc++.h>
lại không được khuyến khích ❌ -
Có 2 lý do chính như sau:
1.1. Tăng thời gian biên dịch
-
Bình thường khi cần dùng hàm của thư viện nào, chúng ta chỉ cần include thư viện đó, thì trình biên dịch sẽ thực hiện nhanh chóng.
-
Nhưng khi sử dụng
<bits/stdc++.h>
, trong header file này include rất nhiều những thư viện chuẩn của C++, tức là bao gồm cả những thư viện mà trong chương trình của chúng ta không cần dùng đến. Do đó, thời gian biên dịch sẽ lâu hơn ⏳ -
Đặc biệt là khi làm việc với những project lớn, thường xuyên phải code-run-test, mà biên dịch chương trình còn lâu nữa chắc chắn sẽ khiến cho anh em developer vô cùng khó chịu 🤬
1.2. Một số trình biên dịch không hỗ trợ
- Vì
<bits/stdc++.h>
chỉ là một phần của GNU C++ Standard Library (libstdc++), được sử dụng trong trình biên dịch GCC (GNU Compiler Collection), chứ không phải một thư viện chuẩn trong C++, nên các bạn sẽ có thể gặp lỗi khi build chương trình trên những trình biên dịch khác nhau.
-
Tóm lại,
-
Khi đi thi lập trình thi đấu, bạn có thể dùng
<bits/stdc++.h>
, nó không làm chương trình của bạn chạy chậm đi so với include từng thư viện đâu, chỉ làm chậm thời gian biên dịch thôi. Mà lập trình thi đấu thì đâu có chấm thời gian biên dịch đúng không nè 🤗 -
Oái oăm lắm thì có chăng là trường hợp cuộc thi mà các bạn tham gia sử dụng trình biên dịch trên máy chấm điểm không hỗ trợ
<bits/stdc++.h>
. Nhưng trường hợp này rất hiếm gặp, bản thân mình cũng chưa gặp bao giờ. -
Thế còn sau này đi làm dự án thì không nên dùng
<bits/stdc++.h>
nha, bị các anh gõ cho u đầu đó. 🥴
2. using namespace std;
-
Đây chắc hẳn là một trong những câu hỏi phổ biến của nhiều bạn khi mới học lập trình C++
-
Nếu dịch word-by-word thì
using namespace std;
sẽ có ý nghĩa như sau: -
Nhờ có câu lệnh này mà chương trình có thể hiểu các đối tượng như
cin
,cout
đến từnamespace
nào. -
Các
namespace
trong C++ sẽ giúp các đoạn code tách biệt lẫn nhau trong những "không gian" riêng2.1. Vấn đề
-
Cùng xem ví dụ dưới đây:
#include <bits/stdc++.h> namespace MyNamespace { class Person // Class này trùng tên với class dưới { public: string name; int age; }; class Person // Class này trùng tên với class trên { public: string name; int age; }; } using namespace MyNamespace; int main() { Person person; // Lỗi: "Person" is ambiguous person.name = "Trần Minh Sáng"; ... }
-
Trong đoạn code này mình tự khai báo ra một namespace riêng có tên là
MyNamespace
-
Trong namespace này, mình lại khai báo 2 class có trùng tên là
Person
-
Khi mình sử dụng class
Person
để khởi tạo đối tượng trong hàmmain()
, chương trình ngay lập tức báo lỗi “Person” is ambiguous, tức là nó “mơ hồ” không hiểu phải sử dụng class Person ở trên hay Person ở dưới. -
Từ đó chúng ta có thể kết luận: Trong cùng một namespace sẽ KHÔNG ĐƯỢC PHÉP có 2 class có tên giống nhau.
2.2. Cách khắc phục
-
Để khắc phục lỗi này, chúng ta có thể làm theo 2 cách:
-
Cách 1: Sửa tên class thứ hai thành
Person2
, để tránh trùng tên với class thứ nhất#include <bits/stdc++.h> namespace MyNamespace { class Person { public: string name; int age; }; class Person2 // Đổi tên class này để không còn trùng tên với class trên nữa { public: string name; int age; }; } using namespace MyNamespace; int main() { Person person; // Hết lỗi. Đối tượng person sẽ được khởi tạo từ class Person của namespace tên là MyNamespace person.name = "Trần Minh Sáng"; ... }
-
Cách 2: Tạo thêm một namespace khác là
YourNamespace
, và đưa 1 trong 2 classPerson
này sang namespace mới vừa tạo.#include <bits/stdc++.h> namespace MyNamespace { class Person // Mặc dù cùng có tên là Person, nhưng class này nằm ở namepsace khác với class bên dưới { public: string name; int age; }; } namespace YourNamespace // Tạo 1 namespace mới là YourNamespace { class Person // Mặc dù cùng có tên là Person, nhưng class này nằm ở namepsace khác với class bên trên { public: string name; int age; }; } int main() { MyNamespace::Person person; // Hết lỗi. Đối tượng person sẽ được khởi tạo từ class Person của namespace tên là MyNamespace person.name = "Trần Minh Sáng"; ... }
-
Sau đó, mình sẽ chỉ định rằng muốn sử dụng class
Person
của namespace nào bằng toán tử::
(thuật ngữ chuyên ngành gọi là scope resolution operator) -
Khi ấy, việc tồn tại 2 class cùng có tên là
Person
, nhưng nằm ở 2 namespace khác nhau, thì lại hoàn toàn hợp lệ. -
Khi đi làm, các bạn cũng sẽ thấy các anh chị tiền bối sẽ hay sử dụng toán tử
::
hơn làusing namespace
, để giúp tránh lỗi xung đột tên giữa các namespace với nhau. -
Ngoài ra, một namespace không nhất thiết chỉ xuất hiện trong 1 file, mà nó có thể nằm ở nhiều file riêng lẻ.
-
Bạn có thể xem source code của các thư viện
iostream
,heap
,deque
, ... cũng sẽ thấy sự xuất hiện của namespacestd
bao bọc lấy xung quanh đoạn code của các thư viện này. -
Điều này chỉ ra rằng: những hàm, biến, class, ... được khai báo bên trong đó đều thuộc về namespace
std
. -
Đó cũng là lý do tại sao khi include các thư viện này, các bạn chỉ cần “
using namespace std
“ là có thể sử dụng được các biến, hàm, class, ... nằm trong tất cả những thư viện ấy.
3. Input và Output
-
Trong C++, chúng ta thường xuyên sử dụng đối tượng
cin
vàcout
với ý nghĩa:cin
cout
Viết tắt của “character input” Viết tắt của “character output” Đọc dữ liệu đầu vào Xuất dữ liệu đầu ra
3.1. Đối tượng cin
-
Đối tượng
cin
, là một đối tượng được định nghĩa trong thư việniostream
, thuộc namespacestd
, dùng để đọc một thông tin nào đó từ thiết bị nhập chuẩn (mặc định là bàn phím), sau đó lưu thông tin đó vào một biến. -
Toán tử
>>
mà các bạn thường nhìn thấy giống như mũi tên chỉ sang bên phải (thuật ngữ chuyên ngành gọi là extraction operator) được dùng chung vớicin
, cho biết hướng đi của dữ liệu từ màn hình console vào một biến. -
Đầu vào của chương trình thường bao gồm các số hoặc các chuỗi, được phân tách bằng dấu cách và dấu xuống dòng (newline).
-
Khi đó, chúng có thể được đọc từ
cin
như đoạn code dưới đây:int a; string b; cin >> a >> b;
-
Đoạn code này có thể đọc được cả 2 input sau:
123 tmsangdev
và
123 tmsangdev
-
Dù là input sử dụng khoảng trắng hay sử dụng dấu xuống dòng (newline), thì biến a vẫn sẽ nhận được giá trị là
123
, và biến b sẽ vẫn nhận được giá trị là chuỗi"tmsangdev"
.
3.2. Đối tượng cout
-
Đối tượng
cout
cũng là một đối tượng được định nghĩa trong thư việniostream
thuộc namespacestd
, dùng để hiển thị một thông tin nào đó lên thiết bị xuất chuẩn (mặc định là màn hình). -
Toán tử
<<
(thuật ngữ chuyên ngành gọi là insertion operator) được dùng chung vớicout
, cho biết hướng đi của dữ liệu từ giá trị bên phải toán tử này đến màn hình console. -
Bạn cũng có thể sử dụng toán tử
<<
nhiều lần để in nhiều thông tin trên cùng một dòng. Ví dụ:cout << a << " " << b << "\n";
-
Kết quả sẽ in ra màn hình là
123 tmsangdev
và 1 dấu xuống dòng (newline)123 tmsangdev
4. endl
và "\n"
-
Có thể sẽ có bạn thắc mắc tại sao mình ở đoạn code trên, mình không dùng
endl
để xuống dòng, mà lại dùng"\n"
. -
Thực tế là
"\n"
chạy nhanh hơn so vớiendl
trong đa số các trường hợp.
Vậy khi nào nên sử dụng endl
? Khi nào nên sử dụng "\n"
?
5. Fast I/O
-
Một mẹo thần thánh nữa mình cũng thấy mọi người thường sử dụng, được gọi là Fast I/O, với 2 dòng lệnh kinh điển sau:
ios_base::sync_with_stdio(false); cin.tie(nullptr);
-
Tuy nhiên, mình có hỏi thử các bạn học sinh lớp 12 trong CLB lập trình từng tham gia thi HSG những năm gần đây, thì các bạn trả lời chỉ "nghe nói" hoặc "thấy mọi người bảo là" dùng cái này sẽ tăng tốc độ cho chương trình, mà chưa thực sự hiểu bản chất của nó là như thế nào.
-
Một khi đã không hiểu, thì có thể bạn sẽ gặp phải trường hợp làm chương trình trở nên chậm hơn khi sử dụng thứ gọi là Fast I/O này đó.
-
Trước tiên chúng ta cần hiểu ý nghĩa của 2 dòng lệnh này trước đã.
5.1. ios_base::sync_with_stdio(false);
-
Nếu nhìn vào tên hàm, bạn có thể hiểu nôm na tác dụng của nó là để đồng bộ (sync) với standard input output (
stdio
) -
Hàm này truyền vào giá trị
false
, tức là muốn ngắt bỏ sự đồng bộ này đi ❌️
Vậy tại sao ngắt bỏ sự đồng bộ với stdio
lại có thể tăng tốc độ của chương trình?
-
Lý do là vì trong C++ có 2 hình thức để nhập/xuất từ stream, đó là:
- Sử dụng
scanf
vàprintf
của thư việncstdio
- Hoặc sử dụng
cin
vàcout
của thư việniostream
- Sử dụng
-
Theo mặc định, thứ tự nhập/xuất của
cin
vàscanf
,cout
vàprintf
sẽ được đồng bộ (sync) để đề phòng trường hợp, nếu trong code của bạn có sử dụng cả 2 hình thức này. Ví dụ:cout << "Hello"; printf("Goodbye");
thì thứ tự thực hiện sẽ được đồng bộ đúng như vậy, chứ không bị lộn xộn hết cả lên.
Ơ thế thì tại sao trong lập trình thi đấu, mọi người lại truyền vào hàm sync_with_stdio()
giá trị false
nhỉ???
-
Đó là vì thông thường trong lập trình thi đấu, mọi người sẽ chỉ sử dụng hoặc là cặp
cin
-cout
, hoặc là cặpscanf
-printf
, chứ không dùng lẫn cả 2 loại. -
Nên việc đồng bộ cho 2 luồng này rõ ràng là không cần thiết.
-
Do đó, khi chúng ta tắt đồng bộ đi, đồng nghĩa với việc tốc độ thực thi sẽ nhanh hơn, khi không phải mất thời gian đồng bộ ở trên nữa.
-
Ngoài ra, trên Viblo còn có 1 bài viết rất chi tiết của tác giả @bobamilktea, phân tích về hiểu lầm phổ biến của nhiều anh em chơi CP về Fast I/O, các bạn có thể đọc thêm tại đây nha.
5.2. cin.tie(nullptr)
-
À thế còn dòng lệnh
cin.tie(nullptr)
, cũng là 1 phần của Fast I/O thần thánh mà mọi người hay sử dụng. Vậy ý nghĩa của nó là gì? -
"tie" dịch sang tiếng Việt có nghĩa là thắt, buộc, các bạn có thể liên tưởng đến hình ảnh quen thuộc đó là thắt cà vạt.
-
Còn ở đây,
cin.tie()
được dùng để đồng bộ hay nói dân dã hơn là "buộc" thứ tự nhập/xuất củacin
vàcout
lại với nhau. -
Thao tác "buộc" này sẽ giúp đảm bảo rằng 1 stream (ví dụ
cin
) phải được hoàn thành và xóa xong (flushed), thì một stream khác (ví dụcout
) mới có thể thực hiện được. -
Nếu không có việc buộc (hay đồng bộ) này, thì thứ tự input/output của bạn nhiều khả năng sẽ bị xáo trộn tùm lum.
-
Mặc định,
cin
vàcout
sẽ được đồng bộ với nhau để đảm bảo cho những ứng dụng tương tác với người dùng sẽ đi theo một trình tự hợp lý. -
Ví dụ:
cout << "Nhập tên của bạn: "; cin >> name;
- Khi
cin
vàcout
được đồng bộ, thì bạn có thể yên tâm là chỉ khi nào dòng chữ "Nhập tên của bạn: " được in hết lên màn hình console rồi, thì màn hình mới hiện ra con trỏ nhấp nháy để cho phép người dùng nhập tên và lưu vào biếnname
.
- Khi
-
Thử tưởng tượng, nếu
cin
vàcout
bị ngắt đồng bộ ở đây, thì có thể dòng chữ "Nhập tên của bạn: " chưa được in ra, thì màn hình đã yêu cầu người dùng nhập dữ liệu rồi. Lúc ý khi không có câu hướng dẫn kia, thì người dùng biết phải nhập gì bây giờ đúng không nào? -
Ấy thế nhưng khi đi thi lập trình thi đấu, đặc biệt phải kể đến những kỳ thi HSG ở Việt Nam, đề bài sẽ thường yêu cầu chúng ta lặp đi lặp lại việc đọc ghi qua file với số lượng bộ test lớn, thì việc bật đồng bộ giữa
cin
vàcout
này có thể khiến tốc độ thực thi bị chậm đi. -
Ngoài ra, vì bạn đọc ghi qua 2 file khác nhau, 1 file input, 1 file output riêng, chứ không có sự tương tác với người dùng như ví dụ ở trên, nên việc đồng bộ giữa
cin
vàcout
cũng là không cần thiết. -
Do đó, ngắt đồng bộ bằng câu lệnh
cin.tie(nullptr)
cũng không khiến cho chương trình hoạt động sai được, mà lại cải thiện tốc độ chạy của chương trình.
6. getline()
-
Một lưu ý khác khi tham gia lập trình thi đấu, đó là đôi khi chương trình phải đọc cả 1 chuỗi dài, chứa các khoảng trắng.
-
Ví dụ:
"Tờ Mờ Sáng học Lập trình"
-
Khi đó thay vì dùng
cin
, chúng ta sẽ dùng hàmgetline()
như đoạn code ví dụ dưới đây.string s; getline(cin, s);
7. Nhập rất nhiều bộ test, mỗi bộ test trên 1 dòng. Và bộ test sẽ kết thúc bởi 1 dòng chứa số 0
-
Đây chắc hẳn cũng là trường hợp đặc biệt khác mà nhiều bạn có thể đã từng gặp trong các đề thi.
-
Vòng lặp
while
đơn giản dưới đây sẽ giúp bạn nhanh chóng giải quyết được việc này:while (cin >> x) { if (x == 0) break; ... }
8. Đọc ghi file với freopen()
-
Phần cuối cùng mình muốn chia sẻ với các bạn trong video này, đó là việc đọc ghi file.
-
Trong một số kỳ thi lập trình (đặc biệt là ở Việt Nam), và xa hơn là trong công việc lập trình sau này, có những lúc dữ liệu nhập vào rất nhiều và lớn, việc nhập bằng tay là không khả thi.
-
Khi đó, dữ liệu thường sẽ được sinh ra sẵn và đặt trong một file text nào đó.
-
Nhiệm vụ của người làm bài là nhận dữ liệu từ file text đó, xây dựng thuật toán, sau đó xuất kết quả ra một file text tương đương.
-
Và C++ cung cấp cú pháp rất đơn giản, đó là sử dụng hàm
freopen()
trong thư việncstdio
(viết tắt của C standard input output)freopen(filename, access_mode, stream);
-
Hàm này lần lượt nhận 3 tham số đầu vào là:
-
filename
: Tên của file. Đây có thể là file dữ liệu đầu vào, hoặc file kết quả đầu ra. Trong lập trình thi đấu, đề bài thường yêu cầu các file có định dạng như .INP (viết tắt của INPUT), .OUT (viết tắt của OUTPUT), hoặc .DAT (viết tắt của DATA) -
access_mode
: Chế độ truy cập file, cho biết rằng bạn muốn truy cập file này để làm gì. Có 6 chế độ truy cập với file văn bản, bao gồm:Chế độ Mô tả r
Viết tắt của read. Mở file để đọc dữ liệu. Với điều kiện file đó bắt buộc phải có tồn tại. w
"Viết tắt của write. Tạo 1 file rỗng để ghi dữ liệu ra. Nếu như tồn tại 1 file cùng tên, thì nội dung file đó sẽ bị xóa và bị ghi đè bởi dữ liệu mới." a
"Viết tắt của append. Mở file để ghi dữ liệu vào cuối file. Nếu file đã tồn tại và có dữ liệu, thì dữ liệu đó sẽ vẫn nguyên vẹn, và dữ liệu mới sẽ được ghi tiếp vào cuối file. Nếu file chưa tồn tại, thì nó sẽ tự tạo file mới để ghi vào." r+
"Viết tắt của read/update. Mở file ra vừa để đọc dữ liệu, vừa để update dữ liệu. Với điều kiện là file này phải có tồn tại." w+
"Viết tắt của write/update. Tạo 1 file rỗng và mở nó ra để update dữ liệu. Nếu như tồn tại 1 file cùng tên, thì nội dung file đó sẽ bị xóa và bị ghi đè bởi dữ liệu mới." a+
Viết tắt của append/update. Mở 1 file để update dữ liệu vào cuối file. Mặc dù có nhiều chế độ như vậy, nhưng theo mình quan sát, thông thường trong lập trình thi đấu, chúng ta sẽ chỉ sử dụng 2 chế độ là "
r
" và "w
", tức là read và write. nhập dữ liệu input từ một file, và xuất dữ liệu output ra một file khác. -
stream
: Ở các đề thi lập trình thi đấu, chúng ta thường sử dụng một trong hai luồng làstdin
(standard in), hoặcstdout
(standard out). Tương ứng với luồng đọc dữ liệu vào và luồng xuất dữ liệu ra.
-
-
Dưới đây là một bí dụ minh họa trong kỳ thi HSG Tin, liên quan đến số Amstrong. Với yêu cầu nhập dữ liệu từ file
AMSTRONG.INP
và ghi kết quả ra fileAMSTRONG.OUT
-
Với kiến thức đã học ở trên, lúc này để đọc ghi file, chúng ta đơn giản chỉ cần thêm hai hàm
freopen()
ở đầu hàmmain()
là được:#include <bits/stdc++.h> using namespace std; int main() { freopen("AMSTRONG.INP", "r", stdin); freopen("AMSTRONG.OUT", "w", stdout); int number; cin >> number; ... return 0; }
KẾT LUẬN
-
Vậy là mình vừa chia sẻ với các bạn toàn bộ nội dung của bài viết: Phân tích 8 mẹo kỹ thuật thường sử dụng trong Lập trình thi đấu.
-
Mặc dù bài hơi dài, nhưng mình tin chắc rằng khi hiểu bản chất của những kỹ thuật này, các bạn sẽ thấy lập trình thi đấu thú vị hơn nhiều, chứ không chỉ đơn thuần là học mẹo để đi thi nữa.