# data[].attributes.headline
Khai báo mảng trong main không quá 10^5. Khai báo mảng ngoài main không quá 10^8

# data[].attributes.subject
Khai báo mảng trong main không quá 10^5. Khai báo mảng ngoài main không quá 10^8

# data[].attributes.body
Bài đọc và ghi nhiều bộ số luôn phải có tăng tốc chương trình

ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

# data[].attributes.headline
Sàng nguyên tổ chỉ sàng với kiểm tra snt đến 10^7

# data[].attributes.subject
Sàng nguyên tổ chỉ sàng với kiểm tra snt đến 10^7

# data[].attributes.body
Code tham kháo sàng đến 10^7

#include <bits/stdc++.h>

const int Mx=1e7;

using namespace std;

bool SNT[Mx+5];

void sang()

{

SNT[0]=SNT[1]=1;

for(int i=2; i<=sqrt(Mx); i++)

if(!SNT[i])

for(int j=i*i; j<=Mx; j+=i)

SNT[j]=1;

}

# data[].attributes.headline
Sàng đếm ước dùng khi phải đếm số lượng ước của nhiều số

# data[].attributes.subject
Sàng đếm ước dùng khi phải đếm số lượng ước của nhiều số

# data[].attributes.body
Code tham khảo

vector<int> sieveCountDivisors(int n)

{

vector<int> divisorCount(n + 1, 0); // Mảng đếm ước, khởi tạo tất cả bằng 0

// Tìm ước cho từng số

for (int i = 1; i <= n; ++i)

for (int j = i; j <= n; j += i)

divisorCount[j]++; // Tăng số lượng ước của j

return divisorCount;

}

# data[].attributes.headline
Chương trình sàng tổng ước dùng khi cần tính tổng ước của nhiều số 

# data[].attributes.subject
Chương trình sàng tổng ước dùng khi cần tính tổng ước của nhiều số 

# data[].attributes.body
void sanguoc()

{

fill(p+1,p+1000007+1,1);

p[0]=0;

for(int i=2;i*i<=1e6;i++)

for(int j=i*i;j<=1e6;j+=i)

{

p[j]+=i;

if(i*i!=j) p[j]+=j/i;

}

}

# data[].attributes.headline
Lúy thừa nhanh, tính với trường hợp phải tính lũy thừa của số  có số mũ lớn. Chú ý luôn phải % cho 1 giá trị nào đó nếu không sẽ tràn số

# data[].attributes.subject
Lúy thừa nhanh, tính với trường hợp phải tính lũy thừa của số  có số mũ lớn. Chú ý luôn phải % cho 1 giá trị nào đó nếu không sẽ tràn số

# data[].attributes.body
Code tham khảo

// Hàm lũy thừa nhanh: tính (a^b) % m

long long luythua(long long a, long long b, long long m) {

long long result = 1; // Kết quả ban đầu

a = a % m; // Giảm a về modulo m để tránh số lớn

while (b > 0) {

// Nếu b lẻ, nhân kết quả với a

if (b % 2 == 1) {

result = (result * a) % m;

}

// Tăng b lên 1 bậc và bình phương a

a = (a * a) % m;

b /= 2;

}

return result;

}

# data[].attributes.headline
2 con trò là bài dùng khá hay với việc xét đoạn thỏa mãn 1 điều kiện gì đó. Như bài Dãy con hôm trước thầy chữa.

# data[].attributes.subject
2 con trò là bài dùng khá hay với việc xét đoạn thỏa mãn 1 điều kiện gì đó. Như bài Dãy con hôm trước thầy chữa.

# data[].attributes.body
Code tham khảo:

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

long long M;

cin >> n >> M;

vector<int> A(n);

for (int i = 0; i < n; i++) {

cin >> A[i];

}

long long current_sum = 0;

long long count = 0;

int start = 0;

for (int end = 0; end < n; end++) {

current_sum += A[end];

while (current_sum > M && start <= end) {

current_sum -= A[start];

start++;

}

count += (end - start + 1);

}

cout << count << endl;

return 0;

}

# data[].attributes.body
Không sợ địch giỏi, chỉ sợ ta run

# data[].attributes.headline
Dãy con tăng không liên tục dài nhất. Một ví dụ vận dung QHD cơ bản.

# data[].attributes.subject
Dãy con tăng không liên tục dài nhất. Một ví dụ vận dung QHD cơ bản.

# data[].attributes.body
#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n,kq;

ll a[1000007],l[1000007],w[1000007];

int main()

{

ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

cin>>n;

for(int i=0; i<n; i++)

{

cin>>a[i]>>w[i];

l[i]=w[i];

}

for(int i=1; i<n; i++)

for(int j=0; j<i; j++)

if(a[i]>a[j])

l[i]=max(l[i],l[j]+w[i]);

kq=0;

for(int i=0; i<n; i++)

kq=max(kq,l[i]);

cout<<kq;

}

# data[].attributes.headline
tốc độ thực tế của prinft và cout trong thực tế môi trường IDE của c++

# data[].attributes.subject
tốc độ thực tế của prinft và cout trong thực tế môi trường IDE của c++

# data[].attributes.body
code sinh hoán vị cho thấy rằng tốc độ thực tế đáng bất ngờ của prinft và cout, code giám sát thời gian cho thấy, khi sinh hoán vị của 1 mảng có 8 phần tử khác nhau (chạy bằng đệ quy rút gọn - next_permutation) cho thấy rằng khả năng in ra của cout có tăng tốc nhanh hơn hẳn so với prinft thường!

# data[].attributes.body
code chạy sàng ước sẽ nhanh hơn khi không duyệt qua mảng +1 ban đầu và chỉ +1 khi có phần tử cần gọi

# data[].attributes.headline
Nguyên nhân tại sao "\n" lại nhanh hơn "endl" mặc dù cùng là xuống dòng (chắc ai cũng biết nhưng cứ để đây cho đẹp lmao)

# data[].attributes.subject
Nguyên nhân tại sao "\n" lại nhanh hơn "endl" mặc dù cùng là xuống dòng (chắc ai cũng biết nhưng cứ để đây cho đẹp lmao)

# data[].attributes.body
Trong lập trình thi đấu, sử dụng endl thực sự khiến chương trình của chúng ta chạy chậm đi.

Lí do là vì cout << endl tương đương với cout << "\n" << flush. Flush được dùng để đưa một output đang chứa trong bộ đệm ra ngay lập tức để đồng bộ với chương trình đang chạy. Tuy nhiên trong lập trình thi đấu thì việc chạy đồng bộ không cần thiết vì chúng ta sử dụng đọc xuất file. Việc sử dụng endl chỉ hữu dụng khi làm những bài có tag interactive chẳng hạn trên nền tảng codeforces.

Nếu bạn đã quen tay với việc sử dụng endl rồi, hãy sử dụng #define endl "\n" ở trên đầu đoạn code.

# data[].attributes.headline
Bản C++ trong trình chấm thi Themis là C++14

# data[].attributes.subject
Bản C++ trong trình chấm thi Themis là C++14

# data[].attributes.body
Năm ngoái, thầy Cao có bảo là sử dụng isdigit, to_string, stoi, và những hàm tiện ích xử lý xâu kí tự khi vào máy chấm sẽ bị lỗi. Nhưng đó là năm ngoái, còn năm nay đã được tính là legit khi trình chấm Themis đã chuyển từ C++11 -> C++14 (một phiên bản chấm có thể nói là nhanh gấp bội và rất nhiều tiện ích so với bản cũ). Cho nên anh em cứ thoải mái dùng các hàm tiện ích nhé! (lưu ý là hàm lcm(a.b) - tìm bội chung nhỏ nhất không có trong C++14 mà phải tự anh em define nó)

# data[].attributes.headline
code sàng tổng ước và sàng số các ước có 1 lưu ý nhỏ khi dùng

# data[].attributes.subject
code sàng tổng ước và sàng số các ước có 1 lưu ý nhỏ khi dùng

# data[].attributes.body
bởi vì sàng ước tổng hợp của thầy là sàng nhanh, nên thầy chạy từ i^2 của số ấy, vậy nên khi tính tổng ước, thì hãy cộng bù cả chính số đấy vào, đối với cải tiến không fill, cộng thêm cả 1 vào nữa, vậy nên khi truy suất ra từ sàng tổng ước,hãy cộng thêm số đấy và 1. đối với sàng số các ước, vì số ấy thiếu 2 ước là chình nó và 1, vậy nên, với code không fill, chỉ cần +2 vào là xong

# data[].attributes.body
void sanguoc()

{

p[0]=0;

for(int i=2; i*i<=1e6; i++)

for(int j=i*i; j<=1e6; j+=i)

{

p[j]++;

if(i*i!=j) p[j]++;

}

}

dựa trên ý tưởng của thầy, code này hoạt động y như vậy nhưng là +1 khi quyét qua ước, lưu ý, khi truy suất nó ra, hãy cộng thêm 2 bù cho ước là 1 và chính nó

# data[].attributes.attachment_caption
Tốc độ thực sự giữa printf và setprecision

# data[].attributes.headline
Khi có bài toán in ra số có phần thập phân thì hãy dùng printf thay cho setprecision

# data[].attributes.subject
Khi có bài toán in ra số có phần thập phân thì hãy dùng printf thay cho setprecision

# data[].attributes.body
Nếu nói F1 là cuộc đua tốc độ của chiếc xe thì LCOI cũng được ví như giải F1 của thuật toán. Đơn giản mà nói thì chỉ cần chệch 1 mili giây cũng làm thay đổi cả thế trận ngay cả khi in ra kết quả cũng đủ ảnh hưởng dẫn đến quá thời gian. Như Hoàng và Đạt cho ta thấy được thời gian thực sư giữa cout và printf in ra số nguyên thì cout đã chiếm ưu thế hơn so với printf nhưng khi in ra số có phần thập phân thì lại là một câu chuyện ngược lại khi printf lại nhanh hơn cả cout << fixed << setprecision. Nguyên nhân như sau:

printf nhanh hơn vì nó là một hàm cấp thấp, không sử dụng các lớp trừu tượng và chỉ thực hiện định dạng trực tiếp và in ra.

setprecision trong cout có thêm các thao tác quản lý trạng thái luồng, thay đổi các thuộc tính định dạng, và điều này làm tăng overhead, dẫn đến hiệu suất chậm hơn một chút so với printf.

# data[].attributes.body
thường thì đối với xu hướng làm bài, đa số anh đều thấy và suy đoán từ kinh nghiệm của mình về cách để phân biệt hướng làm chuẩn bằng cách dựa vào phạm vi và độ lớn của số mà bài cho như sau:

dưới 10^3: thường sẽ là chạy trâu đến siêu trâu, và cách chạy thường khó và cần dùng nhiều não, đề bài hay lừa

trong khoảng 10^3 đến 10^6: thường thì đây là phạm vi ta chạy thuật toán thông dụng và nâng cao tốt nhất (như sàng, đếm ước, phân tách số,... đến các thuật toán tự phát)

từ 10^6 đến 10^9: là phạm vi hết cỡ của các thuật toán thi đấu, nên vùng này sẽ ưu tiên các thuật toán tối ưu, có thể thông thường như tìm số nguyên tố 6k+-1 cho đến những thuật toán nâng cao như chặt nhị phân, hàng đợi, chuyển đổi xâu,...

từ 10^9 đến 10^12(có thể lên đến 10^18): đây là thường là vùng số học, logic, nơi ta phải vận dụng não để tìm ra cách tối ưu và đưa thuật toán trở về phạm vi hoạt động bé hơn hoặc đưa về dạng công thức gì gì đó. Ví dụ điển hình của vùng này chính là bài toán số 3 ước, khi mà ta phải luận từ số nguyên tố đến việc vận dụng căn bậc 2 để rút ngắn phạm vi hoạt động

từ 10^12 đổ lên: hoạt động tốt nhất ở đây thì chỉ có tối ưu (ít), công thức (ít nhưng xác suất cao hơn) và duyệt xâu string.

trên đây là tips bài do anh tự kiểm nghiệm và rút ra từ kinh nghiệm làm bài của anh, tất nhiên mấy đứa vẫn cần đọc kỹ và đưa ra hướng làm riêng phòng ngoại lệ, nhưng đa số bài anh đã làm đều hoạt động như thế cả.

# data[].attributes.body
mấy đứa cố lên nhé, nhớ đọc phần lưu ý kinh nghiệm làm bài mà anh đã để ở đây 1 năm trước, nó rất hữu dụng đấy