Protected: Sol_Vuong_19_Dec
Experience Nov
ptree
*) do phuc tap la O(N^2)
C/m: https://codeforces.com/problemset/problem/815/C
Dpt la O( numChild[i] * numChild[j] ) -> O(N ^ 2)
*) trace
dùng trace ngược up[v][x] nghĩa là dp[ dad[v] ][ x ] dùng bao thằng ở con v
another problem: kingdom spoj
winrar algo :v
link đề, có m siêu cạnh a, b, t nghĩa là nối a -> b, a + 1 -> b + 1, a + 2 -> b + 2, …
hỏi có bao thành phần liên thông.
Sol:
O(m căn m):
gọi căn n = x,
tách mỗi siêu cạnh ra thành (a, b, x), (a + x, b + x, x), …
khi đó ta có m căn n cạnh, dùng kruskal đưa về tối đa n cạnh.
sau đó bung đám này ra có n căn n cạnh lại dùng kruskal tiếp.
O(n log)
với mỗi (a, b, t), gọi x = log2(t)
đưa (a, b, t) về (a, b, 2 ^ x) và (a + t – 2 ^ x, b + t – 2 ^ x, 2 ^ x)
xét từ tầng log cao nhất về cuối, trên mỗi tầng ta kruskal để đưa về n cạnh, sau đó, với mỗi (a, b, 2 ^ x) di truyền cho tầng dưới (a, b, 2 ^ (x – 1)) và ( a + 2 ^ (x – 1), b + 2 ^ ( x – 1), 2 ^ (x – 1)).
Bản chất:
dùng tính chất của kruskal, ko quan trọng số lượng input, output luôn <= n.
chia căn
dấu hiệu:
Q: bài nào làm đc chia căn ?
A: những bài có đọ phức tạp phụ thuộc, varied.
ví dụ: https://vn.spoj.com/problems/VMBW/
nếu làm trâu thì nó thành đpt O ( Q * deg(u) ) trong đó u là đỉnh được hỏi.
ví dụ: cho đồ thị vô hướng G = (V, E), đếm số tam giác.
thì nếu làm trâu nó cũng là O(N*deg(u)*deg(v))
Lợi thế:
Tự hỏi 1 đồ thị vô hướng bình thường thì có tính chất gì?
Ngoài cây cầu ra thì :v nah
chia căn sẽ giúp ta phân tập đỉnh ra làm 2 tập, nhỏ và to:
*) tập nhỏ: số đỉnh kề <= căn(n) —-> có thể for trâu được
*) tập to : số đỉnh to tối đa là căn(n)
từ đó cho ta biến một đồ thị bình thường G = (V, E) thành một đồ thị khá bựa.
Bên cạnh đó, ta còn có thể xây được mảng cạnh 2 chiều mà ko cần dùng đến vector, cụ thể:
Với tập cạnh (to – to): xây mảng N ^ 2
Với tập cạnh (to – nhỏ): xây mảng N căn ( N )
Với tập cạnh (nhỏ – nhỏ): for trâu.
lzs:
lcs2x thì quen thuộc với các bạn trẻ rồi, nhưng h, nếu hỏi là, số lượng dãy thỏa mãn độ dài dài nhất thì làm thế nào ?
dãy ở đây là xét về giá trị hén :v
và để cho đơn giản thì ta chỉ xét giá trị sau > giá trị trước trong dãy LCS.
Tư tưởng:
Với cách (N ^ 3), ta có thể for i = 1 -> n, for j = 1 -> m, for k = i – 1 -> 1, và chỉ cập nhật khi a[k] xuất hiện lần đầu trong khoảng từ (k, i]
Lời giải:
Gọi F[i][j] = độ dài dài nhất xét dãy a[1..i] và b[1..j], và kết thúc tại b[j], còn kết thúc ở a thì ko biết.
Gọi Num[i][j] = số lượng dãy unique xét dãy a[1..i] và b[1..j], và kết thúc tại b[j], còn kết thúc ở b thì ko biết.
Nó phức tạp vcc. nên gắng đọc hiểu ha.
Gọi 2 dãy là a[1..n] và b[1..m]
Mình sẽ for i = 1 -> n.
Thêm 1 cái pair best, best.first lưu để dùng cho F, best.second lưu cho Num.
Do ta đang chốt vị trí i của dãy a, nên giả sử b[j] = a[i], thì rõ ràng F[i][j] sẽ luôn lấy cặp (a[i], b[j]), nên Num[i][j] lúc ấy cũng reset về 0 luôn, vì các lần xét ở trước vô nghĩa tại thời điểm này.
Còn giả sử a[i] > b[j], thì b[j] có thể là phần tử đứng trước của b[ j1 ] (j1 > j) mà a[i] = b[j1], nên cập nhật cho best hiện tại với F[i – 1][j]. Nên là tí nữa nếu đến j1, thì cập nhật F[i][j] với best sẽ hợp lí.
Vấn đề còn lại là dãy phải unique. Với tư tưởng ở trên, có thể thấy, nếu b[j] = b[k] (j < k) thì ta sẽ bị trùng, cách xử lý khá đơn giản, lưu lại vị trí của giá trị đó, nếu gặp lại thì mình trừ đi gía trị cũ chơi giá trị mới.
Code mẫu cho một bài tương tự, đọc hiểu concept thôi:
https://pastebin.com/PKtS86p2
Experience_Sep
Remainder
Roads
Gauss
*) big size
Dp string
Greedy
Protected: Solution_D3_Sep2018
Vietnamese Naive Explaination For KMP and Aho-Corasick
KMP:
Một số quy ước:
S(i, j) nghĩa là 1 substring của xâu S, bắt đầu tại i kết thúc tại j
S[i .. j] cũng tương tự S(i, j)
S[i] là kí tự i của xâu S
KMP là cái gì ?
Ta có 1 string S (1-indexed)
ta cần tạo ra mảng kmp[i] = j, trong đó:
- j max (j < i)
- S[1 .. j] = S[i + 1 – j .. i]
Ví dụ với KMP
Có được mảng này thì ta được cái gì ?
Ta có thể kiểm soát việc matching hiện tại
Không chỉ đơn thuần là 1 bài string-matching( SUBSTR spoj ) bằng hash hoặc Z hoặc Trie
KMP cho ta những khả năng kì diệu hơn trong độ phức tạp nhỏ, code dễ và tính chính xác cao :v
Lấy ví dụ, em cần làm 1 bài quy hoạch động, trong đó cần kiểm soát 1 đoạn xâu X đã xuất hiện hay chưa ?
KMP đã ở đây để giúp em
Với việc thêm 1 max prefix hiện tại, ta dễ dàng kiểm soát được tại thời điểm bất kì, thì xâu đã từng xuất hiện chưa.
Xây KMP
Ok, thế bây giờ ta xây KMP kiểu gì
Thử Binary Search
Ờ thì tìm j max, nên binary search có vẻ hợp lí
Đến khi em chợt nhận ra việc hàm này 0 có tuyến tính( nghĩa là ko monotone, là đơn điệu cho ai thắc mắc)
Lấy ví dụ:
abcabcabc
thì tại i = 6, j = 3 sẽ là 1 kết quả đúng, nhưng mà 1, 2, 4, 5 đều là các kết quả sai, nên là không chặt được
Bây giờ em bối rối, em không biết phải làm sao để tính KMP, anh cũng vậy, anh cũng không biết làm sao để giải thích KMP cho em 😦
Ta có mảng KMP[1..i – 1], ta cần tính KMP[i]
trong đó, KMP[x] là max prefix tường ứng suffix của S[1..x]
gọi các ứng cử viên cho KMP[i] của chúng ta là ucv1, ucv2, …, ucvk
thì ta cần tìm thằng to nhất trong đám ucv đúng hem ?
thế thì em phải tìm mối liên kết giữa cái đám ucv và đám KMP[1..i-1], anh cho em 5s suy nghĩ :v
có thể thấy là, S[ucv1] = S[ucv2] = S[ucvi] = … = S[uvck]
thế thì vứt cái đám bằng nhau đó ra, em còn lại gì ?
sẽ tồn tại 1 thằng ucv làm mồi cho S[x – 1] đúng không ?
( vì S[1..ucvx] = S[i + 1 – ucvx..i] ), nên (S[1 .. ucvx – 1] = S[i – ucvx .. i]))
thế thì khá rõ rồi,
giả sử S[ KMP[i – 1] + 1] = S[i] thì KMP[i] = KMP[i – 1] + 1 luôn
lại có 2 câu hỏi:
- lỡ nó không tối ưu nhất thì sao ?
- lỡ S[KMP[i – 1] + 1 ] != S[i] thì sao ?
Câu hỏi 1:
Giả sử tồn tại 1 ucvY mà ucvy > KMP[i – 1] + 1 (1)
như đã nói trước, ucvy mà bỏ đi kí tự cuối thì nó chính là 1 suffix của S[1..i-1]
nên (1) ucvy – 1 > KMP[ i – 1 ] ( vô lý thì KMP[ i – 1 ] phải lớn nhất )
Câu hỏi 2:
như đã c/m ở trên, ucvx – 1 luôn là 1 ứng cử viên thỏa mãn cho KMP[i – 1]
hiện tại, chính KMP[i – 1] đã bị loại nên chúng ta tiếp tục quan tâm đến KMP [ KMP[i – 1] ]
(vì các ứng cử viên cũng là 1 suffix của S[1 .. i – 1], ta tiếp tục quan tâm thằng to nhất như chỗ “có thể thấy là “)
và rõ ràng, chọn KMP[KMP[i – 1]] là ứng cử viên tốt nhất đến hiện tại
và thế là ta có 1 cách c/m đệ quy cho KMP, và pseudo-code như sau:
struct KnuthMorrisPath{
int kmp[M + 10];
void clear(){ memset(kmp, 0, sizeof kmp); }
KnuthMorrisPath(){ clear(); }
KnuthMorrisPath(string st){
clear();
st = " " + st;
KMP[0] = KMP[1] = 0;
for (int i = 2; i < (int)st.size(); i++){
int j = KMP[i - 1];
while (j > 0 && st[j + 1] != st[i]) j = KMP[j];
if (st[j + 1] == st[i]) j++;
KMP[i] = j;
}
}
} KMP;
link: templateCode_KMP_level1
Lưu ý là ta for từ 2 nhé, vì KMP[i] < i, nên KMP[1] PHẢI mặc định = 0 thì các KMP sau mới tính đúng được.
tiếp tục nói về ứng dụng của KMP
Loại 1:
Cái mà KMP cho chúng ta không phải chỉ đơn thuần là 1 cái mảng prefix suffix matching
Nó cho em một tư tưởng, một luồng suy nghĩ, một template, một cái để nhớ về mỗi khi em gặp dạng.
Nói đến thịt gà, anh nghĩ ngay đến lá chanh.
Nói đến thịt chó, anh biết đó là Exciter
Nói đến Bari, anh liên tưởng đến Clorua, blah blah
Thì khi nói đến quy hoạch động với xâu, ta phải nghĩ đến KMP
Và các em cũng chẳng cần lo lắng nhiều, vì cái này nó chỉ có đúng 1 dạng duy nhất.
Ví dụ với bài : XYZ_spoj
Hmm
// click để đọc tiếp đoạn sau, không spoil solution
/// begin solution
/// end solution
Ờ thì cái này điển hình rồi, nên sau này có thể gặp lại với bài D/E div2 CF, thường thế
Ví dụ luôn nè: https://codeforces.com/contest/346/problem/B
Loại 2
cái này là 1 trong những ứng dụng quan trọng của KMP
=> xây cây Aho-Corasick
///
nếu bạn nào vẫn chưa hiểu thì có thể tham khảo video này: youtube_explain
mình thấy cái video đó chất lượng phết .
///
Aho-Corasick:
Mệt rồi, rảnh viết tiếp 😐 …..
lad_training__Aug
Day 1
mototonic
bài này có 1 bản dễ hơn trên codeforces: alternative_mototonic
ờ thì cách giải trên CF khá là rõ ràng và dễ hiểu rồi, nên ở đây mình trình bày
2 cách giải khác:
solution by LAD98:
ta sẽ sử dụng dijkstra cho bài này
Gọi D[i][j] là minCost để đến được đỉnh i, dùng cạnh j, thì ta có thể cập nhật từ D[i][j] -> D[kề(i)][cạnh(i, j)] nếu weight[j] <= weight(cạnh(i, j))
do j chỉ là những cạnh kề với i nên ta có thể đảm bảo bộ nhớ = O(|E|)
cập nhật thì có 1 cách làm trâu, for mọi cạnh từ u, ra đỉnh v, kiểm tra cạnh
rõ ràng cách làm này sẽ bị TLE, ví dụ hình sau: ladSolution_day1_mototonic_picTle1
có thể thấy với mỗi eu[i] thì nó đều scan lại tập cạnh ev* và các eu[j](j != i)
nên độ phức tạp thuật toán trong worst case là 2C(deg[u]), TLE trong trường hợp đồ thị cánh bướm (deg của một đỉnh nào đấy lớn)
dù sao thì có thể cầu may với cách này :v
sau đây là cách cải tiến của lad, mà mình còn gọi là lazy_dijkstra (gọi cho sang chứ chẳng phải lazy đâu :v)
từ đỉnh D[u][id1], ta biết ngay id2 là cạnh kề với u, và có weight[id2] >= weight[id1] (id2 > id1), ta sẽ cập nhật cho
D[v][id2] với giá trị là: D[u][id1] + weight[id2] và
D[u][id2] với giá trị là: D[u][id1]
khi đó, lúc D[u][id2] bị lấy ra khỏi priority_queue, thì nó lại cập nhật cho thằng tiếp theo nó, và cứ thế, thì ta đã di truyền được gía trị D[u][idx] qua từng lần
code tham khảo:
solution by CKMD (trong trường hợp ta cần tìm đường đi qua ít đỉnh nhất, chính là bài CF)
gọi tập cạnh kề của đỉnh u sau khi sort theo tăng dần là e1, e2, e3, e4, .., ek
nhận thấy, giả sử thứ tự được lấy ra khỏi priority_queue lần lượt là ei1, ei2, ei3, …
thì rõ ràng ei1 sẽ luôn cập nhật cho các đỉnh D[vx][ex] ( ex >= ei1 )
sau đó nếu ei2 > ei1 thì ta bỏ qua, vì D[u][ei2] >= D[u][ei1] rồi nên ko cần cập nhật nữa
còn nếu ei2 < ei1 thì cập nhật cho các đỉnh trong [ei2, ei1]
rõ ràng độ phức tạp chỉ là O(M) ( vì ta chỉ cập nhật mỗi đỉnh kề đúng 1 lần)
code tham khảo: CFproblem_codebyCKMD
path:
giả sử ta đã xây được đồ thị theo yêu cầu đề bài, ta sẽ chứng minh G là 1 DAG
giả sử tồn tại một chu trình, các đỉnh lần lượt là u1, u2, u3, ..
theo đề bài:
u1*(u2 – 1) mod n = 0 → u1 * u2 ☰ u1 (mod n) (1)
tương tự thì u2 * u3 ☰ u2 (mod n) (2)
từ (1) và (2): u1 * u2 * u3 ☰ u2 * u1 (mod n)
u1 * u3 ☰ u1 (mod n)
cứ tiếp tục như thể thì u1 ☰ u1 * uk (mod n), mà uk * u1 ☰ uk (mod n)
tức là u1 ☰ uk (mod n) → vô lý, vì các số phân biệt
c/m được DAG thì nhiệm vụ tìm đường đi dài nhất chỉ còn là DP
lưu ý ở cách xây đồ thị, có thể làm trâu như sau:
for ( i : [1 .. n ] ),
tìm x = gcd(i, n),
y = n / x,
for ( j = y, j <= n; j += y)
nối cạnh (i, j – 1)
độ phức tạp của nó sẽ cao nếu tần số xuất hiện của các con y có giá trị nhỏ cao (VD, y = 2, và nó xuất hiện 50 lần, thì sẽ là 50 * n / 2)
nên làm theo cách ngược lại
for i : các ước của n ( tối đa căn(n))
x = n / i
for ( j = x; j <= n; j += x)
nối cạnh (i, j – 1)
cách for này đảm bảo là các x phân biệt trong mỗi lần for i
từ đó đảm bảo số cạnh không quá O(nlogn), cũng như xây cạnh không quá O(nlogn)
ferries(spoj)
Quy ước: có cung (u, v) thì gọi là v kề u
Gọi D[u] là độ dài đường đi nhỏ nhất trong các trường hợp xấu nhất từ đỉnh 1 -> u
kết quả là D[n]
Xét đỉnh u, có các đỉnh kề là v1, v2, …, vk với các cung tương ứng là e1, e2, …, ek
thì giả sử ta biết hết các D[vx], thì rõ ràng cách phân bố tối ưu là cho đỉnh có D[vx] to nhất ghép với cạnh ey nhỏ nhất, và cứ tiếp tục như thế.
khi đó ta có 1 thuật toán đệ quy có nhớ cho bài này.
Để khử đệ quy, ta dùng đồ thị đảo.
D[u] sẽ có ý nghĩa là, độ dài đường đi nhỏ nhất từ u -> n
Đẩy vào priority_queue thì lúc này, có 1 nhận xét là:
thứ tự các đỉnh được lấy ra cũng là thứ tự được sort
giả sử đỉnh u được lấy ra, thì với các đỉnh kề u là v, đỉnh u sẽ được ghép với cạnh thứ deg[v] – mark[v] – 1 trong tập cạnh của v ( trong đó mark[v] là số lượng đỉnh kề với v đã được đánh dấu ).
Để hiểu rõ hơn thì coi code hen.
code: ferries_byCKMD
Day 2
Đề: TVIwnFJ+gH1XLPO36mxkX/XCaju4XxF84956L7g=
Chủ đề là KMP và Aho-Corasick
Experience_August
Aho_corasick
welzl
cutseg
cutseq
alpha dsu
hld
Experience_July
Mo’s Algorithm
Float comparison
Tree:
Bridge tree
Special path
Range queries:
thường là các bài số, hoặc là có truy vấn dạng tìm một hàm F(x) mà L <= x <= R
hãy thử tìm G(x) mà x <= bound.
khi đó có thể F(x) = G(R) – G(L – 1)
bit2d compressed
các bài có dạng, có n điểm trên mặt phẳng 2D, sau đó tìm một hàm gì đấy ( thường là tổng, hoặc đếm số điểm, hoặc max hàm) của hình chữ nhật { (0, 0), (x, y) }
rõ ràng nếu làm BIT
Nhân ma trận ( không biết mình đã viết chưa )
Some tips for I/O in C++
I. FastInput
Sẽ có lúc bạn gặp bài toán, nhập vào đến khi nào dừng input thì thôi.
một câu hỏi đặt ra là, làm thế quái nào máy tính biết lúc nào thì user dừng input
nếu input được nhập từ file, thì câu trả lời là EOF ( end of file ), khá là obviously
nhưng EOF bản chất là cái gì ?
nó là 1 char, nghe có vẻ vô lý vì EOF tận 3 ký tự. dù sao thì, nó vẫn là 1 char
điều đó nghĩa là EOF có thể đọc vào như mọi ASCII khác.
và nó cũng đại diện cho việc có thể fast read = cách detect EOF khi đọc.
nếu input được nhập từ stdin:
mình biết là có 2 kiểu đọc cho loại này
1) while (cin >> x)
2) while (scanf("%d", &x) != EOF)
trong kiểu thứ 2 thì đã chỉ ra rằng, nếu input đã hết, thì scanf sẽ trả về EOF, còn x là cái gì thì nó kệ ( mình đoán thế :v )
nhưng đọc kiểu này sẽ không hiệu quả với các bài Input file > 1e6 characters, nên phải dùng fastRead. Hàm mà lâu nay mình vẫn dùng nó là thế này:
void fastI(int &x){
char c; bool flag = 0;
do { c = getchar(); } while (!isalnum(c) && c != '-');
if (c == '-') flag = 1, c = getchar();
x = c - '0';
while (isalnum(c = getchar())) x = x * 10 + c - '0';
if (flag) x = -x;
}
thế này thì lại không chơi được kiểu while, vì nó cứ đọc mãi, nên chúng ta có giải pháp như thế này:
bool fastI(int &x){
char c; bool flag = 0;
do { c = getchar(); } while (!isalnum(c) && c != '-' && c != EOF);
if (c == EOF) return 0;
if (c == '-') flag = 1, c = getchar();
x = c - '0';
while (isalnum(c = getchar())) x = x * 10 + c - '0';
if (flag) x = -x;
return 1;
}
Có một lưu ý nhỏ là, để thông báo cho máy biết EOF khi đang nhập vào từ bàn phím,
dùng Ctrl-D (Linux) hoặc Ctrl-Z (Window)
II. Đọc từ 1 File
Có 3 kiểu đọc file:
#define FILE "sample"
freopen(FILE".in", "r", stdin);
// file re-open
FILE * input2 = fopen(FILE".in", "r");
// file open
ifstream input3(FILE".in")
// input file stream
Có sự khác biệt ở cái đầu và 2 cái sau
ở cách 1, khi được chạy thì máy sẽ gán input stream (hiểu là luồng input cho đơn giản) thành đọc từ file, nên là sau đó, có thể dùng cin, scanf như bình thường
ở 2 cách còn lại, file input sẽ được đẩy vào input stream riêng, sau đó người dùng lại lấy ra từ input stream đó
ví dụ với cách 2 và cách 3:
int x; // đọc cho x
//--------
// lưu ý là fopen chỉ đọc được char *
char c = fgetc(input2);
x = atoi(c) // hàm chuyển char * -> integer
//--------
input3 >> x; // đọc giống cin
ờ thì, rõ ràng trong competitive programming ta sẽ thường sử dụng cách 1, đơn giản và hiệu quả
cách 2 thì mình không thấy dùng nhiều lắm, 1 phần vì nó là hàm của C, 2 là vì nó khá bất tiện dù hàm khá tốt. Bản thân mình thì lại hay dùng nó để check file có tồn tại hay không.
cách 3 thì dùng khi cần open nhiều file cùng 1 lúc. Lúc đó cách 1 sẽ dùng sẽ không tiện được, vì ta chỉ có 1 stdin mà cứ chuyển qua chuyển lại thì sẽ khá rối.
III. Đọc từ nhiều file cùng 1 lúc
Có 2 định nghĩa cho cái này:
1. Mở nhiều file cùng 1 lúc và xử lý
VD: có file student.txt và score.txt, mở cả 2 files này ra và đọc.
2. Mở nhiều file lần lượt và xử lý lần lượt
VD: có file input1.txt, input2.txt, input3.txt,… và file solve.cpp
rồi chạy file solve.cpp cho mọi file input.txt
Cả yêu cầu 1 và 2 thì có thể làm được với hàm assign bên Pascal.
Và cũng có thể làm được với cách open file ifstream( loại 3) bên C++, nhưng phải thêm 1 số tricks như sau:
*) Với yêu cầu 1 thì dễ rồi
*) Còn với yêu cầu 2 thì như thế này (giả sử ta cần đọc và xử lý lần lượt các file ifile1.in, ifile2.in) :
#include<bits/stdc++.h>
using namespace std;
string toStr(int x){
string result;
while (x > 0)
result = result + char(x % 10 + '0'), x /= 10;
return result;
}
main(){
string str = "ifile";
int num = 2;
for (int i = 1; i <= num; i++){
string inputString = str + toStr(i) + ".in";
ifstream input(inputString);
// ifstream input(inputString.c_str());
// both is fine
int foo;
input >> foo;
cout << foo << '\n';
}
}
// my option in compiler: -std=c++11 -O2 -Wall -Wextra
// for a full code of compiler in sublime, plz visit my git.hub
sử dụng code gần giống trên, chỉ cần thay getchar() thành input.get(), ta có fastInputFromFile:
bool fastI(int &x){
char c; bool flag = 0;
do { input.get(c); } while (!isalnum(c) && c != '-' && !input.eof());
if (c == '-') flag = 1, input.get(c);
x = 0;
while (isdigit(c) && !input.eof()) x = x * 10 + c - '0', input.get(c);
if (flag) x = -x;
return 1;
}
Code:fastIO_fromFile
IV. Linh tinh
Như mình đã nói ở mục 2, có 1 cách code check file khá là tiện.
Chắc hẳn các bạn khi nộp bài cho các trang chấm online, đôi lúc lại quên bỏ freopen ra, dẫn đến việc phải nạp lại bài, khá là khó chịu. Nên sau đây là giải pháp 2 dòng của mình:
if (fopen("sample.in", "r"))
freopen("sample.in", "r", stdin);
super tiện lợi :v
Và trong mục III, cũng có 1 cách dùng freopen như sau:
freopen("input1.in", "r", stdin);
// do smthing with input from "input1.in"
freopen("input2.in", "r", stdin);
// do smthing with input from "input2.in"
// can't go back to input1 unless you call freopen("input1.in", "r", stdin) again
Và như mình nói, nó bất tiện :v
V. Tốc độ chạy của các hàm
Nói ngắn gọn thì : ( a < b nghĩa là a chạy tốt hơn b )
ifstream ~ getchar < scanf < cin, cout ( khi đã dùng ios::sync_with_stdio(0) ) < cin, cout ( không có ios::sync_with_stdio(0) )
Tham khảo thêm tại đây.
Còn 1 lưu ý nho nhỏ cho các bạn là, có sự khác biệt đáng kể giữa endl( c++ only) và ‘\n'( c and c++), vì cách hoạt động 2 thằng này khác nhau.
Hiểu đơn giản: trong mọi bài bình thường ( trừ các bài interactive ), thì nên dùng ‘\n’, vì nó chạy nhanh hơn nhiều endl ( giảm được quá trình in ra đáng kể).
Hiểu sâu: do thằng endl nó còn kiêm luôn chức năng flush, nên nó sẽ làm sạch thằng buffer sau khi đẩy đám hiện tại ra out, nên nó rất chậm, còn ‘\n’ chỉ đơn giản là đẩy kí tự xuống dòng vào buffer.
Tham khảo thêm tại endl vs ‘\n’
Và cái quan trọng nhất, khi nào thì nên dùng fastInput, fastOutput:
Ta cần hiểu là, mọi thứ nên được tính toán dựa trên số lượng chữ cái và chữ số, không nên tính trên số lượng số cần đọc nghen.
Ví dụ cần đọc 1e5 số, mỗi số <= 1e9, thì tức là ta có thể phải đọc 9 * 10 ^ 5 chữ số.
Và sau đây là bảng thống kê: ( gọi NINPUT = số lượng chữ số chữ cái cần đọc vào, NOUTPUT cũng xét tương tự)
- NINPUT <= 1e6 thì có thể dùng cin, cout ( with ios::sync ) để đọc vào
- NINPUT > 1e6 và <= 2e6 thì có thể dùng scanf
- NINPUT > 2e6, chỉ có thể dùng fastINPUT ( ifstream hoặc getchar )
Just, I hate this world 