2025 Nội dung học lớp 8.1 Lộ trình học: • Ôn lại về phần NNLT C++ • Học thuật toán để giải các bài toán trên máy tính • Tìm kiếm nhị phân • Cộng dồn • Xâu kí tự • Adhoc • Hai con trỏ • Thiết kế thuật toán: • Đệ quy • Quay lui • Quy hoạch động

Khóa 4 - Buổi 6: Thuật toán tham lam https://wiki.vnoi.info/translate/topcoder/Greedy-is-Good Tham lam (greedy method): Trong quá trình thiết kế thuật toán, ta chọn giải pháp tốt nhất ở tình huống hiện tại mà ko cần quan tâm đến các bước sau đó. Bài toán Búp bê gỗ Có n con búp bê gỗ, con x có thể nhét vào bụng con y nếu kích thước x + k <= y. Có thể nhét nhiều nhất bao nhiêu con để tổng kích thước chứa các con búp bê bên ngoài là ít nhất có thể. Con to nhất -> ko thể nhét được bụng con nào cả Xét con to nhì, con này nếu ko nhét được vào con to nhất Khi gặp 1 con đầu tiên nhét được vào cả 2 con nhất và nhì -> ta sẽ nhét nó vào bụng con to nhất -> sort từ lớn -> nhỏ Xét từ trái qua phải: 8 2 8 4 2 1 1 3 5 9 i 1 2 3 4 5 6 7 8 a 9 8 5 4 3 2 1 1 i j i j x x 0 0 0 0 0 x 9 + 8 + 1 = 18 sum = a[1]; i = 1 for(j = 2 -> n) { if(a[j] + k <= a[i]) i++; else sum += a[j]; } Bài 2. Quãng đường đi bộ Nếu không có vụ tụ tập trên đường, Biết độ dài là L. -> ta sẽ tính được thời điểm đến đích của mỗi người Vậy cần xét yếu tố nào để biết người a vượt người b? a xuất phát sau và thời điểm về đích của a sớm hơn b -> a vượt b L = 10 1 10 => 101 20 9 =>110 Sắp xếp các a[i] (thời điểm xuất phát và thời điểm về đích) 6 10 5 8 2 10 9 1 1 3 1 2 1 1

i a t finish 1 5 8 85 2 2 10 102 3 9 1 19 4 1 3 31 5 1 2 31 6 1 1 11

Bài 3 Bộ sưu tập tiền 1 3 5 6 1 -> (1) 1 + 3 Cùng lắm là rút 6 đồng để được 2 loại tiền 1 và 5 Nhận xét: Vì ông GS không quan tâm tới mỗi loại bao nhiêu tiền mà chỉ quan tâm số loại khác nhau: Nếu 1 loại -> rút tờ nhỏ nhất -> cần sx các loại tiền tăng dần x = a[1] Để được 2 loại: a1 và a2 khi nào? a1 + a2 < a3 sum = 0; x = 0; for(i = 1-> n) if(sum + a[i] < a[i + 1]) x++, sum +=a[i]

Bài 4 Chụp ảnh Ta có nhận xét: Vì mỗi vận động viên rời hàng nhiều nhất 1 lần -> Xét 2 vận động viên u và v bất kì trong hàn, nếu thứ tự đúng của u là đứng trước v (u < v) thì số ảnh xuất hiện u đứng trước v sẽ có ít nhất là 3 tấm Giải thích: do u đứng trước v nên nếu không có thay đổi gì thì 5 tấm ảnh u đều đứng trước v nếu u thay đổi thì có thể có 1 tấm u đứng sau v nếu v thay đổi thì có thể có 1 tấm u đứng sau v -> có nhiều nhất 2 tấm ảnh u đứng sau v -> có ít nhất 3 tấm u đứng trước v Cần sắp xếp lại thứ tự của các căp (u, v): sao cho cứ u đứng trước v ít nhất 3 tấm ảnh thì trong trật tự đúng: u đứng trước v. Cách code: Ta sẽ tự viết 1 hàm sắp xếp ứng dụng nhận xét trên bool cmp(int u, int v) { int count = 0; for (int i = 0; i < 5; ++i) { if (pos[i][u] < pos[i][v]) { count++; } } return count >= 3; } Bài 5 Lịch sửa chữa ô tô Xét mọi cặp xe:

                i           j                   
                x           y                   
                y           x

Ta cần đưa ra được 1 thuật toán tham lam để quyết định sửa xe nào trước xe nào Ta có nhận xét: Xét 2 xe i và j Nếu sửa i trước j ta tốn: sửa xe i trước: số tiền bị phạt cho xe i: a[i] * b[i] sửa xe j: số tiền bị phạt cho xe j: a[j] * (b[i] + b[j]) Tổng số tiền bị phạt: x = a[i] * b[i] + a[j] * (b[i] + b[j]) Nếu sửa j trước i: Số tiền phạt cho xe j: a[j] b[j] Số tiền phạt cho xe i: ai y = a[j] * b[j] + a[i] * (b[i] + b[j]) vậy sửa xe i sẽ tốt hơn sửa xe j nếu: x < y a[i] * b[i] + a[j] * (b[i] + b[j]) < a[j] * b[j] + a[i] * (b[i] + b[j]). Rút gọn bất đẳng thức còn lại là: a[j] * b[i] < a[i] * b[j] () -> ta sẽ sửa xe i trước xe j nếu (*) Cách code: Tương tự bài 4 ta sẽ code 1 hàm sắp xếp bool cmp(int i, int j) { return a[j] * b[i] < a[i] * b[j]; } Ta gọi đó quy tắc lập lịch công việc tối ưu, quy tắc smith: Bài 6: Các dự án Ta chia dự án thành 2 loại: Loại 1: có lãi -> a[i] < b[i] Loại 2: bị lỗ -> a[i] > b[i] Loại 3: Hòa vốn (nên để làm ở giữa) -> ta luôn nên làm Loại 1 trước loại 2 do sau khi làm loại 1 xong, số vốn của ta sẽ tăng Xét loại 1: Ta nên làm dự án a[i] nhỏ trước Giải thích: Ta chỉ cần bỏ số vốn nhỏ hơn rồi sau đó số tiền sẽ tăng dần để bổ sung cho các dự án tiếp theo

Xét loại 2: Ta nên làm các dự án có b[i] lớn hơn trước để số vốn giảm đi chậm hơn

-> sắp xếp theo quy luật trên và lần lượt xét từng dự án ta sẽ tính được số vốn cần thiết ban đầu Bài 7: Vượt đèo Tương tự bài 6, ta chia con bò thành 2 loại: Loại 1: Lên nhanh xuống chậm -> a[i].tU < b[i].tU and a[j].t Loại 2: Lên chậm xuống nhanh -> a[i] >= b[i]

-> ta đẩy loại 1 lên trước do ta cần các con bò lên dốc thật nhanh để đến lượt con bò tiếp theo

Trong loại 1: Loại nào có a nhỏ hơn thì đi trước Trong loại 2: Loại nào có b lớn hơn thì đi trước Sử dụng 1 struct X{ int tU, tD, idx; } Bài 8: BÚP BÊ GỖ

Khóa 4 - Buổi 5 (17/3/2026): Luyện tập chung

Bài 4: Thu hoạch subtask n * s <= 5e7 Ở subtask này ta có thể sử dụng quy hoạch động giống dạng bài subsetsum để giải

Gọi dp[j] : số cách để tạo ra tổng j khi đó ta for lần lượt các a[i] và ta sẽ có công thức

dp[i] += dp[i - a[j]]

Code mẫu: dp[0]=1; for (i=0;i<n;i++) { for (j=s;j>=0;j--) { dp[j]=dp[j]%998244353; if (j-root[i]>=0) { dp[j]+=dp[j-root[i]]; dp[j]=dp[j]%998244353; } } } cout<<dp[s]%998244353;

Bài 5: Chạy đua

Ta sẽ sử dụng quy hoạch động để giải quyết bài tập này.

Gọi dp[i] : Khoảng cách lớn nhất mà Khánh có thể chạy từ 1 đến i sao cho khi ở i thì mệt mỏi bằng 0. -> đáp án của bài toán là dp[n]

Nhận xét: nếu hiện tại độ mệt mỏi đang bằng 0, ta có thể chọn • nghỉ ngơi không làm gì cả • chạy 1 quãng đường với độ dài x trong khoảng từ 1 -> m và sau đó nghỉ ngơi tương ứng => Từ đó ta tìm được công thức dp như sau: • dp[i] = max(dp[i], dp[i - 1]) (Ta lựa chọn nghỉ ngơi không làm gì từ i-1 -> i) • dp[i] = max (dp[i], dp[i - 2 * x] + độ dài quãng đường từ i - 2 * x -> i - x (sử dụng mảng cộng dồn để tính)) Code mẫu phần dp: for(int i = 0; i <= n; i++) { s[i] = max(s[i - 1], s[i]); for(int k = 1; k <= m; k++) { if(i - 2*k < 0) { break; } int x = p[i-k] - p[i - 2 * k]; s[i] = max(s[i], s[i - 2 * k] + x); } }

Khóa 4 - Buổi 4 + 5 (3/3/2026): Quay lui Quay lui (Backtrack): Quá trình vét cạn toàn bộ các khả năng sinh nghiệm của bài toán ban đầu. Thông thường bài toán quay lui được cài đặt bằng phương pháp đệ quy P(n) ta cần phải biết KQ của các bài toán P(n -1), P(n-2)...P(1), P(0) f(n) = f(n - 1) + f(n - 2), f(1) = 1, f(0) = 0 Dãy nhị phân: 0/1 là 1 dãy số chỉ gồm 2 loại số là 0 và 1. xâu nhị phân có độ dài n: Có bao nhiêu xâu nhị phân độ dài n? là 2^n

i 1 2 3 4 s 0/1 0/1 0/1 0/1 2 2 2 2 0 0 0
1
1

Code: Bài 2. Sinh dãy nhị phân nhưng cụm “01” chỉ được xuất hiện tối đa 1 lần i 00000 00010

00101

Bài Liệt kê hoán vị: Có n vị trí, mỗi vị trí thay vì chỉ nhận 2 giá trị là 0/1 thì có thể nhận các giá trị từ 1 -> n. Nhưng nếu một số đã được dùng trước đó thì KHÔNG được dùng lại (mỗi giá trị chỉ được dùng 1 lần) i 1 2 3 4 5 s 1 5 3 2 4 Để biết 1 giá trị đã dùng rồi/chưa dùng ta sử dụng pp đánh dâu: dd[i] = true/false nếu i chưa/ đã dùng rồi n = 4 (1, 2, 3, 4) s[1] = 1, (2, 3, 4) s[2] =2 (3, 4) s[3] = 3 (4) s[4] = 4 -> 1 2 3 4 Quay lại s3 theo cách đệ quy dd[3] = true (3, 4) s[3] = 4 (3) s[4] = 3 -> 1 2 4 3 Bài 6. Liệt kê phân tích n = 2 + (n - 2) n = 3 + (n - 3) n = 4 + (n - 4) n =11 n = 1 + 2 + 3 + 4 + 5 sum = 0;///tổng của các giá trị đã phân tích n thành tổng for(k = 1 -> n) if(sum + k <= n) { s[i] = k; sum += k; Attempt(i + 1); sum -= k; }

Bài 7: Kĩ thuật chia đôi phân tập Cần chia tập ban đầu thành 2 tập sao cho mỗi phần tử thuộc 1 tập Tồn tại 2 tổng: A, B mỗi phần tử có 2 khả năng: chia nó vào A hoặc là chia nó vào B Khi thực hiện chia hết đủ n phần tử vào hai tập thì ta xét chênh lệch giữa hai tập này: KHi xét đến phần tử thứ i: có 2 quyết định: hoặc thêm vào A: A = A + a[i], B giữ nguyên Thêm a[i] vào B: B = B + a[i], A giữ nguyên Bài 8 Siêu trộm Với mỗi đồ vật, ta có thể chọn lấy nó hoặc không lấy nó cho vào túi Khi lấy đồ vật i, value += v[i], weight += w[i] Nếu ta chọn cách áp dụng giống bài 1:

i 1 2 3 4 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1

v[1] + v[3] + v[4] Cách code: backtrack(i, value, weight) { if(weight > w) ///NEO return; //trọng lượng vượt quá cho phép if(i > n) ///ĐÃ chọn xong tối ưu giá trị value, return; //Có chọn đồ vật i cho vào balo Attempt(i + 1, value + v[i], weight + w[i]) Attempt(i + 1, value, weight); //không chọn } Điều hòa Cần 1 mảng temp[]: Để lưu nhiệt độ các phòng trong quá trình thay đổi từng cái điều hòa Đối với mỗi cái điều hòa, ta có 2 lựa chọn, một là sử dụng nó, hai là không dùng nó • Nếu dùng điều hòa i, tất cả nhiệt độ các phòng trong khoảng từ a[i] → b[i] tăng thêm p[i] đơn vị Ta sẽ bắt đầu với nhiệt độ phòng = 0. Với mỗi điều hòa được bật lên thì các căn phòng từ a[i] -> b[i] sẽ được điều chỉnh để tăng thêm 1 lượng == p[i] Cách code: Attempt(i, money) { if(i > M)///NEO { //kiểm tra nhiệt độ của tất cả con bò: • nếu có một con bò ko thỏa mãn thì bỏ cách này -> return, • nếu đây là một cách hợp lệ → chọn nếu nó là cách dùng ít money nhất, return } ///ĐỆ QUY có sử dụng điều hòa thứ i: for(int j = a[i]; j <= b[i]; j++) temp[j] += p[i] Attempt(i + 1, money + m[i]); //bật điều hòa i for(int j = a[i]; j <= b[i]; j++) temp[j] -= p[i] //nếu không lấy phải trả lại nhiệt độ như cũ //không bật điều hòa i Attempt(i + 1, money); }

Lát nền Nhận xét: 1 hình 2^n * 2^n luôn có thể chia thành 4 hình vuông 2^(n - 1) * 2^(n - 1) Ý tưởng: Ta biết 1 trong 4 hình vuông này sẽ chứa ô bị khuyết → Ta sẽ đặt 1 viên gạch thợ vào giữa 3 hình vuông không chứa ô bị khuyết đó để coi như mỗi hình vuông đều có 1 ô khuyết → Từ đó ta lại quay lui để đặt các viên gạch vào từng hình vuông trong 4 hình vuông này, mỗi hình vuông có 1 ô khuyết Ví dụ:

                x       

        x               
        x   x

Bảng chia làm 4 phần

Q1 | Q2

Q3 | Q4 Giả sử ô khuyết nằm trong Q1: . . . . | . . . . . . . . | . . . . . . X . | . . . . . . . . | . . . . --------+-------- . . . . | . . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . Ta sẽ đặt 1 viên gạch thợ vào giữa sao cho bài toán trở thành bài toán con với 4 hình vuông có 1 ô khuyết: . . . . | . . . . . . . . | . . . . . . X . | . . . . . . . . | T . . . --------+-------- . . . T | T . . . . . . . | . . . . . . . . | . . . . . . . . | . . . . → Từ đây ta lại tiếp tục đặt gạch vào ô Q1, Q2, Q3, Q4 bằng quay lui

Dãy con có tổng lớn nhất Cách trâu: Cứ chọn mọi tập con của tập có n phần tử, mỗi khi chọn được 1 tập ta tính tổng lại -> 2^n tập con -> cứ áp dụng như các bài trên: Attempt(i, sum): chọn/ko chọn giá trị i vào tổng sum Attempt(i + 1, sum): ko chọn Attempt(i + 1, sum + a[i]): có chọn Nhận xét: n <= 35 → Nếu backtrack bình thường sẽ bị quá thời gian Ở bài này ta sẽ sử dụng kĩ thuật quay lui phân tập (meet in the middle):

1 n/2 n

• Chia dãy con ban đầu ra thành 2 nửa, một nửa A có n/2 tập và nửa còn lại B gồm n - n/2 phần tử • Từ tập A sinh ra mọi khả năng và lưu tổng có thể tạo thành từ các tập con được chọn. • Tương tự như vậy với B Bài toán trở thành: A[1], …..A[t] (t = n/2) B[1].......B[k] (k = n - t) • Từ tập A, sử dụng quay lui để sinh ra tất cả các tập con (như giải pháp trâu ở trên và lưu tất cả các tổng có thể tạo thành từ việc lựa chọn các tập con • Tập A sinh ra được dãy sumA • Tập B làm tương tự mỗi khi sinh ra 1 cái tổng sumB _> cần tìm 1 giá trị trên sumA: Để có: sumB + sumA[x] đạt max • Hàm quay lui: Đối với mỗi số a[i] ta có 2 lựa chọn, dùng nó và đưa nó vào tổng hoặc không dùng nó

Bài toán xếp hậu Nhận xét: Con hậu đặt ở hàng i, cột j sẽ ăn được: • Cả hàng i • Cả cột j • Đường chéo chính có các vị trí có hiệu hàng và cột bằng i - j • Đường chéo phụ có các vị trí có tổng hàng và cột bằng i + j Thuật toán: Với ta xét lần lượt từng hàng trong bàn cờ, với mỗi hàng: Ta thử đặt quân hậu vào tất cả các ô chưa bị đánh dấu, khi đặt 1 quân hậu, ta sẽ đánh dấu tất cả các ô mà nó ăn được để không đặt lại con hậu nào lên các ô đó nữa

void backtrack(int x) //hàng x { if(x > n) //có cách đặt hết hậu { ans++; return; } for(int i = 1; i <= n; i++) //thử hết các cột từ 1 → n { if(!cot[i] && !cheochinh[x - i + n] && !cheophu[x + i])//ô này đặt được hậu { cot[i] = cheochinh[x - i + n] = cheophu[x + i] = true //đánh dấu các ô không đặt được backtrack(x + 1) //đi đến hàng tiếp theo để đặt hậu cot[i] = cheochinh[x - i + n] = cheophu[x + i] = false //trả lại các ô vừa bị đánh dấu } } } Trò chơi dò mìn Gọi mảng b[i][j] cho biết ô i j có mìn không (b[i][j] = 0 : không có mìn, b[i][j] = 1 : có mìn) Ở bài này có đến 30x30 ô, hiển nhiên ta không thể quay lui với từng ô một xem có/không có mìn bởi sẽ bị quá thời gian. Tuy nhiên ta có 1 nhận xét quan trọng: Nếu ta biết các ô ở biên trên và biên trái, thì toàn bộ các ô bên trong có thể suy ra được. Vì vậy ta sẽ dùng thuật toán backtrack để: • Thử đặt mìn cho các ô ở biên • Từ đó suy ra các ô còn lại Đó là ý tưởng chung của bài này, chi tiết: Ta sẽ đi theo đường chéo, bắt đầu ở ô (1,1) ta thử lần lượt 0 và 1 (các bảng bên dưới là giá trị của mảng b)

0/1

Sau đó ta đi đến ô (2, 2), ở đây ta sẽ điền các ô (1,2), (2,1) lần lượt 0 và 1

0/1 0/1
0/1

Từ đó, ta đã có thể suy ra ô (2,2) có bom không bằng cách lấy a[1][1] - b[1][2] - b[2][1]

0/1 0/1
0/1 Đã đc tính

Tiếp đó, ta đi đến ô (3,3), điền các ô (1, 3), (3,1)

0/1 0/1 0/1 0/1 Đã đc tính
0/1

Và tương tự trên, ta sẽ tính được các ô (3,2), (2,3) để rồi cuối cùng tính được ô (3,3)

0/1 0/1 0/1 0/1 Đã đc tính Đã đc tính
0/1 Đã đc tính Đã đc tính

và tiếp tục như vậy cho đến hết, ta sẽ tìm được cấu hình phù hợp

Ý tưởng code hàm backtrack:

void bt(int i){ if(daxong) return;

// đã sinh hết mảng b
if(i>m&&i>n){
    bool ok=true;
    for mọi vị trí và tính xem có ra được mảng a không, nếu không ok = false

    if(!ok) return;
    daxong=true;
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            bluu[i][j] = b[i][j];
    return;
}

if(i==1){
Nếu đây là ô đầu tiên, ta bắt đầu thử
    b[1][1]=0;
    duyet(i+1);
    b[1][1]=1;
    duyet(i+1);
    return;
}

for(b[i][1]=0;b[i][1]&lt;2;++b[i][1])
    for(b[1][i]=0;b[1][i]&lt;2;++b[1][i]){
        bool ok=process(i);
        if(ok) duyet(i+1);
    }

}

Và hàm process sẽ xử lý phần tính toán các ô trong bảng khi đã có đầy đủ viền bool process(int i){ for(int j=2;j<=i;++j) Tự viết hàm inside kiểm tra xem i, j có nằm trong bảng không if(inside(i,j)){ b[i][j]=0; int t=check(i-1,j-1); Tự viết hàm check có dạng a[i-1][j-1] - b[8 ô xung quanh] if(t!=0&&t!=1) return false; b[i][j]=t; }

for(int j=1;j<i;++j)
    if(inside(j,i)){
        b[j][i]=0;
        int t=check(j-1,i-1);
        if(t!=0&&t!=1) return false;
        b[j][i]=t;
    }

if(inside(i,i)){
    b[i][i]=0;
    int t=check(i-1,i-1);
    if(t!=0&&t!=1) return false;
    b[i][i]=t;
}
return true;

}

Xếp ba lô 1 Vì bài này n rất lớn nên ta không thể sử dụng quay lui Bài này ta sẽ sử dụng thuật toán quy hoạch động Bạn nào muốn đọc thêm về quy hoạch động có thể tham khảo ở đây https://wiki.vnoi.info/algo/dp/basic-dynamic-programming-1.md Ý tưởng: • Gọi dp[i][j]: Giá trị tối đa có thể lấy được khi xét đến đồ thứ i và có tổng trọng lượng ba lô là j • Mỗi khi xét đến đồ i: • Trường hợp 1: Không lấy đồ i → res1 = dp[i - 1][j] //Giá trị lớn nhất có thể lấy khi xét đến đồ thứ i - 1 và tổng trọng lượng balo là j • Trường hợp 2: Lấy đồ i → res2 = dp[i][j - w[i]] + v[i] //Giá trị lớn nhất có thể lấy khi xét đến đồ thứ i và tổng trọng lượng balo là j - w[i] → Ta sẽ lấy trường hợp tối ưu nhất trong 2 trường hợp trên: dp[i][j] = max(res1, res2) Đáp án: dp[n][m]

Khóa 4 - Buổi 2 + 3: Đệ quy Bài 2. 99/140 = 0,70714285714285 … 714285 … 5/3 = 1.6666667 a = a % b. Lượt a b thương dư 1 9910 140 7 10 2 10 * 10 140 0 100 3 10010 140 7 20 4 20 * 10 140 1 60 5 60 * 10 140 4
Giới hạn k <= 1000: a = a % b; for(int i = 1; i <= k - 1; i++) a = a * 10 % b; cout << a * 10/b; Bài 3. phát biểu y hệt bài 2 nhưng Không thể dùng vòng lặp được do giới hạn của k for(int i = 1; i <= k - 1; i++) a = a * 10; -> a = a10^( i = 1: a = a * 10^1 %b i = 2: a = a * 10^2 %b i = 3: a = a * 10^3 %b i = k - 1: a = a *10 = a10^(k-1) % b P(x,n,m) tính x^n % m. a = a % b; S = P(10, k - 1, b). a = a * S % b; cout << a * 10 /b; Phép nhân Ấn Độ: a * b = a * b/2 + a * b/2 + a * b % 2 t = a * b/2 a * b = t + t + a (nếu b lẻ) còn ngược lại a * b = t * t (b chẵn)

Bài 4. a = 12: 1 2 3 4 6 12 (3^1 - 1)(3^2 - 1)(3^3 - 1)(3^4 - 1)(3^6 - 1)(3^12 - 1)

Bài 5. Giả nguyên tố Số p là số giả nguyên tố cơ sở 2 là số có tính chất 2^p % p = 2 → Thuật toán: • Sử dụng sàng nguyên tố để xác định các hợp số • Duyệt toàn bộ các hợp số p trong khoảng từ 1 → n, sử dụng hàm pow từ bài 1 và tìm xem những số p nào có tính chất 2^p % p = 2 thì in ra Cài đặt hàm: • Sàng nguyên tố: p[i]= 0/1: ghi nhận i là số nguyên tố hoặc không nguyên tố • Hàm tính P(x, n, m): Tính x^n % m (Bài Lũy thừa) sangnt(); cin >> n; for(i = 1-> n) if(p[i] == 0 and P(2, p[i], p[i]) == 2) //i là hợp số: cout << p[i] << “ ”; Cấp số nhân Ví dụ: Làm thế nào: Cài đặt 1 hàm S(n, m): tính S(n)%m Với n lẻ: S(n, m) = S(n/2, m) *(1 + P(x, (n+1)/2, m)) Với n chẵn: S(n,m) = S(n - 1, m) + P(x, n,m) Neo: n = 0 return 1

Bài Tính tổng: Nhận xét: Các số lẻ: Ước lẻ lớn nhất là chính nó. Với các số chẵn i, ta tính ước lớn nhất của nó bằng cách chia (1, i), (2, i/2). Vậy: ước lớn nhất của i là i/2 Tổng các số lẻ: R(n) = (1 + n)*(n+1)/4 S(n) = Tổng các số lẻ(1-> n) + S(n/2) -> S(n) = R(n) + S(n/2) Neo: n = 0 return 0, n = 1 return 1. n < 2: return n.

Tại sao lại là S(n/2)? • Ta quy truy vấn [l, r] thành [1, r]-[1, l-1] • Bài toán chỉ tính truy vấn dạng [1, n] • long long sumadd(long long n){ // tổng các số lẻ từ [1, n] k = (n+1)/2; return k * k; • } • long long get(long long n){// tổng các ước lẻ trong khoảng [1, n] if(n <= 0) return 0; return sumadd(n)+get(n/2); • } Ví dụ: get(7) = sumodd(7) + get(3) // còn lại 2 4 6 chia 2 ta được 1 2 3 hay chính là get(3) = 16 + get(3) get(3) = sumadd(4) + get(1) // còn lại 2 chia 2 ta được 1 hay chính là get(1) = 4 + get(1) get(1) = 1 So sánh phân số Chia ra các trường hợp: a/b và c/d (b == d) - chỉ việc so sánh tử số. với b != d: Cách để so sánh phân số: a/b và c/d -> ad/(bd) và cb/(bd)

• Quy đồng mẫu số -> chắc chắn có phép * -> không làm được vì tràn số. Tìm cách khác: Dùng 1 phân số thứ 3 để so sánh: a/b và c/d: 3/4 và 5/3 a/b < 1 và c/d > 1 -> KL được rồi cả hai phân số đều lớn hơn 1: -> xét phần nguyên: 5/3 = 1(⅔)và 11/4 = 2(¾): Phần nguyên số nào lớn hơn thì lớn hơn Nếu phần nguyên bằng nhau -> xét hai phân số còn lại: 5/3 = 1(⅔) và 7/4 = 1(¾) -> ta cần so sánh ⅔ và 3/4. Ta sẽ đảo ngược hai phân số thành 3/2 và 4/3(Phân số nào lớn hơn thì
  cả hai phân số đều < 1: a < b và c < d -> lúc này ko có cơ sở để so sánh hai phân số này -> cô sẽ so sánh Phân số đảo của hai phân số này: b/a và d/c: b/a > d/c -> a/b < c/d Tìm bit Xét chuỗi có độ dài 2^k: S = (0…s[2^(k-1)])(s[2^(k-1)] … 0) • Nửa sau là đảo bit của nửa đầu Vậy muốn tìm bit thứ n ta sẽ làm gì ? Viết hàm vitri(n, k) //bit thứ n trong dãy độ dài 2^k • Neo của hàm là khi k = 0 → Ta sẽ trả về n • Trường hợp 1: n nằm ở nửa đầu (n < 2^(k - 1)) → bit thứ n giữ nguyên, ta xét trong dãy nhỏ hơn → Trả về hàm vitri(n, k - 1) • Trường hợp 2: n nằm ở nửa sau (n >= 2^(k - 1)) → bit thứ n là đảo bit của bit thứ n - 2^(k - 1) → bit(n) = 1 - bit(n - 2^(k - 1)) → Ta trả về 1 - vitri(n - 2^k, k - 1)

Nén ảnh:

i,j i, j + k /2

i + k / 2, j i + k/2, j + k/2

Gọi độ dài dãy nén của hình vuông t là S(t) Khi xét hình vuông có kích thước kk: • Nếu tổng các số trong hình vuông = kk hoặc bằng 0 → độ dài dãy nén là 2 • Ngược lại, ta chia hình vuông thành 4 phần, gọi 4 phần đó là A, B, C, D → Độ dài dãy nén = 1 + S(A) + S(B) + S(C) + S(D) → Ta đã có 2 trường hợp rồi, vậy viết đệ quy như nào? Viết hàm calc(i, j, k) //Tính độ dài dãy nén hình vuông xuất phát từ điểm (i, j) và có kích thước kk calc(int i, int j, int k){ ll res = tổng các số trong hình vuông if(res = kk || res = 0) return 2; else return 1 + calc(i, j, k / 2) + calc(i, j + k / 2, k / 2) + calc(i + k / 2, j, k / 2) + calc(i + k / 2, j + k / 2, k / 2); } Lưu ý: Để làm bước tính tổng nhanh các bạn sử dụng mảng cộng dồn trên mảng 2 chiều nhé

Dãy số Farey Tính chất của dãy farey: • Giữa 2 phân số a/b và c/d ta tạo phân số trung gian median = (a + c) / (b + d) • Nếu b + d <= N thì phân số này thuộc dãy farey và nằm giữa 2 phân số trên • Phân số đầu và cuối của dãy farey là 0/1 và 1/1 Ví dụ: Với n = 6 Dãy số farey có mẫu <= 6 0 1 1 1 1 2 1 3 2 3 4 5 1 1 6 5 4 3 5 2 5 3 4 5 6 1 Dãy từ 0/1 … 1/1 → Thuật toán: Chia để trị, chia dãy farey ra làm 2 nửa, với ½ là median của 0/1 và 1/1 ta có: • Nửa đầu từ 0/1 … 1/2 • Nửa sau từ ½ … 1/1 → Lặp lại quá trình trên để sinh ra tất cả các phân số trong dãy farey, thứ tự in từ dãy bên trái → số ở giữa → dãy bên phải

Gấp giấy Folding (Hải Long): với N tới 60, sẽ có 2^60 nếp gấp thì các mảng bth 1 là timeout 2 là segment, thì cách tốt hơn là tìm nếp tại 1 điểm k thì thay vì tìm cách để lưu cả tờ giấy, thì chỉ lưu 1 cái k để xem nó di chuyển ntn qua mỗi lần gấp coi tờ đầu là đoạn từ 0 tới 2^n, có 1 đoạn lặp từ lần 1 tới n b1: tìm điểm m giữa đoạn giấy, điểm chính là vị trí nếp gấp, nếu k trùng m, dừng lại và return kết quả b2: nếu lần gấp là lẽ, phần trái giữ nguyên, phần phải lật sang trái, nếu k ở phải, nó sẽ bị chuyển vị trí sang 2 * m - k thì giấy bị lật! chẵn thì ngược lại, k sẽ ở 2 * m -k để mà xem đảo ngược, đặt v là bool, false là nếp lại A, true là loại B mỗi lần k trong phần giấy gấp như loop trên, ta đặt v = !v xong thì chạy th, em nghĩ cái này O(N) đâu khó tới v nhỉ =)

Solution chuẩn: Gọi dãy nếp gấp ở lần gấp thứ n là F(n) → Bản chất: F(n) = F(n-1) + A + reverse(revert(F(n-1))) Trong đó: • A: (vết lõm khi gấp) • reverse(revert(F(n-1))): đổi các phần tử trong F(n-1) từ A → B và B → A rồi reverse lại dãy Do đề bài gấp luân phiên trái phải, nên ở mỗi bước gấp ta cần đổi hệ quy chiếu vị trí, để biết khi nào gấp trái hay phải ta sẽ dựa trên số lần gấp • Lẻ: Gấp trái sang phải • Nửa trái bị lật • Nửa phải giữ nguyên • Chẵn: Gấp phải sang trái • Nửa phải bị lật • Nửa trái giữ nguyên Ý tưởng đệ quy tìm phần tử ở vị trí k: Viết hàm bool Findpos(len, k, cnt) //Phần tử ở vị trí k trong dãy nếp gấp độ dài len với số lần gấp cnt • Trả về true nếu là A • Trả về false nếu là B Đặt len = 2^n, mid = len / 2 Trường hợp 1: cnt chẵn • Nếu k = mid → Đó là vết lõm ở giữa → là A • Nếu k < mid → Vết lõm nằm ở nửa trái → Do nửa trái giữ nguyên→Ta trả về Findpos(mid, k, cnt+1) • Nếu k > mid → Vết lõm nằm ở nửa phải → Do nửa phải bị lật → Vị trí tương ứng của nó trong dãy đảo là len - k, đảo lại kết quả(A→B, B→A) → Trả về !Findpos(mid, len - k, cnt + 1)

Trường hợp 2: cnt lẻ • Nếu k = mid → trả về true • Nếu k < mid → Vết lõm nằm ở nửa trái → Do nửa trái bị lật → Ví trí tương ứng là mid - k, đảo kết quả → trả về !Findpos(mid, mid - k, cnt + 1) • Nếu k > mid → Vết lõm nằm nửa phải → Do nửa phải giữ nguyên → Vị trí tương ứng là k - mid → trả về Findpos(mid, k - mid, cnt + 1)

Gấp dây Ý tưởng: Thử mọi điểm có thể gấp ở trên dây, với mỗi điểm, ta chỉ cần kiểm tra xem tất cả các điểm có điểm nào tương ứng với nó không • Với điểm gấp g: → 2 điểm x và y đối xứng với nhau nếu g - x = y - g Vì vị trí gấp có thể là .5 (Ví dụ 1.5, 0.5 , …) → Ta nhân cả mảng lên 2 lần để tránh phải xử lí số thực • Sắp xếp lại mảng tăng dần để dễ xử lí • Thử mọi số nguyên g trong khoảng [1, 2L - 1] • Với mỗi vị trí g: • Tìm vị trí p cuối cùng có a[p] < g • Tìm vị trí q đầu tiên có a[q] > g → Tất nhiên để tất cả các nút đều có vị trí đối xứng với nó thì p và q phải tương ứng với nhau, tương tự, p - 1 và q + 1 tương ứng, … → Sử dụng 2 con trỏ, duyệt i từ p về 1, j từ q đến 2L - 1, kiểm tra g - a[i] = a[j] - g • Nếu có 1 cặp không bằng nhau thì vị trí g này không thỏa mãn, ngược lại ta tăng đáp án thêm 1

Bài 15 (Hải Long): Đầu tiên, sắp xếp các mỏ trái -> phải để khi chia nhóm, cắt đoạn dễ b2: tìm vị trí đặt nhà máy cho 1 trong số các nhóm kia, thì quy tắc là đặt ở điểm cân bằng về sản lg nghĩa là tính tổng sản lg, đi từ đầu rồi cộng dòng, khi nào cộng dòng = 1/2 tổng sản lg thì dừng thì chỗ đó đặt nhà máy, họi là trung vị b3: vận chuyển thôi! chạy qua từng mỏ lấy sản lg cộng lại, ra chi phí nhóm đoạn sau khó nhé, quy hoạch động đầu tiên sẽ lập 1 cái bảng ghi nhớ, là cái dp đó nếu chỉ có 1 nhà máy tốn bao nhiêu? nếu có 2 nhà máy? tính tới K nahf máy! rồi in ra kết quả ở đáy (dp[n][k]) KHóa 4 - Buổi 1) Tổng ôn tập đầu khóa Bài A Bài B Bài C: Cho 1 dãy số nguyên dương a1-> an và một số M Đếm các đoạn con có tổng <= M

i 0 1 2 3 4 n a a1 a2 a3
s 0
s[0] = 0 s[i] = a[1] +... + a[i] = s[i - 1] + a[i] Nhận xét vì a[i] > 0 s[i] = s[i - 1] + a[i] > s[i - 1] Vậy s là 1 mảng tăng dần.

1. s[1] <= M
2. s[2] <= M
3. s[3] <= M
4. s[4] <= M
5. … i - 1. s[i-1] <= M i. s[i] > M Với mỗi a[i] ta cần tìm vị trí j sao cho: s[j] - s[i - 1] > M 5 4 1 2 3 4 5 i 0 1 2 3 4 5
   a 1 2 3 4 5
   s 0 1 3 6 10 15
   Xét s[1]: 1, 1 2 (2) Xét s[2] = 3, đi tìm s[j] - s[1] > 4 -> s[j] > 4 + 1 =5 s[2]: 2 (1) s[3]: s[j] - s[2] > 4 s[j] > 4 + 2 = 7: 3(1) s[4]: 1 Bài toán trở thành: với mỗi i: ta cần tìm j sao cho s[j] - s[i - 1] > -> s[j] > s[i - 1] + M Khi đó: KQ được cập nhật: res += (j - i). res = 0; for(i = 1-> n) { v = s[i - 1] + M; x = upper_bound(s, s + n + 1, v)- s; res += x - i; } Bài 4: (bài toán ngược của bài 3): cho trước số lượng đoạn con đẹp, cần xác định giá trị M sao cho có tồn tại k đoạn con có tổng <= M (đẹp). Nhận xét: khi M càng tăng thì số lượng đoạn con có tổng <= M càng tăng lên -> Điều này gợi ý cho ta sử dụng phương pháp chặt nhị phân để tìm M: L = 1, R = 10^14, mid; while(L <= R) { mid = (L + R)/2; if(BaiC(mid) < k) L = mid + 1; else R = mid - 1; } Đáp số: L Bài 5: Cần xác định mỗi độ cao h[i] có bao nhiêu chướng ngại vật Dùng 1 mảng thống kê: H[1] -> H[5*10^5 + 1] xem với mỗi h[i] có bao nhiêu chướng ngại vật. Tìm giá trị min trong mảng H và số lượng phần tử nhỏ nhất đó. Bài 6. Bài này chính là bài Đua ngựa (phiên bản chỉ tính trận thắng) 5 a: 2 3 5 1 7 -> 1 2 3 5 7 b: 3 5 2 6 2 -> 2 2 3 5 6 i = 1, j = 1; while(i <= n && j <= n) { if(a[i] < b[j])-> xử luôn i++, j++; cnt++; else j++

} Bài G • Ta sẽ chặt nhị phân số kẹo tối đa mà mỗi học sinh có thể nhận tạm gọi là mid • Để kiểm tra xem tồn tại cách chia mà mỗi học sinh không quá mid ta chia tham lam mỗi loại kẹo cho ít học sinh nhất có thể mà tổng số học sinh nhận kẹo không quá n thì là hợp lệ • Mỗi loại kẹo i gồm ai sẽ phải chia cho tối thiểu ai/mid (làm tròn lên) học sinh (vì phải chia hết số kẹo). Vậy là tổng số học sinh ít nhất để chia hết kẹo sẽ là tổng của biểu thức trên với mỗi loại kẹo. → nếu tổng đó > n thì hàm check = false, ngược lại thì mid là 1 cách chia thỏa mãn, check = true

Bài H • Bài này có một nhận xét quan trọng như sau nếu hai hình chữ nhất i, j mà hi>= hj, wi >=wj thì hình chữ nhật i chứa hình chữ nhật j nên chỉ cần tính diện tích hình chữ nhật i là đủ. • Ta sẽ sắp xếp hình chữ nhất theo thứ tự giảm dần của h tức i<j thì hi>hjthì hình chữ nhật j chỉ lòi ra so với i hình chữ nhật trước đó nếu wj >max(wi) và phần lòi ra của hình chữ nhật j so với các hình chữ nhất i trước đó chính là hj(wj-max(wi)) (vì nếu wj<= max(wi) thì hình chữ nhật j sẽ bị bao trọn bởi các hình chữ nhật trước đó) với max(wi) là wi lớn nhất của các hình chữ nhất i trước đó • Để tính max(wi) nhanh chóng thì ta chỉ việc duy trì biến mx chính là max(wi) mỗi lần ta chỉ việc cập nhất mx = max(mx, wi) → Cách code: Ta tính trước diện tích hình chữ nhật w[1]h[1] (sau khi sort giảm dần) sau đó cộng thêm với phần dư của mỗi hình chữ nhật lòi ra sau đó ( các hình chữ nhật có wj >max(wi)) một khoảng bằng hj*(wj-max(wi))

Bài I • Gọi mảng dồn theo phần dư với d của dãy a là sum tức sumi=(sumi-1+ai)%d • Thì để một đoạn con liên tiếp từ [l, r] chia hết cho d thì sumr-suml-1 =0 hay sumr=suml-1 • Hay bài toán bây giờ của ta là đếm số cặp giá trị bằng nhau trên mảng sum. Việc này có thể dễ dàng làm được bằng cách sắp xếp lại mảng sum dần đếm số lượng các phần tử bằng nhau liên tiếp (Khóa 3 - Buổi 10): Kiểm tra cuối khóa

Tặng quà Dùng mảng cnt1 và cnt2 cnt1[x] = số lượng số có giá trị = x cnt2[x] = số lượng số có giá trị = -x ⇒ For(i:1->n) if(x<0) thì cnt2[-x]++ else cnt1[x]++ ⇒ For(i:1→1e6) ans += cnt1[x]cnt2[x]; // duyệt hết tất cả các cặp ans += cnt1[0](cnt1[0]-1)/2;

Điền số (FILLNUM) Nhận xét: x không được vượt quá n^2 Vì nếu x > n^2 thì sẽ không có cách thỏa mãn ⇒ x <= 10^14 ⇒ xét tất cả các ước của x for(i:1;i*i<=x;++i) if(x%i==0) if(x/i<=n&&i<=n) // Nằm trong bảng cnt++;

cout << cnt

Tập xe CSP For(i:1->n) // Với mỗi i, tìm số lượng thằng j thỏa mãn với i ⇒ Dùng chặt nhị phân (lowerbound / upperbound)

Dãy con

a1 a2 ... am

b1 b2 b3 b4 b5 b6 bn

Nếu a là dãy con của b thì chắc chắn phải tồn tại tập con j1<j2<...<jm sao cho b[j1] = a[1], b[j2] = a[2], …, b[jm] = a[m]</p>

Giả sử có 2 vị trí có thể của j1 như 4 và 6 trên. Thì ta cần ưu tiên chọn vị trí càng nhỏ càng tốt, để có “nhiều đất” cho thằng j2

int j = 1 For(i:1→m) { while(j<=n && b[j]!=a[i] ) j++; if(j>n) { cout << “NO”; return; // Bước này giúp dừng lại cả hàm luôn } ans.push_back(j) ; } cout << “YES” for ( int x : ans ) cout << x; Họp lớp Nhận xét: Khoảng thời gian mình cần quan tâm chỉ là khoảng [a,b] --> Trong khoảng thời gian từ a --> b thì ở thời điểm nào có nhiều bạn đến nhất Tính xem trong mỗi khoảng thời gian có bao nhiêu bạn có thể đến, for từ a --> b để tìm ra thời điểm nhiều bạn đến nhất

Thuật toán “ngây thơ”: • Với mỗi truy vấn G x --> Bạn i sẽ có thể đến trong khoảng từ [x, b] --> for j từ x → b, cnt[j]++ • Với mỗi truy vấn L x --> Bạn i sẽ đến trong khoảng từ [a, x] --> for j từ a → x, cnt[j]++ Sau khi thực hiện hết các truy vấn, việc còn lại chỉ là for từ a → b để tìm ra thời điểm cho cnt lớn nhất

Cải tiến: Ở đây ta sẽ cải tiến ở 2 điểm • Thứ nhất: Cải tiến việc cập nhật, sử dụng kĩ thuật mảng hiệu để tăng tốc độ cộng hết các phần tử trong khoảng bất kì thêm cùng 1 giá trị, ví dụ, tạo một mảng hiệu diff[]: • Với G x: ta cho diff[x]++, diff[b + 1]-- • Thứ 2: Sau khi thực hiện hết các truy vấn, thông thường ta sẽ for từ a → b để cộng dồn mảng hiệu và tìm ra đáp án, nhưng vì a, b rất lớn (1e9) nên không thể for như vậy • Thay vào đó, ta sẽ chỉ cộng dồn ở những điểm then chốt (những điểm bị thay đổi ở mảng hiệu phía trên) Cách code: • Khi cập nhật mảng hiệu ở các truy vấn, ta sẽ push pair<chỉ số được cập nhật, giá trị cập nhật> vào 1 vector<pair> tạo trước • Sau đó sort vector lại theo first để các điểm được cập nhật tuần tự → Không làm thay đổi ý nghĩa của mảng hiệu • Thực hiện cộng dồn với các phần tử trên vector vừa tạo và tìm phần tử lớn nhất

Trung bình cộng (AVERSEG) Giả sử a <= b Trường hợp 1: c <= a || c >= b --> ans = 1 Giải thích: Dãy càng có nhiều số --> Trung bình cộng càng hội tụ về giữa a và b --> Sẽ xa hơn so với việc chỉ chọn a hoặc chỉ chọn b Trường hợp 2: c nằm trong a --> b

• Trường hợp 2.1: Nếu ta lấy 2 số --> (a + b) / 2
• Trường hợp 2.2: Nếu ta lấy > 2 số:
  • Trường hợp 2.2.1: Nếu lấy chẵn số --> trung bình ko khác gì trường hợp 2.1 --> ko tối ưu bằng 2.1 vì cần lấy ít số nhất
  • Trường hợp 2.2.2: Nếu lấy lẻ số --> Số lượng số sẽ có dạng 2k + 1: Dãy có thể bắt đầu từ a hoặc b if(c > (b + a) / 2) swap(a,b); --> ta sẽ muốn dãy luôn bắt đầu từ số gần c hơn, ta sẽ mặc định a gần hơn vì thế cần swap nếu c gần b hơn Dãy bắt đầu từ a --> a,b,a,b,...,a → Có k + 1 số a, k số b --> Trung bình cộng là abs((a * (k + 1) + bk) / (2k + 1) - c) min --> (a * (k + 1) + bk) / (2k + 1) - c = 0 --> abs(a * (k + 1) + bk - c * (2k + 1)) / (2k + 1) min --> a * (k + 1) + bk = c * (2k + 1) Chuẩn hóa: b = b - a, c = c - a, a = a - a = 0 --> bk = c * (2k + 1) --> bk = c * 2k + c --> k * (b - 2c) = c --> k = c / (b - 2c) --> k xấp xỉ c / (b - 2c) → k có thể bị lệch 1 đơn vị so với đáp án --> Cần kiểm tra xem k tối ưu hơn hay k + 1 hơn Kiểm tra: abs(bk - c * (2k + 1)) / (2k + 1) > abs(b(k + 1) - c * (2k + 3)) / (2k + 3) --> if(abs(bk - c * (2k + 1)) * (2k + 3) > abs(b(k + 1) - c * (2k + 3)) * (2k + 1)) --> ans = k + 1 else ans = k; cout << 2 * ans + 1;

Chó kéo xe Ban đầu ta chưa cho người nào ngồi lên xe Ta sẽ có 2 công thức sau: • Số chú chó cần để kéo người a[i] là x = ceil(a[i] / k) = (a[i] - 1) / k + 1 → Phần dư ra là p[i] = k * x - a[i] • Số chú chó cần để kéo xe b[j] là y = ceil(b[j] / k) = (b[j] - 1) / k + 1 → Phần dư ra là q[j] = k * y - b[j] Để tiết kiệm được số chú chó, ta sẽ tìm những cặp i và j sao cho p[i] + q[j] >= k, vì khi ghép những cặp này thì phần dư ra vượt quá giới hạn của 1 chú chó, nên ta sẽ tiết kiệm được 1 con với mỗi cặp Ví dụ a[i] = 5, b[j] = 6, k = 4 → Ban đầu ta dùng 2 chó cho a[i], 2 chó cho b[j], tổng là 4, nhưng ta tính được dùng thế thì dư tận 3 cho a[i], dư 2 cho b[j], và 3 + 2 > 4 → nếu ghép a[i] và b[j] thành 1 cặp thì ta chỉ cần 3 chó thôi, tiết kiệm 1 chú

Vậy thuật toán của ta là tìm số cặp p[i] + q[j] >= k nhiều nhất có thể, các bạn có thể sử dụng 2 con trỏ để giải quyết Chiến thuật tham lam: • Sắp xếp mảng p và q tăng dần • Dùng hai con trỏ: ghép q[j] lớn nhất với p[i] nhỏ nhất, nếu q[j] + p[i] >= k, ghép luôn, ngược lại thì p[i] sẽ không ghép được với ông nào nên ta sẽ bỏ qua

(Khoá 3 - Buổi 9): Luyện tập tổng hợp 2

BÀI Xếp thùng sơn Duyệt từ trái sang phải, nếu dãy đầu là đỏ thì ta lấy min(k,n). Nếu dãy đầu là Xanh thì ta lấy max(0, k - n)

BÀI Đánh số trang Xây dựng hàm tính số chữ số của 1 trang Sau đó ta đi xét lần lượt từng trang 1 để đếm số lượng các chữ số được tạo ra, nếu vẫn < và không bằng N thì ta tăng tiếp.

BÀI Ủng hộ Ta có nhận xét, số lớn nhất <=s mà chia hết cho x là: s - s%x Do vậy ta chỉ cần duyệt từ (s - s%x) đến a+1 là các giá trị: …, s - x, s - 2x, s - 3x, … Vậy mỗi một giá trị trên ta sẽ tìm được 1 giá trị là số sách cho trường N.

BÀI Ngày hội sách Bước 1: Xây dựng hàm cộng dồn để dễ dàng tính được mức độ hấp dẫn trong 1 đoạn bất kì Giả sử i quyển đầu tiên chỉ đọc bìa. Vậy ta có thể đọc i =min(n, t/b) quyển Số quyển sách còn lại có thể đọc cả quyển là: y = (t - b*i)/a Duyệt lần lượt từng giá trị i Ta sẽ lấy các phần tử từ (i+1) -> (i+y) Hay chính là s[min(n, i + y)] - s[i]), cập nhật kết quả lớn nhất.

BÀI Mượn sách BÀI Cặp số đặc biệt Nhận xét: Các phần tử a[i] là phân biệt và a[i] <= 2*n Ta cần tìm các cặp i, j sao cho a[i] * a[j] = i + j Mà i + j <= 2 * n, không mất tính tổng quát giả sử a[i] <= a[j] → a[i] <= sqrt(2n) Đến đây ta có thể nghĩ đến việc duyệt theo giá trị thay vì duyệt theo mảng như bình thường • Tạo mảng pos[a[i]]: lưu lại vị trí xuất hiện của a[i] • for i = 1 → sqrt(2n) if(pos[i] > 0) //giá trị i có tồn tại for(int j = i + 1, j * i <= 2n; j++) { if(pos[j] > 0) //giá trị j tồn tại if(pos[i] + pos[j] = i * j) ans++ }

Đường tròn Thực hiện việc nhảy k lần, bắt đầu từ vị trí p = 1 Tại mỗi lần nhảy: • Nhảy d bước → p += d, nếu p <= n → chưa ra khỏi vòng tròn thì ans += p • Ngược lại, nếu p > n → ta phải tìm xem vị trí nó nhảy quá trên đường tròn là bao nhiêu thì đó chính là p % n → p %= n, ans += p

Phát quà Yêu cầu: Tìm số 𝑥 nhỏ nhất sao cho tồn tại phương án Bình chọn quà mà An không thể có cách chọn được tổng giá trị quà lớn hơn x → Tìm giá trị quà lớn nhất An có thể chọn nếu Bình chọn tối ưu

Thuật toán: Ta cho Bình chọn thử hết tất cả các cách có thể rồi tìm xem trong các cách chọn đó thì cách nào làm cho giá trị lớn nhất An có thể chọn là nhỏ nhất

• Giả sử Bình chọn điểm xuất phát là i → dãy Bình chọn là [i, i + k - 1] → An chỉ có thể lấy được quà ở 1 trong 2 vùng [1, i - 1] và [i + k, n] Mà ta cần tìm giá trị quà lớn nhất An có thể chọn → Nghĩa là ta cần dãy độ dài k có giá trị lớn nhất trong 2 dãy [1, i - 1] và [i + k, n]

• Gọi p là dãy độ dài k có giá trị max trong dãy [1, i-1], q là dãy độ dài k có giá trị max trong dãy [i + k, n] → Giá trị lớn nhất An có thể chọn chính là max(p,q) Vậy tính p như nào ? • Nhận xét: Giả sử món quà đầu tiên (điểm xuất phát) mà An chọn có chỉ số là i → món quà cuối cùng An chọn chính là i + k - 1 và tổng giá trị dãy quà đó là prefix[i + k - 1] - prefix[i - 1] → Ta tìm p bằng cách duyệt hết điểm xuất phát có thể trong đoạn [1, i - 1] và lấy max của tất cả (prefix[i + k - 1] - prefix[i]) Chú ý: vì dãy có độ dài k nên điểm xuất phát có thể chỉ có thể là các vị trí trong khoảng [1, i - k] → Tuy nhiên duyệt như thế sẽ mất thời gian Cải tiến: sử dụng kĩ thuật max dồn: • Gọi l[i] là giá trị của dãy quà nếu điểm xuất phát An chọn là i → l[i] = prefix[i + k - 1] - prefix[i - 1] • Thay vì duyệt để tìm l[i] lớn nhất thì ta sẽ duy trì 1 mảng prefixmaxleft[i]: giá trị l[i] lớn nhất có thể tính đến vị trí i → prefixmaxleft[i] = max(prefixmaxleft[i - 1], l[i]) Vậy p chính là prefixmaxleft[i - k] Làm tương tự để tìm q → Giá trị lớn nhất An có thể chọn trong trường hợp Bình chọn điểm xuất phát là i chính là max(p,q) → Làm tương tự với tất cả các điểm xuất phát Bình có thể chọn và tìm min của chúng

(Khoá 3 - Buổi 8): Luyện tập tổng hợp 1 BÀI Chia hết Sub 1: 2 vòng lặp Sub 2: 1 vòng lặp từ 1 đến 10^6 Sub 3: 1 vòng lặp từ 1 đến sqrt(n) Với mỗi i ta tìm dc n/i tương ứng là 1 cặp (a,b) Tìm dc d của nửa từ 1 đến sqrt(n) ta phải nhân đôi vì còn 1 nửa từ sqrt(n+1) đến n. Vậy vì sao phải trừ đi k^2? Các cặp (a,b) với a<=k và b<=k đều bị đếm 2 lần nên số cặp tạo thành là k^2. ta phải trừ đi BÀI Tìm số Sử dụng hàm pre_permutation() để sinh cấu hình gần số ban đầu nhưng nhỏ hơn.

BÀI Số phía sau Sử dụng hàm nextpermutation() để sinh cấu hình gần số ban đầu nhưng lớn hơn. BÀI Tập xe Sắp xếp lại trọng lượng các học sinh tăng dần, Duyệt lần lượt từng học sinh, với mỗi a[i] ta đi tìm xem có vị trí nào có giá trị bằng x = p - a[i]. Việc tìm kiếm x có thể sử dụng hàm upperbound

BÀI Khu vườn Ý tưởng: Có thể làm cho tất cả các cây có độ tươi tốt ≥ x hay không, với tối đa L lít nước? Từ đây ta sẽ đi tìm giá x lớn nhất bằng cách tìm kiếm nhị phân trên đáp án. Tức là tìm trong khoảng từ 1 đến 10^9.

Chương trình chính

BÀI Tổng đoạn con Ở bài này, ta vừa áp dụng mảng hiệu và mảng cộng dồn: Sử dụng mảng hiệu. Gọi diff[i] = a[i]-a[i-1] (Chênh lệch giữa 2 thằng cạnh nhau) Mỗi truy vấn l,r,x là tăng đoạn a[l],a[l+1],...,a[r] lên x

i 1 2 … L L+1 … R R+1 n +x +x +x +x
Nhận thấy là chênh lệch giữa 2 thằng cạnh nhau từ vị trí L ⇒ R là không thay đổi (tức diff[L+1],diff[L+2],...,diff[R] không thay đổi) Tuy nhiên diff[L] và diff[R+1] thay đổi vì a[L] và a[R] tăng lên x, nhưng a[L-1] và a[R+1] không thay đổi ⇒ diff[L] tăng x đơn vị ⇒ diff[R+1] giảm x đơn vị Cách code: Thiết lập mảng diff ⇒ Khi cin mảng a, ta có mảng diff với diff[i] = a[i]-a[i-1] Sau đó mỗi truy vấn l,r,x thì diff[L] += x; diff[R+1] -=x; Sau q truy vấn, từ mảng diff, ta có thể tìm lại được mảng a. • Vì diff[i] = a[i]-a[i-1] ⇒ diff[1] = a[1]-a[0] mà a[0] = 0 ⇒ diff[1] = a[1] • Khi có a[i-1] ta hoàn toàn có thể tìm được a[i] với công thức a[i] = diff[i]+a[i-1] ⇒ Khi có được mảng a sau khi thay đổi thì ta sẽ sử dụng prefix sum để trả lời truy vấn

Dãy số Cách giải của bài này hoàn toàn tương tự bài đoạn con có tổng lớn nhất mà chúng ta đã làm, chỉ khác là bây giờ ta chỉ cập nhật min(sum[l - 1]) khi r là số nguyên tố và xét tại các điểm r là số nguyên tố chứ không xét toàn bộ n điểm r như trước Xóa chữ số Nhận xét: Chữ số thứ i đầu tiên tính từ bên trái thỏa mãn: s[i] < s[i+1] chắc chắn phải xóa → Thuật toán: Tìm chữ số đầu tiên từ bên trái < chữ số liền sau và xóa luôn cho tới khi xóa đủ k chữ số Ví dụ: với s = 7918256, k = 4 Cách code: • Lấy từng ký tự trong xâu s đưa vào một xâu kết quả t • Khi một ký tự c trong s được xét: • Nếu t rỗng hoặc k = 0 hoặc c ≤ ký tự cuối của 𝑡 → Đưa c vào cuối xâu 𝑡 • Nếu không: Xóa ký tự cuối của 𝑡 và lặp lại cho tới khi rơi vào TH trên: t rỗng hoặc k = 0 hoặc c ≤ ký tự cuối của t • Khi xét hết xâu s mà k > 0, xóa nốt k ký tự cuối → Khi kết thúc, t chính là xâu cần tìm

(Khoá 3 - Buổi 7): Luyện tập các kĩ thuật

BÀI Cặp số Gợi ý: Bước 1: Sàng nguyên tố. Bước 2: Duyệt từ 2 với i + k<= n if (isPrime[i] && isPrime[i + k]) { ++countPairs; }

BÀI Bộ ba có tổng lớn nhất Gợi ý: Sắp xếp lại dãy, sau đó tạo mảng chỉ lấy ra các phần tử khác nhau từ mảng ban đầu.

So sánh abs(tổng 3 số đầu tiên) và abs(tổng 3 số cuối cùng) giá trị nào lớn hơn thì lấy.

BÀI Dãy kí tự ‘A’ + n*(n+1)/2 % 26

BÀI Cắt sắt Giải thuật 1: với mỗi k. ans = 0; for i = 1..n: ans += abs(a[i] - k); Giải thuật 2: Ý tưởng:

1. Sắp xếp lại dãy a.
2. Xây dựng mảng cộng dồn của dãy a.
3. Tách thành 2 nhóm a. 1 nhóm chứa các phần tử < s b. 1 nhóm chứa các phần tử >=s

Với mỗi k ta đi tìm 1 vị trí mà giá trị a[i] < s sử dụng tìm kiếm nhị phân, hàm lower_bound tìm ra vị trí đầu tiên >= s. Nhóm 1: a[i] < s → phải nối thêm Số thanh: tmp - 1 Chi phí: (s−a[1])+(s−a[2])+...+(s−a[tmp−1]) Công thức tổng quát s * (tmp - 1) - b[tmp - 1] Nhóm 2: a[i] ≥ s → phải cắt bớt Số thanh: n - tmp + 1 Chi phí: (a[tmp]−s)+...+(a[n]−s) Công thức tổng quát (b[n] - b[tmp - 1]) - s * (n - tmp + 1) code mẫu

BÀI Trại gà • Chặt nhị phân tìm thời gian nhỏ nhất mà bé Bo thu được ít nhất x quả trứng • Làm sao để kiểm tra xem ở ngày mid bé Bo đã nhận được bao nhiêu trứng? • Con gà i sẽ đẻ ra max[(mid-ai) /bi+1, 0] quả trứng trong mid giây → Để kiểm tra xem với thời gian mid thu được quả trứng chỉ cần tính tổng số trứng nhận được trên tất cả con gà trong mid giây là được

Gợi ý code hàm check: BÀI Di chuyển cây Để ý thấy giới hạn bài này rất nhỏ: m, n, t <= 100 → Ta hoàn toàn có thể làm trâu được • Với mỗi điểm a[i][j], ta lần lượt đi sang trái và phải điểm đó để đếm xem trên hàng đó có mấy ô liền kề bằng nó, nếu có >= t → Giữ lại cây a[i][j] • Nếu không, ta tiếp tục kiểm tra hàng dọc, đi lên và đi xuống điểm đó để đếm xem trên cột chứa điểm đó có mấy ô liền kề bằng nó, nếu có >= t → Giữ lại cây a[i][j], ngược lại thì cây a[i][j] là cây cần di chuyển Câu lạc bộ • Tại mỗi thời điểm, ta cần đếm xem có bao nhiêu học sinh ở đó • Học sinh thứ i sẽ ở lớp trong khoảng thời gian từ a → b → Trong khoảng thời gian từ a → b sẽ có thêm 1 bạn học sinh ở lớp Từ đây ta nảy ra ý tưởng trâu: • Duy trì mảng dem[x] với ý nghĩa lưu lại số học sinh ở lớp tại thời điểm x • Với mỗi học sinh i, tăng dem[x] thêm 1 cho mọi x từ a[i] đến b[i] → Để tối ưu, ta nhận thấy chính là bài toán quen thuộc với chúng ta, sử dụng kĩ thuật mảng cộng dồn để tính số học sinh ở lớp tại mỗi thời điểm x từ 1 → 1e6 (do a[i], b[i] <= 1e6) (giống bài tưới cây 1) Cách làm:

1. Tạo mảng dem[x] ban đầu bằng 0
2. Với mỗi học sinh i có khoảng thời gian đến và đi là a[i] và b[i]: • dem[a[i]]++; • dem[b[i] + 1]--
3. Tính cộng dồn lại dem[x] cho mọi x từ 1 → 1e6 (để bao phủ hết các điểm trên trục thời gian)
4. Lấy giá trị lớn nhất của dem[x] Đoạn con Nhận xét: • Tổng mỗi đoạn chỉ có thể là ước của tổng cả dãy Ý tưởng: • Gọi S là tổng tất cả các phần tử • Ta duyệt tất cả các ước d của S, kiểm tra xem có thể chia dãy thành các đoạn con có tổng = d không • Cách kiểm tra: • Tạo một biến res = 0 • Duyệt từ trái sang phải, cộng lần lượt các phần tử vào res • Nếu res > d → Không thể chia → return false • Nếu res == 0 → Đặt lại res = 0 để bắt đầu đoạn con mới • Nếu đến cuối cùng duyệt hết mà không lỗi → return true (Có thể chia được)

Ngày 23/12/2025 Mua sữa

C = 100, D = 99 => C-D = 1 A = 100 => mua được 1 lần chai thuỷ tinh Đồng xu • Tổ chim thứ i cần thêm bi - ai đồng xu để rơi xuống • Khi rơi xuống, ta có thêm ai đồng xu • Tham lam: Ném tiền vào tổ cần ít đồng xu nhất => Cho nó rơi xuống -> nhặt tiền Cách làm: • Sắp xếp theo bi - ai tăng dần b1 - a1 < b2 - a2 < b3 - a3 < … < bn - an • Nếu ném rơi được tổ 1: m += a[1] • Nếu ném rơi được tổ 2: m += a[2] • …

Số nguyên tố lớn nhất ans = -1

• B1: Tìm vị trí của hai dấu ? • B2: • for (c = ‘0’ -> ‘9’) • for (d = ‘0’ -> ‘9’) • Điền c, d vào số • B3: Kiểm tra số thu được có phải số nguyên tố không ? • Truy cập xâu • Biến xâu thành số Nguyên tổ • Duyệt qua MỌI xâu con liên tiếp có độ dài <= 5 của xâu đã cho • Kiểm tra có ký tự không phải chữ số • Kiểm tra đoạn đó có tạo thành số nguyên tố hay không: • Biến xâu thành số • Kiểm tra số nguyên tố

s = “51234” v = 51234 —------------------ v = 0 for (char c : s) { v = v * 10 + (c - ‘0’) }

• Các số phải in ra theo thứ tự xuất hiện: • s[i … j] • Dùng mảng đánh dấu ck[v] = số v đã được in ra hay chưa ? Số lớn nhất • Không biến xâu thành số, so sánh xâu: • 437856874398798374987295 428234875283746234526437897 • Số có nhiều chữ số hơn thì lớn hơn • Khi hai số có cùng số lượng chữ số: So sánh theo thứ tự từ điển • Hai con trỏ

// s[i…j]: s[i] != ‘0’ string ans = “”; for (int i = 0; i < s.length(); ++i) { if (s[i] là chữ số và s[i] != ‘0’) { int j = i; while (j < s.length() && s[j] là chữ số) ++j;

    // s[i … j - 1] = một số
    if (ans.length() < j - i || ans.length() == j - i && ans < s.substr(i, j - i)) ans = s.substr(i, j - i);

    i = j - 1;

} }

    i               j <- i

Phố đi bộ • Ở bài này ta cần đếm số lượng phần tử mà bé hơn di-r với mỗi điểm vui chơi di → Với mỗi điểm d[i] ta cần đếm số điểm j sao cho dj<di-r • Sắp xếp lại mảng d tăng dần • Với mỗi i ta cần tìm j lớn nhất mà thỏa mãn dj<di-r vì sắp xếp mảng d tăng dần thì mọi d1, d2, ..., dj<di-r ⇔ có j vị trí thỏa mãn ứng với i => Ta chỉ việc tính tổng các giá trị j ứng với mỗi i thì ta thu được kết quả

Cấp số cộng • Dựa vào thứ tự ưu tiên của bài ta sẽ ưu tiên tìm ai nhỏ nhất xong đến aj và ak bằng cách sắp xếp dãy a tăng dần sau đó tìm bộ ba (i < j <k) nhỏ nhất có thể • Nhận thấy n <= 5000 không quá lớn đủ cho ta duyệt lần lượt các cặp (i, j) tăng dần trong độ phức tạp là O(n2) • Khi ấy công việc của ta là kiểm tra xem tồn tại k nhỏ nhất thỏa mãn hay không thì ta thấy điều kiện cần thỏa mãn ak-aj=aj-ai → ak=2*aj-ai mà i, j đang duyệt nên bài toán của ta bây giờ là tìm xem ak tồn tại hay không thì quen thuộc ta dùng chặt nhị phân tìm kiếm ak thỏa mãn Vòng tròn • Nhân đôi dãy => Biến bài toán dãy vòng tròn về dãy 1d • Tìm dãy con liên tiếp không giảm dài nhất

i i n 1 j

Dãy đối xứng Nhận xét: • Vì phép biến đổi là phép tính cộng → Khi biến đổi sẽ làm tăng giá trị của phần tử • Để dãy trở thành đối xứng thì 2 đầu của nó phải bằng nhau Thuật toán: • Sử dụng kĩ thuật 2 con trỏ, tạo con trỏ i là đầu dãy, j là cuối dãy • Thu hẹp dần vào giữa dãy (i tăng, j giảm): • Nếu a[i] = a[j] → Đã đối xứng, thu hẹp vào • Nếu a[i] < a[j] → Gộp a[i] với a[i + 1], thu hẹp phía bên trái (i tăng) • Nếu a[i] > a[j] → Gộp a[j] với a[j - 1], thu hẹp phía bên phải (j giảm) • Lặp lại cho đến khi i >= j thì ta đã tạo được dãy đối xứng và số thao tác gộp chính là đáp án của chúng ta

Cưa máy Nhận xét: Với mỗi truy vấn m[i] bất kì, nếu ta đặt độ cao của lưỡi cưa là k thỏa mãn thì chắc chắn mọi độ cao < k cũng thỏa mãn → Ta có thể nghĩ đến thuật toán chặt nhị phân đáp án Thuật toán: • Với mỗi truy vấn m[i], ta chặt nhị phân để tìm độ cao k của lưỡi cưa sao cho k là lớn nhất và tổng số mét gỗ thu được >= m[i] • Sắp xếp lại chiều cao của các thanh gỗ tăng dần • Cách viết hàm check(k): • Gọi j là chiều cao của thanh gỗ đầu tiên >= k (j = lower_bound(k)) → (Chỉ các thanh gỗ từ j → n mới bị cưa) → Tổng số mét gỗ thu được là S = (a[j] - k) + (a[j + 1] - k) + (a[j + 2] - k) + … + (a[n] - k) = (a[j] + a[j + 1] + … + a[n]) - k * (n - j + 1) = prefix[n] - prefix[j - 1] - k * (n - j + 1) → Nếu S >= m[i] hay prefix[n] - prefix[j - 1] - k * (n - j + 1) >= m[i] thì return true, ngược lại return false

Minitest 16/12/2025 Chuyển cỏ Để tất cả các bó cỏ bằng nhau → Các bó cỏ cần được thêm / bớt sao cho đạt được giá trị trung bình của tất cả các bó cỏ Thuật toán: Tính trung bình cộng của tất cả các bó cỏ ban đầu, gọi là k → Đáp án chính là tổng của tất cả các (k - a[i]) với tất cả các a[i] < k (các bó cỏ thừa ra sẽ bù vào các bó bị thiếu này)

Chơi bóng chày Để ý thấy n <= 1000 → Ta có thể nghĩ cách có độ phức tạp O(n ^ 2) Thực chất đề bài yêu cầu ta đếm số bộ ba i, j, k sao cho: • a[i] < a[j] < a[k] (1) • 2 * (a[j] - a[i]) >= a[k] - a[j] >= a[j] - a[i] → a[j] + 2 * (a[j] - a[i]) >= a[k] >= a[j] + (a[j] - a[i]) (2) → Đến đây ta đã ra được cách để làm đó là for 2 vòng để cố định i, j sau đó đếm số lượng chỉ số k thỏa mãn điều kiện trên là được Cách code: sort lại mảng để xử lí điều kiện (1) for(i = 1 → n) for(j = 1 → n) { cnt = số lượng k thỏa mãn điều kiện (2) (Sử dụng chặt nhị phân để tính cnt) ans += cnt } cout << ans

Gợi ý thêm đoạn chặt nhị phân: Ta biết k có 2 tính chất:

1. a[k] >= a[j] + (a[j] - a[i])
2. a[k] <= a[j] + 2 * (a[j] - a[i]) → Ta chặt nhị phân để tìm vị trí k đầu tiên thỏa mãn tính chất 1 và vị trí k cuối cùng thỏa mãn tính chất 2 → Tất cả những vị trí trong khoảng giữa 2 vị trí vừa tìm được ở trên chính là những k thỏa mãn

Sách Thuật toán: Sử dụng kĩ thuật 2 con trỏ để tìm ra đoạn ngắn nhất chứa m loại sách khác nhau: • Duy trì 1 biến cnt là số loại sách khác nhau trong đoạn đang xét • Sử dụng 1 mảng đánh dấu để lưu số lần xuất hiện của mỗi loại sách trong đoạn hiện tại • Dùng 2 con trỏ i, j để làm điểm bắt đầu và kết thúc của đoạn • Ban đầu i = 1, j = 1 Bước 1: Mở rộng đoạn về bên phải • Tăng dần con trỏ j để mở rộng đoạn • Khi xét quyển sách thứ j: • Tăng số lần xuất hiện của loại sách đó lên 1 • Nếu đây là lần đầu tiên loại sách này xuất hiện trong đoạn → tăng cnt lên 1 Bước 2: Khi đoạn đã chứa đủ m loại sách (cnt = m) • Tính độ dài quãng đường bằng j - i + 1 • Ta thu hẹp dần phạm vi đoạn đang xét bằng cách tăng con trỏ i lên cho đến khi cnt != m • Với mỗi lần thu hẹp: • Tăng i lên để thu hẹp đoạn • Giảm số lần xuất hiện của loại sachs a[i], nếu số lần xuất hiện của nó trở về 0 → giảm cnt đi 1 (do ta vừa mất đi 1 loại sách) • Dừng thu hẹp khi cnt != m • Tiếp tục làm tiếp bước 1 → Đáp án chính là đoạn ngắn nhất chứa đủ m loại sách (đoạn j - i + 1 nhỏ nhất khi cnt = m)

Băng giấy (Băng số) Thuật toán: Với các bài có dạng hình tròn như này, cách làm đơn giản của ta là gấp đôi string s lên Duyệt lần lượt các vị trí từ 1 → n của s, tại mỗi vị trí, ta rút ra 1 string n phần từ (dùng lệnh substr) rồi tìm xem string ở vị trí nào là lớn nhất thì lưu lại làm đáp án Lưu ý: các vị trí bắt đầu từ 1, không phải từ 0 như mọi khi (do đề bảo), và nếu có nhiều vị trí phải in ra vị trí nhỏ nhất

Trò chơi blackjack Lại thấy n <= 1e4 → Ta nghĩ cách làm sao để dùng thuật toán có độ phức tạp O(n^2) Thực chất đề bài yêu cầu ta tìm bộ ba số i, j, k sao cho: • a[i] + a[j] + a[k] là lớn nhất có thể • a[i] + a[j] + a[k] <= m → a[k] <= m - a[i] - a[j] → Nếu cố định i việc còn lại của ta là tìm j, k sao cho a[j] + a[k] là lớn nhất mà a[j] + a[k] <= m - a[i] → Đến đây ta đã ra được cách để chạy được O(n^2) đó là cố định i lại sau đó tìm cặp a[j] + a[k] lớn nhất thỏa mãn điều kiện

Cách code: for(i = 1 → n) { tmp = max(các cặp (a[j] + a[k]) <= m - a[i]) (tìm tmp tốt nhất bằng kĩ thuật 2 con trỏ) ans = max(ans, a[i] + a[j] + a[k]) }

Nói thêm về cách dùng 2 con trỏ để tìm cặp a[j] + a[k] tốt nhất: • Trước tiên ta nên sort lại mảng để có tính chất tăng dần • Đặt j = i + 1, k = n • Nếu a[j] + a[k] > m - a[i] → giảm k xuống • Nếu a[j] + a[k] <= m - a[i]: • Cập nhật tmp = max(tmp, a[j] + a[k]) • Tăng j lên để thử xem có cặp tối ưu hơn không

Ngày 16/12/2025: Bài Đua Ngựa: Ước chung lớn nhất

                l               r

p[i] = UCLN(a[1], …, a[i]) s[i] = UCLN(a[i], …a[n]) p[1] = a[1]; for(i = 2-> n) p[i] = _gcd(p[i - 1], a[i]); s[n] = a[n]; for(i = n - 1-> 1) s[i] = _gcd(s[i + 1], a[i]); KHi bỏ đi đoạn [l ,r] ta chỉ cần in ra: GCD(p[l - 1], s[r + 1]) • Khi bỏ đi đoạn [l, r] thì việc cần làm là đáp án ta cần tìm chính là gcd(gcd(1…l - 1), gcd(r + 1…n)) → Sử dụng ý tưởng tương tự kĩ thuật max dồn để làm thành kĩ thuật gcd dồn • Tạo ra 2 mảng prefixgcd[i] và suffixgcd[i] với ý nghĩa • prefixgcd[i]: gcd của các số từ [1, i] → prefixgcd[i] = gcd(prefixgcd[i - 1], a[i]) • suffixgcd[i]: gcd của các số từ [i, n] → suffixgcd[i] = gcd(suffixgcd[i + 1], a[i]) → Khi bỏ đi đoạn [l, r] thì đáp án ta cần tìm chính là gcd(prefixgcd[l - 1], suffixgcd[r + 1])

Ngày 9/12/2025: Hai con trỏ Hai con trỏ: là 1 kĩ thuật lập trình sử dụng hai biến trỏ vào hai vị trí khác nhau trên mảng 1 chiều.

Hái nấm i 1 i j i n a 1 0 1 1 1 1 1 0 1 1 1 s x j j j j j
Hái nấm ở 1 đoạn liên tiếp gồm toàn số 1 (vị trí có nấm) (nếu vị trí i có nấm a[i]= 1. Đoạn từ i -> j gồm toàn số 1 khi vào chỉ khi tổng của tất cả các phần tử trong đoạn này = độ dài đoạn s[0] = 0 s[1] = a[1] = s[0] + a[1] s[2] = a[1] + a[2] = s[1] + a[2] s[3] = a[1] + a[2] + a[3] = s[2] + a[3] s[4] = a[1] + a[2] + a[3] + a[4] = s[3] + a[4] … s[i] = s[ i - 1] + a[i]

s[0] = 0; for(i = 1-> n) s[i] = s[i - 1] + a[i];

Tìm 1 đoạn con dài nhất chỉ gồm các số 1 res = 0; for(i = 1-> n) for(j = i -> n) sum = s[j] - s[i - 1]; if(sum == j - i + 1) res = max(res, j - i + 1);

Cải tiến: Bài Chạy tiếp sức:

x       x           x       x       x       x
gậy

khi chạy sang bên phải người cầm gậy có hai lựa chọn:

1. Chạy tiếp sang phải
2. trao gậy cho người đứng ở vị trí đó để người đó chạy sang phải v = a[1]; s = a[1]; for(i = 2-> n - 1) { v = min(v, a[i]); s += v;///tổng thời gian để mang gậy về đích } Bài Trang trí: Chọn 1 đoạn con liên tiếp có độ dài chẵn sao cho tổng lớn nhất Để tính tổng các giá trị từ i -> j: s[j] - s[i - 1] x y x y x y x jy y

s[j] - s[0] = tổng đoạn từ a[1] -> a[j] s[j] - s[1] = tổng đoạn từ a[1] -> a[2] Tìm 1 đoạn có tổng lớn nhất: for(j = 1-> n) { for(i = 1-> j)//đoạn từ i -> j { sum = s[j] - s[i- 1]; if((j - i + 1)% 2 == 0 and res < sum) res = sum; } } CẢI TIẾN: tại 1 vị trí j ta sẽ tìm các vị trí i (cùng tính chất chẵn lẻ với j) max(s[j] - s[j - 2],s[j] - s[j - 4], s[j] - s[j - 6]...) …. và tìm max để tìm được max: s[j] - min(s[j - 2], s[j - 4], …s[j - 2k]) gọi p[i] = min(s[i], s[i - 2], s[i - 4]...) p[1] = s[1], p[2] = s[2] for(i = 1 -> n) p[i] = min(p[i - 2], s[i]); res = LLONG_MIN; for(i = 2-> n) res = max(res, s[i] - p[i - 2]); Bài ĐUA NGỰA sắp xếp các con ngựa của TT tăng dần theo sức mạnh sắp xếp các con ngựa của nhà Vua tăng dần theo sức mạnh:

i 1 2 3 4 5 6 n vua i na TT j j nb

Nếu: con ngựa khỏe nhất TT[nb] > vua[na] -> đấu luôn wTT++; na–, nb– Nếu con ngựa yếu nhất của TT thắng được con ngựa yếu nhất của vua - đấu luôn: wTT++; i++, j++; Ngược lại: cho con yếu nhất của TT đấu con khỏe nhất của vua: nếu con ngựa TT[j] < vua[na]: wVua++; j++, na–; Bài Chia dãy:

Tìm 1 đoạn con có tổng chia hết cho d: Thuật trâu: cnt = 0; for(i = 1-> n) for(j = i -> n) sum = s[j] - s[i - 1]; if(sum % d == 0) cnt++; cout << cnt; Cải tiến: Nhận xét: Đoạn con từ i đến j chia hết cho d khi và chỉ khi s[j] và s[i - 1] đồng dư s[j] % d == s[i - 1] % d Vậy ta tính lại mảng s: thay vì lưu mảng s ta lưu lại phần dư của mỗi phần tử cho d s[0] = 0; for(i = 1-> n) s[i] = (s[i - 1] + a[i]) % d; Ví dụ: 4 6 2 1 2 1 4 1 i 0 1 2 3 4 5 6 a 1 2 1 2 4 1 s 0 1 3 0 2 2 3 i -> j chia hết cho d khi và chỉ khi s[j] == s[i - 1] 1 2 1 1 2 4 1 4 -> sắp xếp các giá trị của s tăng dần để đưa các giá trị bằng nhau về cạnh nhau 1 1 1 2 2 2 2 3 3 3 9 1: 3 * 2/2 = 3 2: 4 * 3/2 = 6 3: 3 3 + 6 + 3 = 12 Đoạn con có tổng bằng 0: Trâu: \Tính mảng cộng dồn s sau đó xét mọi đoạn con: res = -1; for(i = 1-> n) for(j = i -> n) if(s[j] - s[i - 1] == 0) res = max(res, j - i + 1); Để đoạn từ i -> j có tổng = 0:s[j] - s[i - 1] == 0 -> s[j] = s[i - 1] -> SX mảng s tăng dần để đưa các giá trị bằng nhau về cạnh nhau. ta tìm hai chỉ số của các giá trị bằng nhau mà xa nhau nhất để được độ dài là dài nhất -> Ta phải lưu trữ thêm chỉ số cũ (vì nếu sắp xếp thì chỉ số bị thay đổi) 9 2 7 5 -3 -2 4 -9 -2 1

i 0 1 2 3 4 5 6 7 8 9 a 2 7 5 -3 -2 4 -9 -2 1 s 0 2 9 14 11 9 13 4 2 3 s’ 0 2 2 2 2 9 9 11 13 14 0 1 8 9 11 2 5 4 6 3

Cách 2 (anh Long): sử dụng map để lưu chỉ số của tổng tạo được trong quá trình tính: Cho mảng a, tìm đoạn con dài nhất có tổng bằng 0 → Tìm 2 chỉ số l, r xa nhau nhất sao cho a[l] + a[l + 1] + … + a[r] = 0 Ý tưởng: tạo mảng prefix → Bài toán trở thành: Tìm 2 chỉ số l, r xa nhau nhất sao cho prefix[r] - prefix[l - 1] = 0 → prefix[r] = prefix[l - 1] → Với mỗi r, ta tìm chỉ số l xa nhất sao cho prefix[r] = prefix[l - 1] Ý tưởng: Tạo 1 mảng đánh dấu để lưu lại vị trí xuất hiện đầu tiên của mỗi giá trị prefix[i] → Mỗi khi ta duyệt đến một vị trí j bất kì, ta chỉ cần so sánh nó với vị trí đầu tiên xuất hiện prefix[j] (vì so sánh với vị trí đầu tiên luôn là vị trí xa nhất)

Triển lãm tranh Trước đây khi làm bài tích lớn nhất giữa 2 số, ta có tích lớn nhất = max(tích 2 số lớn nhất, tích 2 số nhỏ nhất) → Tương tự, tích lớn nhất giữa 2 dãy chính là max(tích 2 dãy lớn nhất, tích 2 dãy nhỏ nhất) Vậy chia dãy như nào ? • Giả sử ta chia dãy thành 2 nửa, 1 nửa từ [1, i], 1 nửa từ [i + 1, n] (i bất kì) Gọi: • p là tổng của dãy con có tổng lớn nhất của nửa đầu • q là tổng của dãy con có tổng lớn nhất của nửa sau • x là tổng của dãy con có tổng nhỏ nhất của nửa đầu • y là tổng của dãy con có tổng nhỏ nhất của nửa sau → Tích lớn nhất trong phép chia này là max(p * q, x * y) → Công việc của ta là tìm cách chia dãy (chọn điểm chia i) tốt nhất sao cho tích lớn nhất trong phép chia đó là tốt nhất → Việc đơn giản là thử tất cả các vị trí i từ 1 → n để xem xem chia ở điểm nào là ngon nhất

Vấn đề đặt ra: Tìm tổng lớn nhất / nhỏ nhất của nửa đầu / nửa sau kiểu gì ?

Để tìm tổng lớn nhất của nửa đầu: Áp dụng thuật toán bài đoạn con có tổng lớn nhất để tính k = tổng đoạn con có tổng lớn nhất kết thúc ở i → tính k bằng chính ý tưởng bài đoạn con có tổng lớn nhất Tạo mảng prefixmax[i]: tổng của dãy con có tổng lớn nhất trong khoảng [1, i] → prefixmax[i] = max(prefixmax[i - 1], k)) Làm tương tự để tính các mảng prefixmin, suffixmax, suffixmin

→ Tổng kết: sau khi tính được 4 mảng prefix/suffix trên, việc còn lại của ta là thử tất cả các vị trí i từ 1 → n để xem xem chia ở điểm nào là ngon nhất for(int i = 1; i <= n; i++) { ll p = prefixmax[i] * suffixmax[i + 1]; ll q = prefixmin[i] * suffixmin[i + 1]; ans = max({ans, p, q}); }

Điền số Nhận xét: Có những vị trí ta có thể sử dụng lệnh fill cũ để “kéo dài ra” đến nó Ở đây ta sẽ quy ước 2 khái niệm: • Giá trị “mở”: giá trị không bị chặn bởi 2 giá trị nhỏ hơn bên cạnh nó • Giá trị “đóng”: giá trị bị chặn bởi giá trị nhỏ hơn đằng sau nó • Ví dụ: 2 3 2 → 3 là giá trị “đóng” Vậy khi nào ta cần lệnh fill mới ? • Nếu giá trị a[i] lớn hơn các giá trị đang “mở” trước đó → bắt buộc phải tạo một lệnh fill mới với giá trị a[i] • Nếu a[i] bằng một giá trị đã xuất hiện trước đó → có thể kéo dài lệnh fill cũ, không cần lệnh mới

Thuật toán: • Sử dụng 1 stack để lưu lại các giá trị fill đang “mở” • Mỗi phần tử trong stack là một giá trị đã được fill nhưng chưa “đóng” • Ban đầu trong stack chứa giá trị 0 (vì ban đầu cả dãy bằng 0) • Duyệt lần lượt các phần tử từ a[1] → a[n] • Khi duyệt đến một phần tử a[i], xóa hết giá trị stack.top > a[i] (vì các giá trị đó bị “đóng” bởi a[i]) • Nếu stack.top = a[i] → Ok đi tiếp đến phần tử a[i + 1] vì ta có thể coi như ta mở rộng lệnh fill trước đó đến điểm i vừa xét • Nếu stack.top < a[i] → Cần 1 lệnh fill mới với giá trị bằng a[i] → ans++, stack.push(a[i])

Tráo bài (Shuffle) Ở bài này ta sẽ sử dụng kĩ thuật link list: • Tạo 2 mảng before[i], after[i]: Lưu phần tử đứng liền trước, liền sau của giá trị i • Ban đầu before[i] = i - 1, after[i] = i + 1 với mọi i Ví dụ: dãy ban đầu là 1 2 3 4 5 thì before[3] = 2, after[3] = 4, before[4] = 3, after[4] = 5 • Với mỗi truy vấn x, y: tráo y lên trước x thì mối quan hệ của các số thay đổi như thế nào ? • Ta chia việc tráo đó thành 2 công đoạn: Công đoạn 1: Rút y ra → Nối 2 phần tử bên cạnh y ban đầu lại với nhau • before[after[y]] = before[y] • after[before[y]] = after[y] Công đoạn 2: Nhét y vào trước x → y sẽ nằm giữa x và before[x] • after[before[x]] = y • before[y] = before[x] • after[y] = x • before[x] = y Coi 0 là mốc, phần tử nào đứng sau 0 (after[0]) sẽ là phần tử đầu tiên của dãy Sau khi thực hiện tất cả các truy vấn, việc còn lại của ta đơn giản là in ra dãy bắt đầu từ phần tử after[0] và các phần tử kế tiếp của nó

int x = after[0] for(int i = 1; i <= n; i++) { cout << x; x = after[x]; }

Phát quà Yêu cầu: Tìm số 𝑥 nhỏ nhất sao cho tồn tại phương án Cám chọn quà mà Tấm không thể có cách chọn được tổng giá trị quà lớn hơn x → Tìm giá trị quà lớn nhất Tấm có thể chọn nếu Cám chọn tối ưu

Thuật toán: Ta cho Cám chọn thử hết tất cả các cách có thể rồi tìm xem trong các cách chọn đó thì cách nào làm cho giá trị lớn nhất Tấm có thể chọn là nhỏ nhất

• Giả sử Cám chọn điểm xuất phát là i → dãy Cám chọn là [i, i + k - 1] → Tấm chỉ có thể lấy được quà ở 1 trong 2 vùng [1, i - 1] và [i + k, n] Mà ta cần tìm giá trị quà lớn nhất Tấm có thể chọn → Nghĩa là ta cần dãy độ dài k có giá trị lớn nhất trong 2 dãy [1, i - 1] và [i + k, n]

• Gọi p là dãy độ dài k có giá trị max trong dãy [1, i-1], q là dãy độ dài k có giá trị max trong dãy [i + k, n] → Giá trị lớn nhất Tấm có thể chọn chính là max(p,q) Vậy tính p như nào ? • Nhận xét: Giả sử món quà đầu tiên (điểm xuất phát) mà Tấm chọn có chỉ số là i → món quà cuối cùng Tấm chọn chính là i + k - 1 và tổng giá trị dãy quà đó là prefix[i + k - 1] - prefix[i - 1] → Ta tìm p bằng cách duyệt hết điểm xuất phát có thể trong đoạn [1, i - 1] và lấy max của tất cả (prefix[i + k - 1] - prefix[i]) Chú ý: vì dãy có độ dài k nên điểm xuất phát có thể chỉ có thể là các vị trí trong khoảng [1, i - k] → Tuy nhiên duyệt như thế sẽ mất thời gian Cải tiến: sử dụng kĩ thuật max dồn: • Gọi l[i] là giá trị của dãy quà nếu điểm xuất phát Tấm chọn là i → l[i] = prefix[i + k - 1] - prefix[i - 1] • Thay vì duyệt để tìm l[i] lớn nhất thì ta sẽ duy trì 1 mảng prefixmaxleft[i]: giá trị l[i] lớn nhất có thể tính đến vị trí i → prefixmaxleft[i] = max(prefixmaxleft[i - 1], l[i]) Vậy p chính là prefixmaxleft[i - k] Làm tương tự để tìm q → Giá trị lớn nhất Tấm có thể chọn trong trường hợp Cám chọn điểm xuất phát là i chính là max(p,q) → Làm tương tự với tất cả các điểm xuất phát Cám có thể chọn và tìm min của chúng

Ngày 2/12/2025: Luyện tập Bài 1. Tự làm Bài 2. Tự làm Bài 3. Đếm dãy: Đáp án: 2^(n-1) n = 1

1. 1 n = 2
2. 1 + 1
3. 2 n = 3
4. 1 + 1 + 1
5. 1 + 2
6. 2 + 1
7. 3 n = 4
8. 1 + 1 + 1 + 1
9. 1 + 1 + 2
10. 1 + 2 + 1
11. 1 + 3
12. 2 + 1 + 1
13. 2 + 2
14. 3 + 1
15. 4 Chứng minh: Cách chứng minh của Vĩnh Khang: gsử ban đầu có n nhóm gồm 1 số 1, và giữa mỗi nhóm có một khe hở để mà đặt vách ngăn(n-1 khe), thì mỗi vách ngăn có 2 trạng thái là đặt hoặc không đặt, nên số cách là 2^(n-1). Đáp số: 2^(n-1) -> bài toán quy về việc tính 2^(n-1)% 123456789 long long P = 1; m = 123456789; for(i = 1-> n) P = P * 2 % m; Hàm tính lũy thừa nhanh Bài 4: Lời giải có trong slide cô gửi trên nhóm

Bài 5: (Hải Long) gọi x là số băng dán cần mua => tổng nhãn = x * m tổng nhãn đem đi chia => có n bạn, mỗi bạn ít nhất y cái, y>=1; có k bạn nhận thêm 1 cái nữa => tổng phát = ny+k => xm = ny+k => có 2 đk tìm x đk 1: xm >=n+k => x>=[(n+k)/m] với cái [] là làm tròn(nguyên) đk2: ny = xm-k => y là số nguyên => xm -k chia hết n hay xm đồng dư k mod n đoạn 3 thì ktra vô nghiệm, từ ptrinh mod kia thì chỉ có nghiệm nếu k chia hết cho ucln m,n g = gcd m,n k%g khác 0 in ra -1 để tìm x, chia cả 2 vế cho m, chia m,n,k cho g để có m', n',k' dùng eculid mở rộng tìm nghịch đảo m' qua mod n' tìm nghiệm cơ sở xbase, đây là x nhỏ nhất tman chia hết so sánh xb với giá trị tối thiểu cần mua nếu xb nhỏ quá => công them n' vào, cho tới khi đủ lớn hay bằng mưacs tối thiểu [(n+k)/m] chỉ khó ở đoạn euclid mở rộng thôi Stickers Ngày 25/11/2025: Luyện tập kĩ thuật lập trình Bài 1. Bài cho điểm Bài 2. Dữ kiện 1: a và b là hai số nguyên ko âm. long long x[5]; -> trong 4 số x[0], x[1], x[2], x[3], x[4] thì số lớn nhất sẽ là a + b sort(x + 1, x + 5) b = (x[1] + x[2] + x[3])/2 -> b nguyên khi (a1 + a2 + a3)%2 -> từ đó tính được a = x[4] - b Bài 3. Tìm số. Mấy bài dễ không biết làm đánh đít nhé

Bài 4: Tích lớn nhất Tích lớn nhất khi hai số đó là số nguyên dương lớn nhất hoặc là hai số nguyên âm nhỏ nhất.

• 100 -99 2 3 Tìm số lớn nhất, lớn nhì, nhỏ nhất nhỏ nhì và so sánh hai tích tìm được Bài ODOOR: 3 T = 0 2 2 1 2 2 3 đáp án là 5: cửa số 1 ở giây thứ 2: mở và lấy chìa khóa. cửa số 2: 1, 3, 5, 7, 9.. (s[2] + d[i] * k) cửa số 3: 2, 5, 8, 11,
  Gọi T là thời điểm để mở cánh cửa thứ i: T = 0; for(i = 1-> n) { nếu (T <= s[i]) -> T = s[i] ngược lại: Cần tìm 1 thời điểm: s[i] + x * d[i] >= T x = ceil(T - s[i])/d[i]) T = s[i] + x * d[i]

}

Giá trị khác nhau Bài này dễ quá rồi:) Bài Đa thức: Ta xét lần lượt p(x) khi thêm các hệ số a[i]: Thêm a[0]: p(x) += a[0] * x ^ 0 Thêm a[1]: p(x) += a[1] * x ^ 1 Thêm a[2]: p(x) += a[2] * x ^ 2 … Thêm a[n]: p(x) += a[n] * x ^ n → Thuật toán: Duyệt tất cả các a[i], mỗi khi duyệt đến một i bất kì thì ta cho p(x) += a[i] * x ^ i Lưu ý: Nhớ mod ở tất cả các bước để tránh tràn số

Trộn dãy Để nối 2 dãy a, b, ta có thể gấp đôi kích thước tối đa của dãy a lên sau đó thêm lần lượt các phần tử của dãy b vào “đuôi” của dãy a Ví dụ, thông thường ta khai báo mảng a[100005] thì giờ ta sẽ khai báo thêm thành a[200005] (để có đủ dung lượng chứa thêm dãy b) Sau đó ta chỉ việc gán các giá trị a[n + 1], a[n + 2] , … a[n + m] = các giá trị trong dãy b là đã trộn được 2 dãy vào với nhau: for(int i = n + 1; i <= n + m; i++) { a[i] = b[i - n]; } Việc còn lại chỉ là sort lại dãy a và in ra kết quả

Đua rô bot Nhận xét: Xe i vượt xe j khi: • j < i • Thời gian về đích của xe i < Thời gian về đích của xe j Với mỗi xe i: tính được thời gian về đích của mỗi xe Quãng đường: d, vận tốc là v[i], thời điểm xuất phát là i -> thời điểm về đích của xe i: i + d/v[i] < j + d/v[j] thì xe i vượt xe j. sử dụng 1 vector để lưu thời điểm về đích của mỗi xe: t[i] = i + d/v[i] xe i vượt xe j: j < i và t[i] < t[j]. Trung bình cộng (Averin) Trung bình cộng của dãy (i, j) = (a[i] + a[i + 1] + … + a[j]) / (j - i + 1) → Đề bảo gì làm nấy, ta xét tất cả các đoạn (i, j) và kiểm tra xem trong đoạn đó có giá trị k nào bằng trung bình cộng của dãy không

    i       j

Cải tiến: Để kiểm tra trong đoạn (i, j) có giá trị k nào không nhanh ta có thể sử dụng kĩ thuật mảng đánh dấu Dãy số nguyên liên tiếp dài nhất

0 1 2 3 4 5 6 7 8 9 10 11 10^6 x x x x x x x x x

• Dãy a là dãy số nguyên không âm đôi một phân biệt => có tối đa 1 số 0 • Vì dãy số nguyên liên tiếp này ta xét trên tập giá trị nên ta dùng mảng cnt để đếm xem mỗi giá trị xuất hiện chưa • cnti số lần xuất hiện của giá trị i có trong mảng a • Xét trên tập giá trị thì ta sẽ đếm được độ dài dãy liên tiếp dài nhất • Có thể thay 1 số nếu cnt0=1 => giá trị bị thiếu giữa 2 đoạn giá trị liên tiếp • a = [0, 1, 2, 3, 5 ,6, 7] => cnt = [1, 1, 1, 1, 0, 1, 1, 1] • Ta xét 2 trường hợp riêng biệt là có thay không thay • Trường hợp không thay số 0 thì đơn giản là ta duy trì 1 biến len là độ dài giá trị liên tiếp dài nhất cho đến đến giá trị hiện tại • cnti=1, len = len + 1 • cnti=1, len=0
+ Trường hợp có thể thay số 0: + Cố gắng tối đa độ dài của 2 dãy giá trị liên tiếp + Ta duy trì thêm 1 biến pre là độ dài giá trị liên tiếp dài nhất ngay phía trước (thiếu không quá 1 giá trị) + cnti=1, len += 1 + cnti=0, pre=len, len=0 •
Rải sỏi • Suy nghĩ đơn giản: for trâu từ điểm x, đi từng ô 1 và tăng giá trị lần lượt => chậm Cải tiến: sử dụng mảng cộng dồn: muốn tăng 1 đoạn từ a[l] đến a[r] lên 1 đơn vị, ta tăng mảng cộng dồn tương ứng b[l] lên 1 và b[r + 1] giảm 1:

0   1   2   3   4   5   6   7   8

a +1 +1 +1 +1 +1
b +1 -1
Ví dụ tăng từ a[2] đến a[6] lên 1 đơn vị, ta tăng b[2] lên 1, giảm b[6] đi 1 => áp dụng vào đường tròn: Ta chia làm 3 trường hợp • TH1: đi hết 1 vòng: tăng b[0] lên 1, không giảm ở đâu cả => cả vòng tăng • TH2: đi trong vòng (ví dụ đi từ điểm 2 -> 6), làm như ví dụ trên • TH3: đi vượt vòng (ví dụ đi từ điểm 7 về điểm 3): ta cắt đôi ra rồi tăng như bình thường(ta tăng từ 7->8 rồi tăng từ 0 -> 3) Code tham khảo: Số tầng Số phòng từ tầng cao nhất tới hết tầng thứ m trong tòa n tầng là 1+2+....+ (n-m+1) Đặt h = n-m+1 => 1+2+..+h = h(h+1)/2 Rõ ràng, nếu phòng thứ i ở tầng m thì tổng số lượng phòng từ phòng thứ i tới phòng n(n+1)/2 phải nhỏ hơn hoặc bằng h(h+1)/2 và lớn hơn (h-1)h/2 ⇒ Đặt x = số lượng phòng từ phòng thứ i tới phòng n(n+1)/2 = n(n+1)/2 - i + 1

Với ví dụ với ô số 9 ở trên, số lượng ô tô đậm là giá trị của x ⇔ h(h-1)/2 x h(h+1)/2 ⇔ h(h-1) 2x h(h+1) ⇔ h(h-1) 2x h(h+1) Lưu ý rằng các phép toán ở đây là ép kiểu xuống. Nên ta có được phương trình ⇔ h-1 2*x h ⇒ Lúc này chỉ có 2 trường hợp xảy ra là i có thể đứng ở tầng h và h-1 từ trên xuống, tức là tầng n-h+1 hoặc n-(h-1)+1 ⇒ Kiểm tra lại điều kiện để xác định Code mẫu:

Ngày 18/11/2025: Khởi động đường dài Bài 1. Đếm cặp: a = 1, b <= N/a đều có tích <= N: N - 1 + 1số a = 2, b<=N/2 đều có tích <= N: 2-> N/2:N/2 - 2 + 1 số a = 3: b <= N/3 đều tạo ra tích <=N:N/3 - 3 + 1 2 3 4 a <= b a * b <= N -> a <= sqrt(N). res = 0; for(a = 1-> sqrt(N)) { b = N/a; res += b - a + 1; } Bài 2: T = (a * b * c ..x …)% x = 0 vì đây là 1 phép chia hết
T = 2 * 3 * 5 % 15 = 0 Nếu n >= m -> KQ = 0. res = 1; for(i = 2-> N) res = res * i % m; cout << res; Bài 3. 𝑎𝑖+𝑎𝑖+1+⋯+𝑎𝑗≤𝑀
Cần tính tổng cộng dồn. Khi đó, 𝑎𝑖+𝑎𝑖+1+⋯+𝑎𝑗 = s[j] - s[i - 1] ≤𝑀
Trâu: cnt = 0; for i = 1-> n for(j = i ->n) nếu (s[j] - s[i -1]<= M) cnt++; Nhận xét: Vì các giá trị a[i] > 0, với mỗi giá trị i thì khi j càng tăng thì s[j] - s[i] càng tăng (không giảm) M = 7 i j j 1 2 1 1 1 2 3 2 3 1 1 2
Sử dụng thuật toán hai con trỏ: từ i….j mà s[j] - s[i] > M thì tất cả các điểm dừng j1 trước j đều cho ta tổng <= M res += j - i Bài 4. D: Khi M càng tăng thì số đoạn con càng nhiều Đếm số lượng đoạn con có tổng <= 5 Đếm số lượng đoạn con có tổng <= 10 Ta đang cần tìm giá M để dãy ban đầu có đúng k đoạn con đẹp: -> chặt nhị phân đáp án: l = 1, r = n * (n + 1)/2; while(l <= r) { M = (l + r)/2; if(baiC(M) < k) l = M + 1; else r = M - 1; }

Bài E: Nhận xét: • Với măng đá có độ cao là x thì sẽ gây cản trở cho đom đóm nếu bay ở độ cao [1, x] • Với nhũ đá có độ cao là x thì sẽ cản trở những con đom đóm bay ở độ cao [H - x + 1, H] → Nếu con đom đóm bay ở vị trí x, nó sẽ va phải những măng đá có độ cao [x, H] và nhũ đá có độ cao [H - x + 1, H] → Ta có thể đếm xem ở mỗi vị trí i thì con đom đóm sẽ va phải bao nhiêu măng đá và nhũ đá bằng kĩ thuật mảng cộng dồn Tạo 2 mảng cnt để lưu lại độ cao của các măng đá và nhũ đá (tính từ dưới lên) • Số lượng măng đá ở vị trí x chính là số lượng măng đá có độ cao >= x (Tính được bằng mảng cộng dồn) • Số lượng nhũ đá ở vị trí x chính là số lượng nhũ đá có độ cao <= x Tính xong thì ta chỉ cần lấy độ cao mà nó phải vượt ít chướng ngại vật nhất

Bài F Ta sắp xếp hai mảng theo thứ tự tăng dần và sử dụng thuật tham lam như sau để đếm số cặp thắng lớn nhất • Duyệt từng học sinh của các trường khác từ bé đến lớn ta tìm học sinh yếu nhất của bên ta mà thắng được ta cho thắng luôn vì để dành các học sinh mạnh hơn cho các đối thủ mạnh hơn nhằm tối đa số cặp thắng • Cách code: Sử dụng 2 con trỏ, duy trì chỉ số i, j lần lượt là học sinh yếu nhất của đội khách chưa ra sân, học sinh đội chủ nhà hiện tại là học sinh yếu nhất chưa ra sân nếu học sinh bj>ai thì cho đấu luôn và tăng i, j lên 1 ngược lại tăng j lên 1 vì dãy được sắp xếp tăng dần nên bj không thắng được ai thì cũng không thắng được ai cả

Bài G • Ta sẽ chặt nhị phân số kẹo tối đa mà mỗi học sinh có thể nhận tạm gọi là mid • Để kiểm tra xem tồn tại cách chia mà mỗi học sinh không quá mid ta chia tham lam mỗi loại kẹo cho ít học sinh nhất có thể mà tổng số học sinh nhận kẹo không quá n thì là hợp lệ • Mỗi loại kẹo i gồm ai sẽ phải chia cho tối thiểu ai/mid (làm tròn lên) học sinh (vì phải chia hết số kẹo). Vậy là tổng số học sinh ít nhất để chia hết kẹo sẽ là tổng của biểu thức trên với mỗi loại kẹo. → nếu tổng đó > n thì hàm check = false, ngược lại thì mid là 1 cách chia thỏa mãn, check = true

Bài H • Bài này có một nhận xét quan trọng như sau nếu hai hình chữ nhất i, j mà hi>= hj, wi >=wj thì hình chữ nhật i chứa hình chữ nhật j nên chỉ cần tính diện tích hình chữ nhật i là đủ. • Ta sẽ sắp xếp hình chữ nhất theo thứ tự giảm dần của h tức i<j thì hi>hjthì hình chữ nhật j chỉ lòi ra so với i hình chữ nhật trước đó nếu wj >max(wi) và phần lòi ra của hình chữ nhật j so với các hình chữ nhất i trước đó chính là hj(wj-max(wi)) (vì nếu wj<= max(wi) thì hình chữ nhật j sẽ bị bao trọn bởi các hình chữ nhật trước đó) với max(wi) là wi lớn nhất của các hình chữ nhất i trước đó • Để tính max(wi) nhanh chóng thì ta chỉ việc duy trì biến mx chính là max(wi) mỗi lần ta chỉ việc cập nhất mx = max(mx, wi) → Cách code: Ta tính trước diện tích hình chữ nhật w[1]h[1] (sau khi sort giảm dần) sau đó cộng thêm với phần dư của mỗi hình chữ nhật lòi ra sau đó ( các hình chữ nhật có wj >max(wi)) một khoảng bằng hj*(wj-max(wi))

Bài I • Gọi mảng dồn theo phần dư với d của dãy a là sum tức sumi=(sumi-1+ai)%d • Thì để một đoạn con liên tiếp từ [l, r] chia hết cho d thì sumr-suml-1 =0 hay sumr=suml-1 • Hay bài toán bây giờ của ta là đếm số cặp giá trị bằng nhau trên mảng sum. Việc này có thể dễ dàng làm được bằng cách sắp xếp lại mảng sum dần đếm số lượng các phần tử bằng nhau liên tiếp.

Ném trứng (gợi ý) • Gọi dpi,jlà số lần thử tối thiểu nếu ta cần kiếm tra toà nhà có i tầng và trong tay có j quả trứng

Đếm dãy con Nhận xét: Bài toán về tổng dãy con → Nghĩ đến prefixsum Ta cần đếm số cặp i, j sao cho L <= prefix[j] - prefix[i - 1] <= R → Bài toán trở thành: với mỗi i, ta cần đếm số lượng chỉ số j thỏa mãn L + prefix[i] <= prefix[j] <= R + prefix[i] Gợi ý: Để tìm số lượng prefix[j] nằm trong khoảng đó, ta sử dụng tìm kiếm nhị phân Số lượng đó chính là upperbound(R + prefix[i]) - lowerbound(L + prefix[i])

Ngày 11/11/2025: Kiểm tra cuối khóa 2 Mua thức ăn Ý tưởng: Gọi p là số tiền bỏ ra để mua thức ăn loại 1 → k - p là số tiền bỏ ra để mua thức ăn loại 2 Để IQ và EQ của đàn bò bằng nhau, ta cần a + k * x = b + (k - p) * y → a - b - k * y = -p * (x + y) → p = (a - b - k * y) / (x + y) Mà ta cần p là số nguyên → Chỉ tìm được p nếu phép chia đó là phép chia hết → if((a - b - k * y) % (x + y) = 0) cout << p else cout << -1

Số đặc biệt Nhận xét: Số có số ước là lẻ chính là số chính phương Vậy bài toán đếm số đặc biệt chính là bài toán đếm số lượng số chính phương trong khoảng từ a → b Thuật trâu: for từ a đến b đếm xem có bao nhiêu số chính phương trong đó

Thuật chuẩn: Bài toán là đếm số lượng m thỏa mãn: • m là số chính phương • a <= m <= b → sqrt(a) <= sqrt(m) <= sqrt(b) Mà ta có tính chất: giữa 2 số là bình phương của 2 số nguyên liên tiếp thì không tồn tại số chính phương nào → Bài toán thực chất là đếm số số hạng trong khoảng từ ceil(sqrt(a)) (làm tròn lên) đến sqrt(b)

Đoạn con có tổng lớn nhất • Ta tạo mảng cộng dồn sum trên mảng a thì rõ ràng tổng các phần từ liên tiếp từ l đến r trong mảng a sẽ sử dụng công thức sum[r] - sum[l-1]. Giả sử ta cố định vị trí kết thúc r ta cần tìm đoạn con có tổng lớn nhất kết thúc tại r thì ta cần tham lam tìm sum[l-1] có giá trị bé nhất thì sum[r]-sum[l-1] có giá trị lớn nhất. • Và thật ra ta có thể duy trì giá trị nhỏ nhất này bằng quan sát sau: giả sử từ r chuyển sang r+1 thì giá trị min(sum[l-1]) với l <= r nhỏ nhất sẽ thay đổi như nào ? • Nó sẽ có thêm giá trị sum[r] như sau: • Tại r thì min(sum[l-1]) = min(sum[0], sum[1], ..., sum[r-1]) • Tại r+1 thì min(sum[l-1]) = min(sum[0], sum[1], ..., sum[r-1], sum[r]) • Bằng cách cố định r và duy trì giá trị min(sum[l-1]) với mỗi r, ta có thể tính đoạn con có tổng lớn nhất kết thúc tại r. Vậy với n giá trị r có thể ta lấy max mọi giá có thể thì thu được kết quả với độ phức tạp O(n)

Biến đổi xâu Cách trâu: Đề bảo gì làm nấy, với mỗi truy vấn xy ta for cả mảng để thay kí tự x = kí tự y → Quá thời gian

Thuật đúng: Ta có thể tìm trước trạng thái cuối cùng của tất cả các chữ trước, sau đó mới thay đổi trên xâu gốc Ví dụ: xm eo oa ae → x đổi thành m, e đổi thành o, o thành a, a thành e → Tổng kết: x thành m, e giữ nguyên, o và a thành e, còn các chữ cái khác không thay đổi gì Vậy làm sao để biết trạng thái cuối cùng của mỗi chữ cái ? Rất đơn giản, ta đi ngược lại, vì nếu ta đi ngược lại thì sự biến đổi của ta luôn là hướng đến trạng thái cuối cùng Ví dụ: xm eo oa ae ta đi ngược thành ae oa eo xm → a thành e, o thành a (lúc nãy đã thành e nên cũng là o thành e), e thành o (lúc này cũng đã thành e nên e vẫn là e), x thành m Vậy code như nào? Ta tạo 1 mảng change để lưu lại trạng thái cuối cùng của mỗi kí tự, mỗi khi thực hiện truy vấn xy thay vì t biến x thành y thì ta sẽ biến x thành trạng thái cuối cùng của y for(i = m; i >= 1; i--) { change[x - 'a'] = change[y - 'a']; } Biến đổi lại trên xâu s: Chuyển các kí tự thành trạng thái cuối cùng của nó for(i = 0; i < n; i++) s[i] = char(change[s[i] - ‘a’] + ‘a’)

Trung bình cộng Giả sử a[i] + a[i + 1] +...+a[j] có TBC = k: (a[i] + a[i + 1] +...+a[j])/(j - i + 1) = k (a[i] + a[i + 1] +...+a[j]) = k + k + k + k…+ k (có j - i + 1 số k) (a[i] - k) + (a[i + 1] - k) +...+ (a[j] - k) = 0 → Nếu đọc vào dãy a, lần lượt trừ a[i] = a[i] - k thì bài toán trở thành: tìm 1 đoạn con dài nhất có tổng = 0

Bài toán đoạn con có tổng bằng 0: Cho mảng a, tìm đoạn con dài nhất có tổng bằng 0 → Tìm 2 chỉ số l, r xa nhau nhất sao cho a[l] + a[l + 1] + … + a[r] = 0 Ý tưởng: tạo mảng prefix → Bài toán trở thành: Tìm 2 chỉ số l, r xa nhau nhất sao cho prefix[r] - prefix[l - 1] = 0 → prefix[r] = prefix[l - 1] → Với mỗi r, ta tìm chỉ số l xa nhất sao cho prefix[r] = prefix[l - 1] Ý tưởng: Tạo 1 mảng đánh dấu để lưu lại vị trí xuất hiện đầu tiên của mỗi giá trị prefix[i] → Mỗi khi ta duyệt đến một vị trí j bất kì, ta chỉ cần so sánh nó với vị trí đầu tiên xuất hiện prefix[j] (vì so sánh với vị trí đầu tiên luôn là vị trí xa nhất)

Chạy tiếp sức Ý tưởng: Lại là 1 bài toán với tổng dãy con liên tiếp → Tạo mảng cộng dồn prefix Bài toán yêu cầu: Tìm cách chia a thành 3 đoạn con thỏa mãn yêu cầu → Gọi 2 điểm p và q là 2 điểm chia đoạn → A chạy các đoạn từ 1 → p, B chạy từ p + 1 → q, C chạy từ q + 1 → n → Quãng đường 3 người chạy là • A: prefix[p] • B: prefix[q] - prefix[p] • C: prefix[n] - prefix[q] → Điều kiện: A <= B <= C → Bài toán trở thành: Tìm 2 điểm p và q thỏa mãn điều kiện trên sao cho p lớn nhất có thể Thuật toán: Sử dụng 2 con trỏ để tìm ra 2 điểm p và q đó Con trỏ p chạy từ 1 → n, con trỏ q sẽ chạy sao cho khớp với con trỏ p, nếu p và q thỏa mãn điều kiện thì ta cập nhật ans = max(ans, p)

Gợi ý cách code: q=1; for p = 1 → n: { while(j < n && s[q] - s[p] < s[p]) q++ //đk B >= A if(j == n) break; if(s[q] - s[p] <= s[n] - s[q]) ans = max(ans, p) //đk C >= B }

Số chính phương 2 Nhận xét: Mỗi số đều có thể viết thành dạng x = p1^a1 * p2^a2 * p3^a3 * … (tích các thừa số nguyên tố) Ý tưởng: Để i * j là số chính phương → Số mũ của tất cả các số trong phân tích nguyên tố của i * j đều phải là số chẵn Mà số mũ của các số trong i * j = số mũ của i + số mũ của j → i và j phải có cùng dạng chẵn lẻ của số mũ trong phân tích thừa số Gọi f[i] là tích các thừa số nguyên tố có số mũ lẻ của số i (nếu không có thừa số nguyên tố nào có mũ lẻ thì coi f[i] = 1) → i * j là số chính phương ⇔ f[i] = f[j] → Bài toán trở thành với mỗi i, đếm số lượng j thỏa mãn f[i] = f[j] Thuật toán: • Duyệt tất cả i từ 1 → n • Tính f[i] của mỗi số i • Sử dụng 1 mảng đếm cnt để lưu lại số lần xuất hiện của mỗi f[i] → Với mỗi f[i], ta tạo được (cnt[f[i]])^2 cặp (i,j) hợp lệ (ví dụ: với 3 số 1,4,9 đều có f[i] = 1 → cnt[f[i]] = 3 → tạo đc 3*3 = 9 cặp) → Tính tổng tất cả các (cnt[i] ^ 2) với mọi i từ 1 → n là xong (vì duyệt 1 → n là ta đã duyệt qua mọi f[i] rồi) Đường tàu (Metro) Viết hàm tính độ dài theo chiều kim đồng hồ (1) với d(s,t) là độ dài từ s⇒t theo chiều kim đồng hồ ⇒ Tính độ dài đường đi từ a⇒b (đường đi từ An tới Bình) ⇒ gọi là dab ⇒ Tính độ dài đường đi từ a⇒x (đường đi từ An tới đích của mình) ⇒ gọi là dax ⇒ Tính độ dài đường đi từ b⇒y (đường đi từ Bình tới đích của mình) ⇒ gọi là dyb (vì (1) và b⇒y là ngược chiều kim đồng hồ nên muốn tính khoảng cách từ b⇒y ta phải xét ngược lại là d(y,b)) Nếu An và Bình có thể gặp nhau, thì: TH1: An và Bình gặp nhau khi tàu An chưa vượt qua chỗ Bình và tàu Bình chưa vượt qua chỗ An (gặp nhau khi chưa lướt qua nhau) • Đồ dài đường đi giữa a⇒b phải có độ dài chẵn, nếu không thì họ không thể gặp nhau. Ví dụ: Nếu khoảng cách là 3 thì họ sẽ không thể dừng chung tại 1 ga • Độ dài đường đi từ a đến điểm gặp nhau, và b đến điểm gặp nhau phải nhỏ hơn độ dài của dax và dyb (dab/2 <= dax && dab/2 <= dyb) TH2: Gặp nhau khi lướt qua nhau 1 lượt ⇒ Lúc này dab đã tăng thêm n (do đi thêm 1 vòng) ⇒ dabn = dab+n • Độ dài dabn phải có độ dài chẵn (bởi vì giống TH1) • Độ dài đường đi từ A,B⇒ điểm gặp nhau phải nhỏ hơn độ dài của dax và dyb (dabn/2 <= dax && dabn/2 <= dyb)

Ngày 4/11/2025: Tổng ôn tập Bài 1. Nếu n là lẻ thì n chính là ước lẻ lớn nhất của nó Nếu là n chẵn, ước lớn nhất (trừ n) là n/2: nếu n/2 lẻ thì in ra n/2 ngược lại n = n/2. n = 2^x * k 32 16 8 4 2 1 -> 0 36 18 9 while(n% 2 == 0) n/=2; if(n > 1) cout << n esle cout << -1 Bài 2. Số nguyên tố đặc biệt viết hàm IsPrime(x) Viết 1 hàm sd(x) Liệt kê các snt đặc biệt trong đoạn từ l -> r: for(i = l -> r) { s = sd(i);//tổng các chữ số của i if(IsPrime(i) và IsPrime(s)) cout << i << “ ” } Làm như thế này sẽ bị TLE. Làm hạn chế các bước kiểm tra số nguyên tố. Sử dụng 1 mảng đánh dấu: d[i] = true nếu i là số nguyên tố d[i] = false nếu i không là số nguyên tố N = 1e7 + 1; fill(d, d + N, true); d[0] = d[1] = false; for(int i = 2; i <= sqrt(N); i++) if(d[i]) for(int j = i * i; j < N; j += i) d[j] = false; for(i = l -> r) { s = sd(i);//tổng các chữ số của i if(d[i] và d[s]) cout << i << “ ” } Bài 3. Tổng đoạn Sử dụng mảng cộng dồn: Mảng ban đầu luôn bắt từ a[1] -> a[n] s[0] = 0; for(i = 1-> n) s[i] = s[i - 1] + a[i]; với mỗi câu hỏi l, r: cout << s[r] - s[l - 1] << endl; Bài 4. Biến đổi (dạng bài Adhoc) Nhận xét: Vì yêu cầu tích khác 0 -> đếm xem có bao nhiêu giá trị = 0 ta phải tăng thêm 1 Nếu tổng = 0 -> ans = ans + 1. Bài trồng táo: Trâu: tính cộng dồn s:

1 i j

res = 0; sum = s[j] - s[i -1] nếu sum % 7 == 0 thì res = max(res, j - i + 1); -> TLE.

Cách cải tiến cho nhanh: Đoạn i -> j chia hết cho 7 chứng tỏ: s[j] và s[i -1] đồng dư 1 -> i -1” chia 7 dư x; 1 -> j chia 7 dư x: s[i - 1] = 7q + x s[j] = 7k + x s[j] - s[i - 1] = 7(k - q) -> KL (i -> j chia hết cho 7)’ s[0] = 0; for(i = 1->n) s[i] = (s[i -1] + a[i]) % 7.

i 0 1 2 3 4 5 6 7
a 1 2 1 3 4 4 2
s 0 1 3 4 0 4 1 3
s 0 0 1 1 3 3 4 4
5 s[i] == s[j] thì j - i là 1 đoạn chia hết chia hết cho 7

Tìm số Nhận xét Trong các số từ 1 đến x, có: • x / a số chia hết cho a • x / b số chia hết cho b Nhưng có x / lcm(a, b) số bị đếm trùng (chia hết cho cả a và b). → Ta có thể tính nhanh số lượng số là bội của ít nhất 1 trong 2 số trong khoảng từ 1 → x là: cnt(x) = x / a + x / b - x / lcm(a,b) Từ đây ta nghĩ ra ý tưởng: Chặt nhị phân để tìm số k nhỏ nhất có cnt(k) >= n

Thiên tài thiện xạ Ý tưởng: Giả sử ta đã biết trước một giá trị R, ta có thể kiểm tra xem có đủ K viên đạn để bắn hết bia không bằng cách làm như sau: Sắp xếp các vị trí x1 < x2 < … < xn (Bia nằm rải rác, ta xử lý từ trái qua phải.) Duyệt từ trái sang phải:

1. Chọn bia đầu tiên chưa bị bắn làm mốc (x[i]).
2. Bắn 1 viên đạn sao cho nó bao phủ xa nhất có thể, tức là bắn ở vị trí x[i] + R. → Viên đạn này bao trùm vùng [x[i], x[i] + 2R]. Bỏ qua tất cả các bia nằm trong vùng này.
3. Tiếp tục sang bia tiếp theo chưa được bắn. Đếm xem tổng cộng cần bao nhiêu viên đạn. Nếu số viên đạn cần ≤ K, thì R đủ mạnh. Nếu > K, thì R quá nhỏ → cần tăng lên. → Từ đây ta nghĩ ra ý tưởng sử dụng chặt nhị phân để tìm R thỏa mãn Thuật toán: Chặt nhị phân để tìm R nhỏ nhất thỏa mãn khi ta duyệt như trên thì số đạn cần bắn <= K

Tom và Jerry Ý tưởng: Vì các con mèo có thể đánh hơi và tìm đúng hướng của jerry, nên nếu jerry nằm giữa 2 con mèo nào đó, ta sẽ tính được số bước để nó bị bắt Ta sẽ sort vị trí các con mèo lại cho dễ xử lí: Trường hợp cụ thể:

1. Nếu Jerry nằm bên trái tất cả mèo: Jerry sẽ chạy về hốc 1, còn mèo ở vị trí đầu tiên chạy từ a[1] → 1 → Số bước = a[1] - 1.
2. Nếu Jerry nằm bên phải tất cả mèo (k > a[m]) Jerry chạy về hốc n, còn mèo chạy từ a[m] → n. → Số bước = n - a[m].
3. Nếu Jerry nằm giữa hai mèo liên tiếp: Gọi vị trí 2 con mèo đó là a[g - 1] và a[g] thì Jerry sẽ bị ép dần vào giữa hai con mèo này → Vị trí an toàn nhất của Jerry là ở giữa hai mèo này (mid = (a[g-1] + a[g])/2) → Số bước bắt đc Jerry sẽ là khoảng cách nhỏ nhất giữa 2 con mèo và Jerry res = min(mid - a[g-1], a[g] - mid)

Xử lí xong 3 trường hợp rồi, vậy làm sao để ta biết được bài toán sẽ rơi vào trường hợp nào trong 3 trường hợp này? Rất đơn giản, chặt nhị phân để tìm kiếm con mèo đầu tiên có vị trí a[g] >= k (dùng lower_bound) Khi đó, nếu g = 1 → Trường hợp 1 Nếu g = m + 1 → Trường hợp 2 Còn lại là trường hợp 3

Đoạn chứa Bài này quá dễ 😛Đoạn ngắn nhất chứa cả dãy là đoạn từ số nhỏ nhất đến số lớn nhất trong dãy

Trình diễn xe hơi Sau thời gian T, nếu không bị xe nào cản trở thì vị trí dự kiến của xe là: p[i] = x[i] + v[i] * T Các xe được cho theo thứ tự tăng dần của x[i] (nghĩa là xe i luôn ở phía trước xe i−1 ban đầu) Vậy khi nào 2 xe nhập nhóm ? Giả sử có 2 xe: • Xe A ở trước (xA < xB) • Xe B ở sau (xB > xA) Nếu tại thời điểm nào đó xe B đuổi kịp xe A, thì từ đó trở đi, xe B chạy với tốc độ của xe A, nghĩa là cả hai xe thuộc cùng một nhóm. Vì vậy, khi ta xét ngược từ phải qua trái (từ xe cuối về đầu): • Xe cuối cùng chắc chắn là một nhóm riêng biệt (vì phía trước không có xe nào cản). • Mỗi xe bên trái có thể hợp nhóm với xe bên phải nếu vị trí dự kiến của nó lớn hơn hoặc bằng vị trí cuối cùng của nhóm bên phải (tức là nó đuổi kịp xe trước) • Tạo nhóm mới nếu nó vẫn còn cách xa và không đuổi kịp xe trước.

Phủ trục số Mục tiêu là tìm đoạn dài nhất được phủ kín bởi ít nhất một trong các đoạn này Nói cách khác: Nếu ta “tô” tất cả các đoạn đã cho lên trục số, thì ta cần tìm đoạn liên tục dài nhất đã được tô Vậy tô bằng cách nào? Ta sẽ tô bằng cách “hợp” các đoạn giao nhau, ví dụ [1,4] giao với [3,7] thì sẽ thành [1,7] → Khi đó bài toán trở thành tìm đoạn dài nhất trong các đoạn được tô Cách làm:

1. Sắp xếp các đoạn theo đầu mút trái aᵢ tăng dần. → Mục đích để các đoạn chồng nhau nằm gần nhau, dễ gộp lại.
2. Duyệt lần lượt các đoạn từ trái sang phải: • Giữ một đoạn hiện tại [l, h]. • Nếu đoạn kế tiếp bắt đầu trước hoặc đúng tại h, nghĩa là chồng hoặc nối liền, ta gộp lại: h = max(h, b[j]) • Nếu đoạn kế tiếp bắt đầu sau h, tức là đoạn hiện tại đã kết thúc, khi đó ta cập nhật độ dài lớn nhất, rồi bắt đầu một đoạn mới → Sau khi kết thúc, ans chính là độ dài lớn nhất vừa tìm đc

Tổng độ dài Giống bài trước, chỉ khác là bài này ta tính tổng độ dài được phủ thay vì tìm đoạn dài nhất

Ngày 28/10/2025: Luyện tập về xâu kí tự Bài 1. Chuẩn hóa xâu: Tách các từ trong xâu và lưu thành 1 mảng, mỗi phần tử là 1 từ. Chuẩn hóa các từ trong xâu (trừ từ cuối cùng) In theo đúng thứ tự: Tên Họ Dãy họ đệm Tiền lương (từ cuối cùng) Bài Băng rôn OLP Xét trên xâu S: Đếm các đoạn con có kí tự O, L hoặc P xuất hiện ít nhất 3 lần trở lên

cnt = 0; for(i = 0, i < s.length()) for(j = i -> s.length() for(i-> j) đếm O, L P xuất hiện bao nhiêu lần? nếu cntO, cntL hoặc cntP >= 3 thì cnt++; Giảm xuống 2 vòng for: Tính trước: cntO[i] là số kí tự O xuất hiện từ 1 -> i cntL[i], cntP[i]....

for(i = 0, i < s.length()) for(j = i -> s.length() nếu cntO[j] - cnt[i - 1] >= 3 (tương tự cntL hoặc cntP) thì cnt++;

    i                   j

Nếu ta tìm được vị trí j nhỏ nhất mà đoạn từ i -> j thỏa mãn có ít nhất 1 trong 3 kí tự O, L hoặc P xuất hiện ít nhất 3 lần khi đó mọi đoạn i -> j + 1, j + 2, …n đều thỏa mãn. Có thể sử dụng tìm kiếm nhị phân.

OLPOLPOLPOLPOLPOLP 12+ 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1=78 Bài 3. Tương tự bài 2 (Sử dụng mảng cộng dồn trên 3 kí tự A, B và C để so sánh Bài 4.Xâu đẩy vòng abcabc abc Lần lượt lấy 1 đoạn con gồm có m kí tự (m là độ dài xâu b) và đẩy vòng xem liệu xâu đó có bằng b hay không? Gợi ý: bca abcabc Khi phá vòng: nhân đôi xâu lên Nhân đội xâu b để tạo vòng lần lượt lấy từng đoạn con có m kí tự trên a và tìm xem nó có xuất hiện trong b (sau khi nhân đôi hay không). cin >> a; cin >> b; n = a.length(); m = b. length(); b = b + b; cnt = 0; for(int i = 0; i < n- m + 1; i++) { s = a.substr(i, m); if(b.find(s) != string::npos)cnt++; } cout << cnt; Bài Xâu lặp Gọi n là độ dài xâu A Gọi m là độ dài xâu B Nhận xét: xâu lặp (nếu tồn tại) nó có độ dài là UCLN(n, m) TÌm k = UCLN(m, n) Cần kiểm tra xem xâu có k kí tự đầu của A = k kí tự đầu của B hay không? ABABABABAB ABABABAB n = 10, m = 8 k = gcd(10, 8) = 2 x = AB y = AB Nếu hai đoạn đầu của 2 xâu bằng nhau rồi thì ta tạo ra 1 xâu từ x có độ dài n và xem xâu được tạo ra có == A hay không? tạo ra 1 xâu có độ dài m bằng cách viết lặp lại nhiều lân xâu x xem xâu mới được tạo ra có == B hay không? -> Xâu lặp chính là k kí tự đầu của A.

Tạo chuỗi Ý tưởng: Ta muốn tổng số ký tự trong chuỗi là lớn nhất → nên dùng các ký tự có giới hạn lớn trước. Nhưng vì số lần xuất hiện của các ký tự phải phân biệt, nên mỗi ký tự sau phải có số lần xuất hiện nhỏ hơn ký tự trước ít nhất 1 Thuật toán: Với mỗi kí tự ta lưu vào pair 2 giá trị, first là số lượng của nó (đề bài cho), second là giá chữ cái của nó Sắp xếp các pair theo a[i].first tăng dần Duyệt ngược lại (từ ký tự có a[i].first lớn nhất → nhỏ nhất):

1. Giữ biến cnt (giới hạn trên cho số lần xuất hiện hiện tại).
2. Với ký tự hiện tại: • Số lần xuất hiện thực tế x = min(a[i].first, cnt - 1). • In ký tự đó x lần. • Cập nhật cnt = x.

Sửa ngoặc Với các bài về dãy ngoặc đúng, ta quy ước ‘(‘ = 1, ‘)’ = -1 → Một xâu ngoặc là đúng nếu thỏa 2 điều kiện: • Khi duyệt từ trái qua phải, số lượng dấu ')' không bao giờ vượt quá số lượng dấu '(' trước đó (hay nói cách khác: mọi prefix đều >= 0) • Sau khi duyệt hết, sum = 0 Thuật toán: Ta tạo mảng d[i]: prefix từ đầu đến i Khi đó, xâu đúng khi d[n] = 0 và d[i] >= 0 với mọi i Điều gì sẽ xảy ra nếu ta đổi 1 kí tự ? • Nếu đổi '(' → ')', thì mọi d[j] với j ≥ i sẽ giảm đi 2 → Tổng cuối d[n] giảm 2 • Nếu đổi ')' → '('', thì mọi d[j] với j ≥ i tăng 2 → Tổng cuối d[n] tăng 2 Vậy khi nào thì 1 lượt đổi là đúng ? • Nếu đổi i, ta cần d[j] >= 0 với mọi j <= i • Nếu đổi s[i] từ ‘(‘ → ‘)’, ta cần d[n] - 2 = 0 → d[n] = 2 p, và d[j] >= 2 với mọi j > i • Nếu đổi s[i] từ ‘)’ → ‘(‘, ta cần d[n] + 2 = 0 → d[n] = -2 và i != n Để giải quyết điều kiện d[j] >= 2 hoặc d[j] >= 0 như trên thì ta chỉ đơn giản là tạo ra 1 mảng prefixmin và suffixmin, ví dụ: m[i]: lưu lại min tất cả các prefix từ n → i b[i]: lưu lại min tất cả prefix từ 1 → i

Viết lại số Nhận xét 1: vì s[i] chỉ có tối đa 1e5 chữ số → tổng lớn nhất có thể tạo thành là 9e5 (trong trường hợp xâu s là full 999999…) → Tổng tối đa khi ghép vào chỉ có 6 chữ số, tức là khi xét trên t, chỉ có tối đa 6 phần tử liên tiếp là “tiềm năng” để được ghép thành từ xâu s Nhận xét 2: Điểm bắt đầu được xét trên xâu t chính là điểm bắt đầu bị ghép trên xâu s, nghĩa là giả sử ta lấy đoạn được ghép thành trên xâu t là t[i…m] thì đoạn bị ghép trên xâu s phải là s[i…n] → Thuật toán: Đầu tiên ta tìm vị trí đầu tiên mà 2 xâu khác nhau tính từ cuối, gọi là last, đây sẽ là chốt chặn để ta biết mình xét có đúng không Tạo một mảng cộng dồn cho tổng các phần tử trên xâu s[i], gọi là prefix[i] Xét tất cả các vị trí trên xâu t, coi đó là điểm bắt đầu, gọi điểm đó là i, ta sẽ kiểm tra xem các đoạn t[i…k] có phải 1 đoạn được ghép thành thỏa mãn ko 1 đoạn từ t[i…k] được coi là đoạn thỏa mãn nếu • k >= last (nghĩa là phải thay thế hết các phần tử khác nhau giữa s và t) • t[i…k] = tổng các phần tử trong đoạn từ i → (n - m - k) của s (vì sau khi ghép xong thì s = t) Code mẫu:

Đếm xâu con Tạo mảng cộng dồn prefix[i]: số lượng số 1 cho đến phần tử i Đếm số lượng đoạn con = k → Đếm số cặp l,r sao cho prefix[r] - prefix[l] = k → prefix[l] = prefix[r] - k → Với mỗi r, ta đếm số phần tử l sao cho thỏa mãn điều kiện trên, để tối ưu thời gian thì ta sẽ sử dụng mảng đánh dấu

Chuột Hamster Xét ví dụ: XAAEFYB X Y OIIIXIOIIXIIOX X O i 0 1 2 3 4 5 6 7 8 9 10 11 12 13
s X A A E F Y B X A A E F Y B
x o
O I I I X I O I I X I X I I

i 1 2 3 4
posx 4 9 13
posy 0 6 12

Ý tưởng: Ta tạo ra 2 mảng posx và posy lưu lại vị trí xuất hiện của các X và Y Với mỗi v = posX[i], ta cần tìm chỉ số j nhỏ nhất sao cho posY[j] >= v → Chặt nhị phân để tìm số j này Khoảng cách tối thiểu để đi tới một Y có thể nằm ở: • posY[j] (đi phải) • posY[j-1] (đi trái) → Nếu đặt chuột ở vị trí v đó, khoảng cách chuột cần di chuyển là min(posx[i] - posy[j - 1], posy[j] - posx[i]), tuy nhiên ta cần xét thêm trường hợp đi vòng ngược lại vì đây là vòng tròn nên sẽ xét thêm 2 trường hợp j = 1 và j = ny + 1 (chặt nhị phân không tìm được thì sẽ trả về ny + 1) Chú thích: ny là số lượng phần tử Y trong dãy Ví dụ: Nếu đặt v tại: posx[1] = 4 → j = 2: res1 = min(6 - 4, 4 - 0) = 2 posx[2] = 9 → j = 3: res2 = min(12 - 9, 9 - 6) = 3 posx[3] = 13 → j = 4: res3 = min(13 - 12, n - posy[ny]+posy[1]) Đáp án sẽ chính là max của tất cả các khoảng cách mình thử (các res đó)

Ngày 21/10/2025: Luyện tập Bài 1. Số gần nguyên tố Một số có số lượng ước số lẻ là số đặc điểm gì? là số chính phương Nếu 1 số bình thường thì các ước đi theo cặp: (1, n/1), (a, n/a)..... Vì số ước là lẻ nên có 1 cặp ước a và n/a là bằng nhau. a = n/a -> a^2 = n -> n là số chính phương. Một số n chỉ có 3 ước (số ước lẻ) -> n là số chính phương nhưng 16: 1 2 4 8 16 Nếu a^2 = n thì a là số nguyên tố n có 3 ước là 1, a và n -> a phải ko có ước nào ngoài 1 và chính nó (vì nếu a có ước thì các ước a chắc chắn là ước của n) -> Bài toán quy về việc tìm số k nhỏ nhất >= n sao cho k là bình phương của 1 số nguyên tố. while(true) { kiểm tra xem n có là bình phương của 1 snt? nếu có -> in ra n và break; ngược lại n++; } Để tối ưu: Ta cần phải tìm 1 số nguyên tố rồi bình phương lên để ra 1 số >= n nếu k là 1 số nguyên tố và k * k >= n thì k sqrt(n) Bài 2. Đếm số lượng ước nguyên tố Phân tích 1 số thành tích các TSNT và đếm số lượng Thừa số khác nhau 36 = 2 * 2 * 3 * 3 k = 2 * 2 * 3 * 5 * 7 * 11^4 Bài 3. Tổng ước chẵn Đề bảo gì làm nấy, ta tính tổng các ước của từng số trong mảng, nếu tổng đó là chẵn → cnt++ Bài 4. Lớp học múa Quy ước: nếu kí tự a[i] = ‘a’ => a[i] = 1 ngược lại a[i] = -1. Từ mảng a tính mảng cộng dồn

    i           j

a 1 -1 1 -1 -1 1 s 0 1 0 1 0 -1 0 s’ -1 0 0 0 0 1 1 Tổng từ i -> j == 0 thì s[j] - s[i - 1] = 0 -> s[j] = s[i -1] Các bước cần làm: Đọc vào dãy kí tự và tạo thành mảng a như định nghĩa ở trên Tính mảng cộng dồn s. Tìm tổng của 1 đoạn con liên tiếp = 0 Tìm số cách chọn ra các đoạn con như vậy Cách 1: Trâu: cnt = 0; for(i = 1-> n) for(j = i -> n) { if(s[j] - s[i - 1] == 0) cnt++; } Cách 2: Sắp xếp mảng s tăng dần Sau đó đếm các đoạn có giá trị bằng nhau. Với mỗi đoạn bằng nhau ta tính được số dãy con có tổng = 0: k(k-1)/2 với k là độ dài của đoạn bằng nhau đó 1, 4 2 10/2 + 43/2 + 2*½=7 abbababa

0   1   2   3   4   5   6   7   8

a 1 -1 -1 1 -1 1 -1 1 s 0 1 0 -1 0 -1 0 -1 0 s’ -1 -1 -1 0 0 0 0 0 1 Đoạn các giá trị trên s’ bằng -1: 3: 32/2 =3 Đoạn các giá trị trên s’ bằng 0: 5: 54/2 =10 Đáp số: 3 + 10 = 13

Bài Số đặc biệt: Từ mảng a ta xây dựng mảng b: nếu a[i] chia hết cho tcs của a[i] thì b[i] = 1 ngược lại b[i] = 0. Từ đây dựa trên mảng b ta sẽ đếm được từng đoạn l-> r có bao nhiêu số đặc biệt dựa trên mảng cộng dồn của b:

i 0 1 2 3 4 5 6 7 8 9 10 a 15 11 18 13 6 7 3 11 12 14 b 0 0 1 0 1 1 1 0 1 1 s 0 0 0 1 1 2 3 4 4 5 6

s[8] - s[2] = 4 là số lượng số đặc biệt trong khoảng từ 3 -> 8 Bài Sưu tâp đá quý SX các viên đá tăng dần Chọn viên đá có kích thước nhỏ nhất, chọn viên tiếp theo có kích thước có chênh lệch >=k ….cho tới khi hết dãy a[0], a[1], a[j] a[i]

Vòng tròn số Ý tưởng: Tạo 2 mảng after[x]: số đứng ngay sau x trong vòng tròn before[x]: số đứng ngay trước x trong vòng tròn Ban đầu, các số được xếp theo thứ tự tăng dần Ví dụ: before[2] = 1, after[1] = 2, before[3] = 2, after[2] = 3… Mỗi khi ta thực hiện thao tác với 2 số i và j → số i được chuyển lên trước số j trong mảng → liên kết giữa các số sẽ thay đổi Ta chia bước chuyển đó ra làm 2 bước: Bước 1: Lấy số i ra khỏi mảng after[before[i]] = after[i]; before[after[i]] = before[i];

Bước 2: Chèn số i vào trước số j (Chèn i vào giữa số đứng trước j và số j) int p = before[j]; // p là số đứng trước j after[p] = i; // vì i được chèn vào giữa p và j before[i] = p; after[i] = j;
before[j] = i;

→ Với mỗi thao tác i và j ta thực hiện 2 bước như trên. Cuối cùng in ra dãy số bắt đầu từ 1 int x = 1; for(int i = 1; i <= n; i++) { cout << x << ‘ ‘; x = next[x] //đi đến số tiếp theo sau x } Nối khoảng Đề bài: Cần tìm số lượng nhiều nhất đoạn dây có thể nối liên tiếp với nhau Cách 1: Ý tưởng ngây thơ • Chạy đệ quy, xét từng đoạn [a,b], tìm đoạn tiếp theo bắt đầu ở b,.... • Cuối cùng sau khi không tìm được đoạn con tiếp theo bắt đầu ở b thì ta đã có thêm một phương án sắp xếp. Kết quả của bài chính là max số lượng đoạn con được dùng trong tất cả các phương án đã tìm được → Khó cài đặt và độ phức tạp rất lớn

Cách 2: Dùng quy hoạch động • Dùng mảng dp[x] (x là điểm tọa độ) lưu độ dài xâu nối nhau dài nhất kết thúc tại điểm x. • Sắp xếp tất cả các đoạn theo điểm kết thúc b tăng dần; nếu cùng b thì theo a tăng dần. • Dịch tọa độ nếu cần để tránh chỉ số âm (ví dụ +100000). • Duyệt từng đoạn [a,b] theo thứ tự đã sắp: • Cập nhật dp[b] = max(dp[b], dp[a] + 1) • Theo dõi ans = max(ans, dp[b]) → Kết quả là ans. → Độ phức tạp chỉ khoảng o(nlogn)

Code mẫu cài đặt: for (int i = 0; i < n; i++) cin >> seg[i].first >> seg[i].second;

 sort(seg.begin(), seg.end(), [](pair<int,int> x, pair<int,int> y) {
    if (x.second != y.second) return x.second < y.second;
    return x.first < y.first;
}); // Viết lại hàm compare để ưu tiên thằng đuôi hơn

int ans = 0;

for (auto x : seg) {
   int a = x.first, b = x.second; 
    a += OFFSET; // Tránh số âm
    b += OFFSET; 
    dp[b] = max(dp[b], dp[a] + 1);
    ans = max(ans, dp[b]);
}

cout << ans;

Bánh trung thu Nhận xét: Để hình chữ nhật nằm hoàn toàn trong hình tròn thì khoảng cách giữa gốc tọa độ với mọi điểm trên hình chữ nhật phải <= bán kính Gọi bán kính hình tròn là r Mà ta biết điểm xa nhất so với gốc tọa độ của hình chữ nhật là điểm ở góc hình chữ nhật, ta gọi 4 góc là A, B, C, D → OA <= r Vậy nếu OA <= r thì in ra YES, ngược lại in ra NO

Ngày 07 + 14/10/2025: Mảng cộng dồn • Khái niệm: Cộng dồn các phần tử của mảng ban đầu vào 1 biến.

i 0 1 2 3 4 5 6 7 8 9 A 1 2 6 -3 2 1 2 0 3 S 0 1 3 9 6 8 9 11 11 14 i j
s[0] = 0 s[1] = 0 + a[1] = s[0] + a[1] s[2] = a[1] + a[2] = s[1] + a[2] s[3] = a[1] + a[2]+ a[3] = s[2] + a[3] s[4] = a[1] + a[2]+ a[3] + a[4] = s[3] + a[4] …. s[i] = s[i - 1] + a[i] Khi đó, S được gọi là mảng cộng dồn của mảng A. Cách tính S: s[0] = 0; for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; • Dùng mảng cộng dồn S để làm gì? Khi cần tính tổng của 1 đoạn con liên tiếp từ i -> j: Sum = a[i] + a[i + 1]+...+ a[j] Sum = 0; for(int k = i; k <= j; k++) Sum += a[k]; -> Cách tính trên bị lâu. nếu có mảng S: ta sẽ tính tổng của 1 đoạn từ i -> j: Sum = s[j] - s[i - 1]; res = n + 1; for(int i = 1; i <= n; i++) { for(int j = i; j <=n; j++) { sum = s[j] - s[i - 1];///tổng từ i -> j ==m if(sum == m) res = min(res, j - i + 1); } }

Để được 100 điểm bài 1: Do dãy A toàn các số nguyên dương s[i] = s[i - 1] + a[i] -> s[i] > s[i - 1] Vậy ta có kết luận: dãy s tăng dần. xét lần lượt từng phần tử trên S từ s[0], s[1], …với mỗi s[.] (ví dụ là s[0] ta đặt v = s[0] + m và ta cần tìm xem có 1 giá trị nào trong mảng s: s[i] = v hay không? s[i] = s[0] + m -> s[i] - s[0] = m//đoạn từ 1 -> i có tổng = m for(int i = 0; i <= n; i++) { int j = BS(s[i]+m); if(j > 0) res = min(res, j - i); }

Cài hàm BS: int BS(long long v) { int l = 1, r = n, mid; while(l <= r)//dừng khi l > r { mid = (l + r)/2); if(a[mid] < x) l = mid + 1; else r = mid - 1; } if(l <= n and a[l] == x) return l; else return -1; }

Bài 2. Thi Nấu ăn Có mảng A: a[i] là số món ăn được nấu bởi người thứ i: Ta cần biết số báo danh các món ăn của người thứ i đã nấu là các số nào? 5 3 i : 0 1 2 3 4 5 A: 5 4 1 2 3 S: 0 5 9 10 12 15 Các món ăn của người 1: 1, 2, 3, 4, 5 Các món ăn của người 2: 6, 7, 8, 9 Các món ăn của người 3: 10 Các món ăn của người 4:11 12 Các món ăn của người 5: 13 14 15 Hỏi: các món 5 6 12 là do ai nấu? S là 1 mảng tăng dần. Với mỗi giá trị p, ta cần tìm giá trị i: sao cho s[i] <= p Bài 3: Ban đầu a[i] = i sau đó tìm cách biến đổi a[i] thành số có 1 chữ số như đề bài yêu cầu. Khi đó, tính tổng cộng dồn s. với mỗi câu hỏi L, R: s[R] - s[L - 1]

Bài 4. Thay vì cần 1 mảng cộng dồn ta cần tới 3 mảng cộng dồn cho 3 loại bò khác nhau và sau đó sử dụng mảng cộng dồn để tìm đoạn có 3 tổng đoạn bằng nhau Bài 5: SUM 1 = Tưới cây 1 (giống nhau) Tính chất: Khi tăng từ i -> j trên mảng s: s[i] = s[i] +x s[i + 1] =s[i + 1] + x …. s[j]= s[j] +x for(k = i-> j) s[k] = s[k] + x; Thì tương đương với việc ta chỉ cần thay đổi ở 2 vị trí trên mảng a: a[i] = a[i] + x; a[j + 1] = a[j + 1] -x; Ví dụ:

i 0 1 2 3 4 5 6 7 8 9 10 a 1 2 1 -3+2 2 1 -2 2 - 2 1 1 s 0 1 3 4 1+2 3+2 4+2 2+2 4 5 6 Nếu tăng a[i] = a[i] + x thì trên mảng s: toàn bộ các giá trị từ s[i] -> s[n] đều tăng lên 1 lượng bằng x

Bài 7(kéo búa bao): Tương tự bài đếm giống Nếu là H: Kéo Nếu là P: Bao Nếu là S: Búa Kéo > Bao, Bao > Búa, Búa > Kéo

Cuội: P P H P S Bờm:H H H S S Các vị trí thắng của Bờm từ 1 -> i: là các trận Cuội ra P: p[i] Các trận thắng của Bờm từ i + 1-> n: là các trận mà Cuội ra H: h[n] - h[i] Tạo 3 mảng: Kéo: h Búa: s Bao: p Ban đầu khởi tạo toàn bộ 3 mảng = 0 Gán giá trị theo dãy kí tự đọc vào: Tính 3 mảng cộng dồn về số lần ra P, S và ra H của Cuội p[i] = p[i -1] + (a[i] == ‘P’); s[i] = s[i - 1] + (a[i] == ‘S’); h[i] = h[i - 1] + (a[i] == ‘H’) Xét các trường hợp: res = 0;///là biến ghi nhận số trận thắng của Bờm Nếu ra H từ 1-> i và từ i + 1 đổi thành S: for i = 1-> n: res = max(res, p[i] + s[n] - s[i]) tại sao số trận thắng của Bờm lại được tính bằng công thức này nếu i kí tự đầu là H và n - i kí tự sai là S: ph[i] + pp[n] - pp[i]: Vì Bờm ra H nên số trận thắng từ 1-> i là số trận Cuội ra búa. Mà số trận ra búa của Cuội chính là ph[i] Nếu ra H từ 1-> i và từ i + 1 đổi thành P res = max(res, ph[i] + ps[n] - ps[i]) Nếu ra S từ 1-> i và từ i + 1 đổi thành P res = max(res, pp[i] + ph[n] - ph[i]) Nếu ra S từ 1-> i và từ i + 1 đổi thành H Nếu ra P từ 1-> i và từ i + 1 đổi thành S Nếu ra P từ 1-> i và từ i + 1 đổi thành H HHHHHHSSSS PSSSSSSSSS Giả sử ban đầu chọn H và đến i + 1 đổi thành S

Dãy cân bằng • Một cách xử lý bài này là ta một mảng mới b bằng cách • b[i] = 1 nếu a[i] chẵn • b[i] = -1 nếu a[i] lẻ • Việc ta đang làm là thay số chẵn = 1 và thay số lẻ = -1 thì một dãy cân bằng trên dãy a sẽ có tổng bằng 0 trong dãy b • Mà một dãy liên tiếp [l, r] (từ l đến r) có tổng bằng 0 thì với sum là mảng cộng dồn của dãy b: sum[r] - sum[l-1] = 0 <=> sum[r] = sum[l-1] • Mà ta muốn đếm số đoạn cân bằng chính là đếm các bộ hai chỉ số l, r mà có cùng giá trị trên mảng cộng dồn

Đoạn con có tổng lớn nhất • Ta tạo mảng cộng dồn sum trên mảng a thì rõ ràng tổng các phần từ liên tiếp từ l đến r trong mảng a sẽ sử dụng công thức sum[r] - sum[l-1]. Giả sử ta cố định vị trí kết thúc r ta cần tìm đoạn con có tổng lớn nhất kết thúc tại r thì ta cần tham lam tìm sum[l-1] có giá trị bé nhất thì sum[r]-sum[l-1] có giá trị lớn nhất. • Và thật ra ta có thể duy trì giá trị nhỏ nhất này bằng quan sat sau giả sử từ r chuyển sang r+1 thì giá trị min(sum[l-1]) với l <= r nhỏ nhất sẽ thay đổi như nào ? • Nó sẽ có thêm giá trị sum[r] như sau: • Tại r thì min(sum[l-1]) = min(sum[0], sum[1], ..., sum[r-1]) • Tại r+1 thì min(sum[l-1]) = min(sum[0], sum[1], ..., sum[r-1], sum[r]) • Bằng cách cố định r và duy trì giá trị min(sum[l-1]) với mỗi r, ta có thể tính đoạn con có tổng lớn nhất kết thúc tại r. Vậy với n giá trị r có thể ta lấy max mọi giá có thể thì thu được kết quả với độ phức tạp O(n) Ảnh đẹp

            i-k             i

Ta cần chọn 1 dãy dài nhất có độ dài chẵn (ít nhất là 4 phần tử) sao cho tổng lớn nhất Giả sử cây cuối cùng ta chọn là i: res = s[i] - min(s[i - 4], s[i - 6], s[i - 8]....) res = -1e9-1; for(int i = 4 -> n) for(j = i - 4, j >= 0, j -=2)
res = max(res, s[i] - s[j]) ///tổng từ j + 1-> i -> Đây là thuật TLE Cải tiến: min(s[i - 4], s[i - 6], s[i - 8]....) f[i] = min(s[i], s[i -2], s[i -4], s[i- 6]..., s[0]) //i chẵn f[i] = min(s[i], s[i -2], s[i -4], s[i- 6]..., s[1]) //i lẻ f[6] = min(s[0], s[2], s[4], s[6]) f[5] = min(s[5], s[3], s[1]) f[7] = min(s[7], s[5], s[3], s[1]) = min(f[5], s[7]) Tính f: f[0] = s[0], f[1] = s[1]; for(i = 2->n) f[i] = min(f[i - 2], s[i]); res = -vc; for(i = 4; i <= n; i++) res = max(res, s[i] - f[i - 4]) Thực chất f cũng là 1 mảng tiền xử lý (tính trước) nhưng ko phải tính tổng mà là tính min. Cho nên nếu s được gọi là mảng cộng dồn thì f được gọi là min dồn Đọc a Tính s Tính f rồi tính res

Đoạn giá trị lớn nhất • Vẫn giống với ý tưởng của bài trước, chỉ khác là lần này ta sẽ cập nhật sau k bước thôi, tính trước f là mảng min dồn rồi với mỗi i ta sẽ tính res = prefix[i] - f[i - k] và lấy max của tất cả các res với mọi i

Đội hình thi đấu Tổng của sức mạnh đội trưởng + dẻo dai của k - 1 người còn lại là min.

Nếu ko cần đội trưởng thì việc chọn k người ta sẽ chọn như nào? Ta cứ chọn k người có b nhỏ nhất -> sx n người theo b vấn đề làm sao để lưu được thông tin của n người rồi sx lại? mỗi người ta lưu vào 1 pair<long long, long long> a[N]; Mỗi người: cho a trước b. ta sẽ lưu a ở second và b ở first: cin >> a[i].second >> a[i].first; sort(a + 1, a + n + 1); thì mặc định là nó sx theo b

Sau khi sort: res = 0; for(k = 1-> n) res = res + a[i].first; cout << res << “ ”; Ta chỉ được chọn k - 1 người có độ dẻo dai thấp nhất và 1 đội trưởng

i x k
dd 1 2 3 6 7 8 9
sm 4 5 -2 3 6 1 1
ma -2 -2 -2 1 1 1 1
Phương án chọn đội trưởng: Tính trước max(b[x] - a[x]) với mọi x từ 1 ->n md[i] = max(b[1] - a[1], b[2] - a[2], b[3] - a[3]..) Phương án 1: Chọn ra từ k ban đầu. res = b[1] + b[2]+...+b[k] - (b[x] -a[x]) Để res min thì b[x] - a[x] phải đạt max. Gọi md[k] là max(b[x] -a[x]) để res min thì (b[x]- a[x]) đạt max Phương án 2: Chọn đội trưởng từ những người từ k -> n có min(a[i]) nhỏ nhất: b[1] + b[2] +...+b[k - 1] + min(a[i]) i=k->n Vậy min(a[i]) i=k->n nên được tính trước: ma[n] = a[n]; for(int i = n - 1 -> 0) ma[i] = min(ma[i + 1], a[i]) • Ta nhận thấy vì chỉ cần 1 đội trường và k-1 đội viên nên nếu chọn trước được đội trưởng ta sẽ tham lam chọn k-1 đội viên còn lại có độ dẻo dai nhỏ nhất có thể để tiềm năng của đội là thấp nhất • Ta sẽ sắp xếp n thành viên theo độ dẻo dai tăng dần thì nếu đội trưởng thuộc khoảng [k, n] thì đương nhiên ta chọn k-1 đội viên đầu vì sau khi sắp xếp lại thì họ là các đội viên ít dẻo dai nhất → Có thể sử dụng prefix sum để tính trước tổng độ dẻo dai của k - 1 thành viên đầu • Vậy nếu đội trưởng nằm trong khoảng [k, n] thì ta sẽ chọn ai ? Đương nhiên là ta sẽ chọn người có sức mạnh nhỏ nhất trong khoảng [k, n] để tối thiểu hóa tiềm năng của đội → Dùng ý tưởng tương tự prefix sum để lưu trước người đó • Còn nếu đội trưởng thuộc k-1 đội viên đầu thì rõ ràng k-1 đội viên dẻo dai nhất chính là từ [1, k] và bỏ đi người đội trưởng hiện tại • Trong trường hợp đội trường thuộc k - 1 người đầu, giả sử người ta chọn là i, nếu so sánh với cách chọn ở trên (chọn đội trưởng trong khoảng [k, n] thì ta sẽ lỗ a[i] - b[i] tiềm năng tổng của cả đội), vậy để tối thiểu hóa chi phí, ta sẽ chọn người có hiệu a[i] - b[i] nhỏ nhất. → Làm tương tự như trên, lưu trước người đó

→ Với mỗi k, ta phải thử cả 2 cách chọn đội trưởng ở trên và chọn ra cách tối ưu nhất • Vậy ta tính được sức mạnh của cả đội với n người đội trưởng có thể thì độ phức tạp là O(n)

Biến đổi dãy số (CSEQ) • Bài này là phiên bản khác của đoạn giá trị lớn nhất • Ta nhận thấy khi ta thực hiện thao tác đổi dấu đoạn [l, r] thì dấu hay giá trị các khoảng bên ngoài không đổi hay [1, l-1] và [r+1, n] không đổi. Lúc này nếu ta biểu diễn dưới dạng mảng cộng dồn sum thì nếu đổi dấu đoạn [l, r] thì tổng n phần từ sẽ thành sum[l-1] + (sum[n] - sum[r]) -(sum[r]-sum[l-1]) lần lượt là • Tổng l-1 phần từ đầu • Tổng n-r phần từ cuối • Tổng r-l+1 phần tử đổi dấu • Thu gọn lại ta thu được sum[n]-2sum[r] + 2sum[l-1] =sum[n]-2*(sum[r]-sum[l-1]) • Để tổng lớn nhất thì ta cần tìm tổng đoạn con liên tiếp [l, r] nhỏ nhất có thể vậy ta chỉ cần làm ngược lại bài đoạn giá trị lớn nhất là được

Hình chữ nhật lớn nhất • Ta sẽ quy bài này từ 2 chiều thành 1 chiều như sau • Để xác định được 1 hình chữ nhật trước hết ta cố định hai hàng l, r tức là ta sẽ xét hết hình chữ nhật bắt đầu từ hàng l và kết thúc ở hàng r • Việc này sẽ tốn O(n2) với mọi cặp l, r và ta còn phải xác định số cột nhưng lúc này khi đã xác định được hàng bắt đầu và kết thúc rồi thì với mỗi cột j ta sẽ lấy hết các phần tử thuộc hàng [l, r] cho nên ta cần tạo mảng b với ý nghĩa bj=∑ai,j với l <= i <= r • Vậy giá trị hình chữ nhật từ cột x đến cột y, hàng l đến hàng r chính là tổng của bl+bl+1+...+br. Hay ta cần tính đoạn con lớn nhất trên mảng b việc này tương tự bài trên ta có thể hoàn thành trong O(n) vậy tổng độ phức tạp là O(n3) • Một lưu ý nhỏ là các bạn cần tính tổng phần từ thuộc các hàng [l, r] cho mỗi cột (hay chính là các giá trị của mảng b) một cách nhanh chóng thì ta dễ dàng làm được bằng cách lưu một mảng cộng dồn theo mỗi cột tức là lưu n mảng cộng dồn cho n cột

Chia đất Chọn một điểm (i,j) làm đỉnh chung của hai hình chữ nhật. Có hai kiểu chia quanh đỉnh (i,j):

• Cách 1: một hình nằm trên-trái của (i,j), hình kia nằm dưới-phải của (i+1,j+1).
• Cách 2: một hình nằm trên-phải của (i,j), hình kia nằm dưới-trái của (i+1,j-1).

Với mỗi kiểu, ta cần đếm số đôi sao cho tổng hai hình chung đỉnh (i,j) bằng nhau. Để nhanh, ta cần dùng prefix sum 2D để tính tổng Giả sử ta duyệt theo cách 1 (cách 2 các bạn làm tương tự) Bước 1: Duyệt tất cả hình chữ nhật ở phía trên trái lưu số lần xuất hiện của mỗi tổng vào cnt[sum]. Bước 2: Duyệt các hình chữ nhật ở phía dưới phải. Giả sử hình chữ nhật ở dưới phải có tổng = S, mà ta đã biết được số hình chữ nhất ở phía trên trái có tổng = S là cnt[S] (làm ở bước 1) ==> Lúc này chỉ cần tăng kết quả thêm cnt[S] Lặp qua tất cả (i,j) và cả hai kiểu ⇒ tổng cuối cùng là kết quả.

Ví dụ cách code theo Cách 1 (Trên trái - Dưới phải) for (i = 1 ; i <= n-1; ++i) for (j = 1 ; j <= n-1 ; ++j) //TẠO bảng đếm COUNT (rỗng) for (int xup = 1 ; xup <= i ; ++xup) for( yup = 1 ; yup <= j; ++yup) { Sup = GETSUM(xup, yup, i, j) // Các bạn tự code hàm này COUNT[S_up] += 1 }

    for ( int x_low = i+1 ; x_low <= n; ++x_low)
        for (int y_low = j+1 ; y_low <= n ; ++y_low) 
        {
            S_low = GET_SUM(i+1, j+1, x_low, y_low)
            res += COUNT[S_low]   // có COUNT[S_low] cách chia hợp lệ
         }

->Độ phức tạp: Với n ≤ 50, mỗi (i,j) xét tối đa O(n²) hình chữ nhật 2 lần ⇒ tổng khoảng O(n^4) (vẫn chạy tốt với n nhỏ)

Ngày 30/9/2025: Tìm kiếm nhị phân Bài 1: Tìm đoạn chứa: Đưa về bài toán tìm max và min của n giá trị đã cho. Gọi giá trị max là R và giá trị min là L Đoạn chứa đủ n điểm có độ dài ngắn nhất chính là [L, R] Bài 2. Phép cộng

1 2 3 4 5 6 7 8 0 0 +1 +1 hai chữ số hàng ĐV: 4 + 8 Bài 3: Contain: Viết 1 hàm bool check(int n, int d) Để kiểm tra trong số n có chứa chữ số d hay không? ví dụ: n = 234557, d = 8 -> không n = 234557, d = 3 -> có Gợi ý: sử dụng kĩ thuật tách chữ số.

cnt = 0; for(int i = 1-> n) if(check(i, d)) == true) cnt++;

cout << cnt;

Bài 4: Tìm kiếm trong xâu: áp dụng thuật toán thống kê xem mỗi chữ cái từ a-> z xuất hiện ở trong xâu hay không? Ôn tập về thuật toán tìm kiếm nhị phân: Có 2 dạng: 1 dạng dễ: Cho 1 dãy đã sắp xếp (tăng dần hoặc giảm dần) và một số x. Hỏi x có trong dãy hay không? Cách làm truyền thống: int t = 0; for(int i = 1; i <= n; i++) if(a[i] == x) { t = 1; break;} if(t == 1) cout << “YES”; else cout << “NO”;

i 1 2 3 4 5 6 n a 2 4 5 7 9 12 15 18 20 l r >=p l r Cải tiến: Do dãy tăng dần nên thay vì ta tìm từ đầu đến cuối (như code ở trên) thì ta lấy phần tử ở giữa dãy và so sánh với x = 15: l = 1, r = n; while(l <= r)//dừng khi l > r { mid = (l + r)/2); if(a[mid] < x) l = mid + 1; else r = mid - 1; } if(l <= n and a[l] == x) return true; else return false; HÀM SẮP XẾP: sx một đoạn từ i -> j trong dãy a 1 2 i j n 1
int a[N]; tạo ra N ô nhớ có địa chỉ liên tiếp trong bộ nhớ và ô nhớ đầu tiên a, a + 1, a + 2, ….., a + n. Khi yêu cầu sx một đoạn trong dãy từ a[i] -> a[j]: địa chỉ của a[i] trong bộ nhớ: a + i địa chỉ của a[j] trong bộ nhớ: a + j sort(a + i, a + j + 1); Nếu là ngày tháng: 30/9/2025 + 7 = 7/10/2025 Bài 6. Thi hoa hậu Với mỗi giá trị p: Bằng tìm kiếm nhị phân ta tìm vị trí l bằng hàm tìm kiếm nhị phân như dưới đây: l = 1, r = n; while(l <= r)//dừng khi l > r { mid = (l + r)/2); if(a[mid] < x) l = mid + 1; else r = mid - 1; } return l;//từ a[l] -> a[n] là tất cả các giá trị >= x. Với mỗi p: cin >> p; k = BS(p); cout << n - k + 1; Bài 7. Tổng các số chính phương: Ta biết rằng: 1^2 +2^2+ 3^2 +...+n^2 = n(n + 1)(2n + 1)/6 Với một số x: ta cần tìm 1 số n thỏa mãn: n(n + 1)(2n + 1)/6 <= x l = 1, r = 10^18, mid mid: mid (mid + 1)(2mid+1)/6 <= x?

Thu hoạch trứng • Ta chặt nhị phân thời gian nhỏ nhất để thu hoạch trứng vì nếu trong thời gian mid thu được x quả trứng thì chắc chắn trong thời gian mid + 1 sẽ thu được ít nhất là x quả trứng • Bài toán của ta bây giờ là với mid thời gian thì ta có thể vận chuyển được bao nhiêu quả trứng, nếu đủ x quả trứng thì mid thỏa mãn, ta thu hẹp phạm vi tìm kiếm và ngược lại • Với con gà thứ i, trong thời gian mid ta thu được (mid - p[i]) / t[i] + 1 quả trứng → Ta tính tổng số quả trứng thu được qua mỗi con gà, kiểm tra xem tổng đó có >= x không, nếu có thì mid thỏa mãn và ngược lại Bài 9: Dãy con: dãy a dãy b Tìm trên mỗi dãy 1 đoạn con sao cho tổng của chúng bằng nhau Gợi ý: sinh toàn bộ tổng của tất cả các dãy con của a: sa và tương tự với b: sb bài toán quy về việc: cho hai dãy sa và sb: với mỗi giá trị trên sa[1], sa[2]..., sa[n^2]: Tìm xem có bao nhiêu giá trị bằng với phần tử đó trên hai dãy Bài 10.Xây kho thóc • Ta chặt nhị phân số lượng cánh đồng vận chuyển được vì nếu vận chuyển được mid cánh đồng sẽ tồn tại cách vận chuyển được mid-1 cánh đồng. • Tức bài toán của ta bây giờ là có thể vận chuyển mid cánh đồng với chi phí không quá K đồng. Thì đương nhiên nếu có ta sẽ chọn mid kho cánh đồng tiếp (gần nhau nhất). Nhưng với mid cánh đồng thì ta chọn vị trí kho thóc như nào để tối thiểu chi phí nhất. Thật ra đó chính là vị trí cánh đồng trung vị (Cánh đồng ở chính giữa) • Chứng minh: giả sử đặt kho thóc ở 1 vị trí bất kì bên trái nó sẽ có x cánh đồng thì bên phải sẽ có mid-x thì nếu ta di chuyển sang phải thì ta sẽ gần với các cánh đồng bên phải hơn mid-x đơn vị và xa các cánh đồng bên trái x đơn vị. Thì đương nhiên ta chọn bên nhiều cánh đồng hơn để giảm chi phí. Hay lúc nó dừng lại thì 2 bên có cùng số lượng cánh đồng (đây là số trung vị của dãy) mà vì ta đã sắp xếp lại nên nó chính là số chính giữa • Khi đã có vị trí kho thóc tối ưu ta sẽ tính được chi phí nhỏ nhất trong O(1) bằng mảng cộng dồn. Và kiếm tra xem chi phí này có quá K không

Ngày 23/9/2025: Luyện tập

Bài 1. Đếm số lượng số chia hết cho 3 hoặc 5 trong khoảng từ 1 đến n. Gọi A là tập hình oval bên trái, B là tập hình oval bên phải A + B thì phần màu vàng + màu xanh và 2 lần phần màu đỏ (do màu đỏ được tính 1 lần trong A và 1 lần trong B) |A ∪ B| = |A| + |B| - |A ∩ B| |A| = n/3 (tập các số chia hết cho 3 trong khoảng từ 1 -> n) |B| = n/5 (tập các số chia hết cho 5 trong khoảng từ 1 đến n) KQ = n/3 + n/5 - n/15 Bài 2: Canh gác: Có 2 con chó: 1 con chó thức khoảng thời gian là a phút rồi ngủ b phút -> Trong 1 đoạn có độ dài a + b: thì nửa đầu nó thức còn nửa sau nó ngủ Vậy ta sẽ tính xem tại thời điểm P: tương ứng nó nằm trong đoạn có độ dài a phía đầu hay độ dài b phía sau bằng cách tính P %(a + b): P = P %(a + b) Nếu (P >= 1 and P <= a) -> con chó đang thức ngược lại con chó đang ngủ

Bài chọn điểm: A(3, 1) B(8, 1) C(8, 5) D(3, 5) Gióng theo cột 1: tọa độ 3 xuất hiện ở điểm A và D tọa độ 8 xuất hiện ở điểm B và C Gióng theo cột 2: tọa độ 1 xuất hiện ở điểm A và B tọa độ 5 xuất hiện ở điểm C và D Nếu khuyết 1 điểm: A(3, 1) B(8, 1) D(3, 5) -> Điểm bị thiếu sẽ có tọa độ x = số nguyên mà xuất hiện 1 lần trong các x -> điểm bị thiếu sẽ có tọa độ y = số nguyên mà xuất hiện 1 lần trong các y. Bài vẽ đường tròn Cần vẽ 1 hình tròn với bán kính nhỏ nhất có thể chứa số điểm đen = số điểm trắng. -> khi ta vẽ đường tròn tăng dần bán kính lên thì khi “chạm” vào 1 điểm mà thỏa mãn được số điểm đen = số điểm trắng sẽ tốt hơn là đường tròn ko chứa điểm nào -> bán kính của đường tròn cần tìm chính là độ dài từ (0,0) đến 1 điểm đã cho. Khi đó, giả sử bán kính đến điểm M(x, y): sqrt(x^2 +y^2) Cần tính được khoảng cách của mọi điểm đã cho đến điểm O(0, 0), và mỗi điểm có 2 màu đen/trắng Ta sẽ sử dụng pair<int, int> để lưu thông tin về 1 điểm. ta có tất cả 2*n điểm như vậy sort lại rồi xét lần lượt từ đầu đến cuối dãy và tính các điểm nằm trong hình tròn xem cân bằng số điểm đen và trắng hay chưa. Bài Số đặc biệt: Nhắc lại kiến thức về ước số: Để liệt kê các ước của 1 số: for(int i = 1; i <= n; i++) if(n % i == 0) cout << i; Cải tiến: nhận xét: a là ước của n thì a * b = n -> b = n/a cũng là ước (a, n/a) là 1 cặp ước. a * b = n thì giả sử a <= b khi đó a <= căn(n) và b >= căn(n) (gợi ý: CM phản chứng giả sử cả a và b đều nhỏ hơn căn(n) và tương tự với cặp a, b >= căn(n)) for(i = 1-> sqrt(n)) if(n % i == 0) cout << i và n/i *Lưu ý với số n là số chính phương

Dựa trên 2 nhận xét trên: ta sẽ đi for(a = 1-> căn(n)) kiểm tra xem i và i + 1 có là ước của n hay không? -> làm thế này ta có 60 điểm

n = a * b n = 60: 1 2 2 3

Cải tiến: Ta cần tìm các số x sao cho n % (x * (x + 1)) == 0 (vì x và x + 1 nguyên tố cùng nhau nên n % x == 0 && n % (x + 1) == 0 khi và chỉ khi n % (x * (x + 1)) == 0) Duyệt từ 1 → sqrt(n) là quá lớn khi n lên đến 1e18 → Ta cần nghĩ cách để chỉ duyệt đến cbrt(n) thôi Nhận xét: Trường hợp 1: x <= cbrt(n) → x * (x + 1) <= n^(⅔) → Ta có thể duyệt trực tiếp và kiểm tra Trường hợp 2: x > cbrt(n) → x * (x + 1) > n ^ (⅔) Ta gọi n / (x * (x + 1)) = i → n % i == 0 Mà x * (x + 1) > n ^ (⅔) → i < n ^ (⅓) → i < cbrt(n) → Tồn tại 1 ước i < cbrt(n) sao cho n / i = x * (x + 1) → Ta duyệt hết các ước i < cbrt(n) và kiểm tra xem n / i có phải tích 2 số liên tiếp hay không

Ngày 16/9/2025: Luyện tập xâu kí tự Xử lý xâu s: sử dụng các hàm có sẵn: s.length(), s.substr(), resize()....

Bài 1: Tìm tên Đọc vào xâu đến kí tự thứ i mà trước đó là nguyên âm -> bỏ nó đi Tính điểm Quy tắc điểm: mỗi C được điểm bằng số câu trả lời đúng liên tiếp kết thúc ở chính câu này. Mỗi N cho 0 điểm và làm đứt chuỗi đúng liên tiếp. → Ý tưởng: Ta sẽ duyệt hết xâu từ trái qua phải, duy trì 2 biến: • cnt: số c liên tiếp hiện tại (nếu gặp c thì cnt tăng, gặp n thì đặt lại cnt = 0) • total: tổng điểm cộng dồn (tính bằng tổng tất cả cnt ở mọi vị trí) → Hay nói cách khác, việc ta cần làm là duyệt hết cả xâu • Mỗi khi gặp c: cnt++ rồi total += cnt • Mỗi khi gặp n: cnt = 0

Đếm kí tự Để đếm số lần xuất hiện của mỗi kí tự, ta có thể tạo một mảng đếm cnt[26] để đếm số lần xuất hiện của các kí tự từ ‘A’ → ‘Z’ Ví dụ: cnt[0] = số lần xuất hiện của A, cnt[1] = số lần xuất hiện của B, … Duyệt cả xâu, tăng đếm cho kí tự tương ứng Ví dụ: mỗi khi gặp 1 kí tự s[i] thì ta cho cnt[s[i] - ‘A’]++ (s[i] - ‘A’ là để tìm ra vị trí của s[i] trong bảng chữ cái, với s[i] = ‘A’ thì s[i] - ‘A’ = 0, s[i] = ‘B’ thì s[i] - ‘B’ = 1, …)

Bài 2: Mạch DNA 12A123G1T4A 1: m = 1 2: m = 1 * 10 + 2 3: m * 10 = 12*10+ 3 = 123 xét i = 0-> s.size() s[i] = 0->9 là kí tự số:

Thi đua Đề bài yêu cầu ta đếm số chuỗi liên tiếp mà năng lực của 3 bạn bằng nhau Ý tưởng: Sử dụng mảng cộng dồn: Gọi: • cntA[i] = số chữ A trong đoạn [1..i] • cntN[i] = số chữ N trong đoạn [1..i] • cntM[i] = số chữ M trong đoạn [1..i] → Số chữ A trong đoạn là L.. R là cntA[R] - cntA[L - 1] Tương tự với N và M Vậy 1 đoạn con L→R thỏa mãn khi: • cntA[R] - cntA[L - 1] = cntN[R] - cntN[L - 1] • cntA[R] - cntA[L - 1] = cntM[R] - cntM[L - 1] → (cntA[R] - cntN[R]) = (cntA[L-1] - cntN[L-1]) (cntA[R] - cntM[R]) = (cntA[L-1] - cntM[L-1]) Đặt x[i] = cntA[i] - cntN[i], y[i] = cntA[i] - cntM[i] Khi đó đoạn L..R thỏa mãn khi (x[R], y[R]) = (x[L - 1], y[L-1]) → Bài toán trở thành, với mỗi i, ta đếm xem có bao nhiêu j thỏa mãn sao cho (x[i],y[i]) = (x[j],y[j]) → Sử dụng kĩ thuật mảng đánh dấu để lưu lại số lần xuất hiện của cặp (x[i], y[i]) Ở đây để lưu được số theo dạng cặp như này ta nên dùng map<pair>:

Khối lượng phân tử Ý tưởng tương tự bài mạch DNA, mỗi khi gặp 1 chuỗi số ta sẽ lưu 1 biến res để chuyển chuỗi số đó sang dạng int, đồng thời lưu lại phân tử hóa học trước chuỗi số đó để thực hiện phép nhân tính khối lượng phân tử Ví dụ: với N2, ta sử dụng 1 biến res để lưu lại số 2 theo dạng int như bài DNA, đồng thời dùng 1 biến c để lưu lại chữ cái ‘N’ → Khi đó khối lượng phân tử chúng ta sẽ được là ans += 14 * res Nhớ thay đổi số nhân với mỗi chữ cái khác nhau nhé H = 1, O = 16, N = 14, C = 12

Đếm xâu con Sử dụng ý tưởng mảng cộng dồn như bài thi đua, ta gọi cnt[i] là số lượng '1' trong s[1..i] (chỉ số từ 1) → Để xâu từ L đến R có đúng k số 1, ta cần cnt[R] - cnt[L-1] = k hay cnt[R] - k = cnt[L-1] → Với mỗi i, ta cần đếm số số j thỏa mãn cnt[i] - k = cnt[j] → Đếm số lần xuất hiện của cnt[i] - k Đến đây thì lại trở thành 1 bài toán quen thuộc sử dụng kĩ thuật mảng đánh dấu

Bài 3: Simple Math UEOAI s = “UEOAI” i 0 1 2 3 4 5
sum 0 1 2 3 4 5

Để xét và tính số lượng nguyên âm từ i -> j: res += (sum[j] - sum[i - 1])/(j - i+1) Ví dụ 2: s = “saesdetifsa”

i 0 1 2 3 4 5 6 7 8 9 10 11 a 0 0 1 2 2 2 3 3 4 4 4 5 res = 0; for(int i = 1-> n) for(int j = i -> n) res += 1.0*(a[j] - a[i - 1])/(j - i + 1); cout << res; Cải tiến: Cần đưa về sử dụng các kiến thức về mảng cộng dồn +TKNP Cải tiến: Gọi H[i] là tổng tất cả phân số từ 1/1 → 1/i H[i] = 1/1 + ½ + ⅓ + … + 1/i (tính bằng mảng cộng dồn) • Giả sử s[k] là nguyên âm. • Khi đó, trong mọi đoạn con chứa S[k], nó đóng góp 1 / (độ dài đoạn) vào độ đẹp. • Một xâu con từ L → R chứa s[k] thì phải thỏa mãn tính chất: L <= k <= R • Khi đó, s[k] đóng góp 1 / (R - L + 1) độ đẹp vào xâu [L, R] → Với mỗi s[k], ta cần tính lượng đóng góp mà nó tham gia vào tổng độ đẹp Gọi lượng đóng góp đó là beauty[k] beauty[k] = L = 0kR = kn - 11R - L + 1 Tách công thức: Cố định L ta có R = kn - 11R - L + 1 = t = k - L + 1n - L1t = H[n - L] - H[k - L]

→ beauty[k] = L = 0k(H[n - L] - H[k - L]) = L = 0kH[n - L] - L = 0kH[k - L] = j = n - knH[j] - j = 0kH[i]

Ta tạo thêm 1 mảng HH[i] = tổng các h[i] từ i = 1 → i HH[i] = h[1] + h[2] + … + h[i] (tính bằng mảng cộng dồn)

→ beauty[k] = HH[n] - HH[n - k - 1] - HH[k] → Vậy việc còn lại của ta chỉ là tính k = 0n - 1beauty[k] là ra đáp án .Bài 4: i -> j: sl(N) == sl(A)== sl(M)

(Khóa 2 - Buổi 1): Luyện tập xâu ký tự

• Xâu ký tự nằm trong thư viện string

include <string>

using namespace std;

string a, b; cin >> a >> b;

abc cba

string s; getline(cin, s);

Bài đếm số từ • Để đọc tất cả các từ, dùng while (cin) thay vì getline(cin) Bài Chó nâu • Bản chất các chữ là số (a -> 97, b->98, … => Vị trí trong bảng mã ascii) • ‘c’ - ‘a’ = 2 • ‘z’ - ‘a’ = 25 • Xâu là mảng các ký tự (char) đánh số từ 0 • s[0], s[1], …, s[s.size() - 1] • Sử dụng mảng đánh dấu để biết mỗi ký tự ‘a’, ‘b’, …, ‘z’ có xuất hiện hay không Bài xâu đối xứng • Kiểm tra điều kiện: • s[0] == s[s.size() - 1] • s[1] == s[s.size() - 2] • … • s[i] == s[s.size() - 1 - i] • Nếu có một điều kiện không thỏa mãn thì quit In hoa • Xử lý từng ký tự: Duyệt từng ký tự từ trái sang phải • Nếu si là chữ hoa: if (s[i] >= ‘A’ && s[i] <= ‘Z’) • Nếu si là chữ thường: if (s[i] >= ‘a’ && s[i] <= ‘z’) Thứ tự từ điển • C++ cài sẵn phép so sánh >,<, =:

string s, t; if (s < t) … else … SO sánh • Số có nhiều chữ số hơn thì to hơn • Hai số có cùng số lượng chữ số => So sánh thứ tự từ điển Xâu nguồn • Nếu s là xâu con của t => Số ký tự cần xóa là t.size() - s.size() • Kiểm tra: • Tìm vị trí xuất hiện của s[0] • Sau vị trí này, tìm vị trí xuất hiện s[1] • Sau vị trí đó, tìm vị trí xuất hiện của s[2] • … • Nếu tìm được tất cả, khẳng định s là con t Ghép số • a đứng trước b nếu ghép a vào b > ghép b vào a: • VD: 123 46 • 46123 > 12346 • Coi mỗi số là 1 xâu ký tự => Dãy các xâu ký tự: string s[N]; • Sắp xếp dãy s, cần viết lại hàm compare • compare(string x, string y): (x + y) > (y + x); Đếm số lần xuất hiện • Hàm substring: s.substr(i, c) là c ký tự từ phần tử thứ i • s = “abcdef”, s.substr(2, 3) = “cde” • Duyệt mọi vị trí i: s.substr(i, y.size()) == y Số lớn thứ K • Bản chất xâu là một dãy ký tự (char) => sort được • string s; sort(s.begin(), s.end());

(Khóa 1 - Buổi 9): Luyện tập chung Bài Đặt phòng cout<<a+b/3+(b%3!=0);

Bài Số phong phú Xây dựng hàm tính tổng các ước của một số a nào đó. Duyệt từ L đến R và kiểm tra từng số.

Bài Tam giác vuông Công thức Pitago Bình phương cạnh huyền bằng tổng bình phương hai cạnh góc vuông. a^2 + b^2 = c^2 Công thức tính diện tích tam giác vuông S = ½ab -> 2S = ab Giả sử a < b. Duyệt a từ 1 đến sqrt(2S) -> tìm được 1 giá trị b = 2S/i Chương trình chính

Bài Số chính phương Các số chính phương là: 1^2 + 2^2 + 3^2 + …+ k^2 = k(k+1)(2k+1)/6 gần bằng k^3/3 Xây dựng tổng cộng dồn sum[] để lưu tổng từ 1 đến 2*10^6. Bài Xâu chính phương

Bài Dãy số • Xây dựng mảng tổng cộng dồn sum[] để tính tổng các phần tử, và chan[] để tính số lượng phần tử chẵn • Dùng cửa sổ trượt sliding window để xét từng đoạn kích thước k Bài Xóa số nguyên tố • Sàng nguyên tố, tạo một mảng đánh dấu các số nguyên tố •
• Sau đó duyệt lần lượt từng phần tử. Phần tử nào không phải SNT thì tính tổng và đưa vào 1 mảng hoặc 1 vector

Bài Vị trí đẹp • Xây dựng hàm kiểm tra nguyên tố. • Duyệt từ 1 đến n.

(Khóa 1 - Buổi 8): Tối ưu thuật toán Bài Tìm số Bước 1: Cài hàm tính số lượng các số chia hết cho a, b trong đoạn từ 1 đến x. Bước 2: vì các số trong dãy tăng dần, ta sẽ tiến hành tìm kiếm nhị phân trong đoạn từ 1 đến 10^18 để tìm vị trí thứ n. Code đầy đủ:

Bài Tổng chính phương Giải pháp 1: Cài nhị phân, • Sắp xếp lại dãy tăng dần. • Duyệt từ 1 đến n để kiểm tra Giải pháp 2. Dùng mảng đánh dấu.

Bài Dãy lego hoàn hảo dãy vị trí từ 1 đến n. Ta có nhận xét, nếu giảm a[1] (số đầu tiên của dãy), không ảnh hưởng đến dãy . a[1]--; Duyệt từ 2 đến n. • Nếu a[i] < a[i-1] thì in ra “No” và return 0; kết thúc chương trình. • Nếu a[i] > a[i-1] thì a[i]-- Nếu cuối vòng for mà chưa return 0 thì kết luận “Yes”

Bài Khoảng cách 100 = 2^2 * 5^2 = 100/20 = 5 = 5^1 360 = 2^3 * 3^2 * 5^1 = 18 = 2 =2^1 * 3^2 Để biến 100 thành 360: 100/5 * 2 * 3 * 3 Ta thấy tổng số phép tính bằng tổng số mũ của các thừa số nguyên tố sau khi chia cho UCLN(a,b): 1 + 1 + 2 Hàm tính tổng số mũ của các thừa số nguyên tố. Duyệt từng test: Nhập a, b -> tìm x = __gcd(a,b) -> in ra check(a/x) + check(b/x) Bài Tìm giữa (Hà Nội 20 - 21) • Công thức tính tổng từ l đến r = (l+r)(r-l+1)/2 • Tổng từ 1 đến l -1 = l (l -1)/2 Tổng các số từ 1 đến = M * (M+1)/2 Nếu sử dụng công thức sấp xỉ để tính M thì M gần bằng long long 2sqrt(total(l, r) / 2 + total(1, l - 1)) Giải pháp 2. Tìm kiếm nhị phân trong đoạn [l, r] Tìm vị trí M để độ chênh lệch nhỏ nhất.

Bài Hoán vị số (Hà Nội 20-21) Nhận xét: N để chia hết cho 30 phải thỏa mãn 2 điều kiện: tổng các chữ số chia hết cho 3 và có chữ số cuối cùng = 0; Ta nên xử lí bài toán dưới dạng nhập xâu số N.

(Khóa 1 - Buổi 7): Luyện tập Bài Khuyến mãi • Giải pháp 1: Nếu xử lí bằng số học thì phạm vi của n chỉ đạt tối đa gần 10^19 • Giải pháp 2: xử lí bằng string. • Duyệt từ 0 đến s.length()-1 sum += s[i] - ‘0’; Bài Phân tích số • Phân tích từng thừa số nguyên tố xuất phát từ 2 và đếm. •
Bài Số lớn thứ K • Sử dụng mảng đánh dấu a để đánh dấu từng chữ số xuất hiện, sau đó tạo mảng b chỉ chứa các phần tử có giá trị > 0 trong mảng a. • Sắp xếp lại mảng b, và đưa ra vị trí (số lượng ptu của b - k) Ví dụ: n = 7853 mảng a[0->9]=0 mảng đánh dấu a: a[3]=true; a[5]=true; a[7]=true; a[8]=true tạo mảng b: b[0]=7; b[1]= 8; b[2]=5; b[3]=3 (7, 8, 5, 3) Sắp xếp lại b(3,5,7,8) vị trí số lớn thứ k là: b[4-3] = 5

(Khóa 1 - Buổi 6): Luyện tập Tìm kiếm nhị phân Bài Tìm kiếm nhị phân

Bài Đếm cỏ Bài Tổng số chính phương Bài Cấp số cộng (Khóa 1 - Buổi 5): Thuật toán tìm kiếm nhị phân Bài Phần tử trung bình duyệt i từ 2 đến n -1 nếu (2a[i] = a[i-1] + a[i+1]) thì dem++; Bài Tổng chẵn • đếm số lượng chữ số chẵn. chan • đếm số lượng chữ số lẻ. le ta có số cặp là: long long res = 1LL(chan(chan-1)/2) + 1LL(le(le-1)/2) Bài Phát quà tìm K = __gcd(X,Y) Ta đi tính tổng các ước của K. Bằng cách phân tích K thành các thừa số nguyên tố, tích của các (số mũ + 1) của các thừa số nguyên tố là số ước cần tìm. VD: K = 2^a3^b5^c -> số ước = (a+1) (b+1)(c+1) Bài Số đẹp 2

Bài Tìm kiếm nhị phân Cách 1: Cài đặt cơ bản Cách 2: dùng lower_bound tìm vị trí đầu tiên >= v Bài Lễ hội bánh dân gian • Tính mảng cộng dồn số tiền dùng tại các cửa hàng. • Tiến hành tìm kiếm nhị phân vị trí đầu tiên lớn hơn t. lấy vị trí đó trừ đi vị trí đầu tiên. Bài Đếm cặp giá trị tìm kiếm mỗi lần là a[i]-k Bài Bé Tuệ gọi x là số quà lớn nhất trong tất cả các màu: ví dụ 4 quà đỏ, 7 quà xanh, 5 quà tím => x = 7 ta có nhận xét: đáp án sẽ chỉ trong khoảng: 1 -> x Gọi đáp án là ans: => từ 1 -> ans - 1: ko thể có cách chia quà từ ans -> x: luôn chia được(do chỉ cần chia theo cách trong trường hợp ans) => ta chặt nhị phân đáp án: l = 1, r = x => mid = (l + r) / 2 => ta chia từng màu ra thành các phần quà, mỗi phần gồm x món quà ví dụ: 7 món quà màu đỏ, mid = 2 => chia thành 2 2 2 1 => 4 phần quà sau đó ta tính tổng sum tất cả số phần quà nếu sum <= n => r = mid - 1 else l = mid + 1 Bài Phố đi bộ

Bài

Contest: (Khóa 1 - Buổi 4): Thiết kế thuật toán cơ bản Bài Tam giác Hướng dẫn: • Nếu A+B+C!=180 -> KHONG • Nếu A=90 hoặc B=90 hoặc C=90 -> VUONG • Nếu A>90 hoặc B>90 hoặc C>90 -> TU • Sai -> NHON Bài Nhà toán học tài ba Hướng dẫn: – Sàng nguyên tố tìm danh sách các số nguyên tố. • Sắp xếp lại mảng A. • Duyệt lần lượt từng phần tử, nếu gặp số nguyên tố thì giảm dần k. Nếu k = 0 thì dừng và in ra A[i] • Nếu k >0 in ra -1 Bài Tổng K HD: Sắp xếp lại dãy theo thứ tự tăng dần. Duyệt từng phần tử int s = 0, cnt = 0; for (int i = 0; i < n; i++) { if (s + a[i] <= k) { s += a[i]; cnt++; } else { break; } } if (cnt == 0 && k < 0) { cout << -1; } else { cout << cnt;

Bài Đếm số trong xâu Ý tưởng: Lấy từng nhóm chữ số, cho vào mảng đánh dấu. s += 'A'; int cur = 0; for (int i = 0; i < s.size(); i++) if (s[i] >= '0' && s[i] <= '9'){ cur = cur * 10 + s[i] - '0'; } else if (cur > 0) { mark[cur]++; cur = 0; } Bài Chênh lệch nhỏ nhất Ý tưởng: Có thể 2 con trỏ • Sắp xếp hai dãy A và B tăng dần. int i = 0, j = 0, res = LLONG_MAX; while (i < m && j < n) { res = min(res, abs(a[i] - b[j])); if (a[i] < b[j]) { i++; } else { j++; } } Bài Siêu nguyên tố

Bài Biến đổi dãy số (CSEQ) Ý tưởng: • Tìm đoạn nhỏ nhất (số âm nhất có thể): Cách làm: sum = 0
for i 1->n: sum += a[i] nếu sum > 0: sum = 0 Ta tìm được X là đoạn nhỏ nhất. S là tổng tất cả các phần tử. Thì ta công thức: S - X(- X) = S - 2.X Bài Mua quà Ý tưởng: • Sắp xếp. • Dùng sliding window để tìm đoạn nhỏ nhất int res = 1e18; for (int i = 1; i <= n - k + 1; i++) { res = min(res, a[i + k - 1] - a[i]); } Contest: (Khóa 1 - Buổi 3): Ngày 1/7/2025 Bài 5: Rải sỏi • Suy nghĩ đơn giản: for trâu từ điểm x, đi từng ô 1 và tăng giá trị lần lượt => chậm Cải tiến: sử dụng mảng cộng dồn: muốn tăng 1 đoạn từ a[l] đến a[r] lên 1 đơn vị, ta tăng mảng cộng dồn tương ứng b[l] lên 1 và b[r + 1] giảm 1:

0   1   2   3   4   5   6   7   8

a +1 +1 +1 +1 +1
b +1 -1
Ví dụ tăng từ a[2] đến a[6] lên 1 đơn vị, ta tăng b[2] lên 1, giảm b[6] đi 1 => áp dụng vào đường tròn: Ta chia làm 3 trường hợp • TH1: đi hết 1 vòng: tăng b[0] lên 1, không giảm ở đâu cả => cả vòng tăng • TH2: đi trong vòng (ví dụ đi từ điểm 2 -> 6), làm như ví dụ trên • TH3: đi vượt vòng (ví dụ đi từ điểm 7 về điểm 3): ta cắt đôi ra rồi tăng như bình thường(ta tăng từ 7->8 rồi tăng từ 0 -> 3) Contest: (Khóa 1 - Buổi 2): Ngày 1/7/2025 Bài 1 Số đẹp Tính tổng s là các chữ số sau đó nếu s%9 =0 thì đó là số đẹp. Bài 2 Chia hết Số lượng các số trong khoảng từ 1 đến N chia hết cho a hoặc b bằng: n/a + n/b - 2*(n/lcm(a,b))

Bài 3 Cặp số bằng nhau Tạo mảng đánh dấu cho mảng a for (int i = 1; i<=n; i++) { cin >> x; a[x]++; } for(int j = 1; j<=m; j++) { cin >> x; res+= a[x]; } Bài 4 Số có 3 ước ý tưởng: • Dùng sàng nguyên tố. • duyệt từng phần tử a[i], kiểm tra a[i] có phải số chính phương không và sqrt(a[i]) có phải số nguyên tố không. Bài 5 Số đặc biệt 2 Sàng nguyên tố Duyệt lần lượt từng a[i], kiểm tra ll r = sqrt(a[i])) Bài 6 Kho báu

Bài 7 Chuỗi thu gọn

Contest: (Khóa 1 - Buổi 1): Ngày 24/6/2025 Bài 1 Chạy bộ x27 Bài 2 Tiền điện if (k <= 100) { tong = k * 650; } else if (k <= 150) { tong = 100 * 650 + (k - 100) * 1250; } else if (k <= 200) { tong = 100 * 650 + 50 * 1250 + (k - 150) * 1580; } else { tong = 100 * 650 + 50 * 1250 + 50 * 1580 + (k - 200) * 1790; } double tien = tong * 1.10; cout<<fixed<<setprecision(2)<<tien;</p>

Bài 3 Số nút Cách 1: Lặp lại tính tổng các chữ số cho đến khi n<10 thì dừng lại. while (n > 9) { int total = 0; while (n > 0) { total += n % 10; n /= 10; } n = total; } Cách 2: 1+(n-1)%9 Bài 4 Quà sinh nhật Dùng mảng đánh dấu. Mẫu. Code Lê Bảo Nam phần đánh dấu. int dem[13] = {}; for (int i = 0; i < n; ++i) { int t; cin >> t; dem[t]++; } Sau đó duyệt mảng dem. nếu dem[i]>0 thì in ra i và dem[i]. Bài 5 Số đặc biệt Hàm kiểm tra số nguyên tố bool isPrime(long long n) { if (n < 2) return false; for (long long i = 2; i * i <= n; ++i) if (n % i == 0) return false; return true; }

Hàm tính tổng bình phương các chữ số. long long sumOfSquareOfDigits(long long n) { long long sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; }

Bài 6 Bộ ba số Cách 1: Dùng hai con trỏ. B1. Sắp xếp lại mảng theo thứ tự tăng dần B2. Duyệt lần lượt từng a[k] (k chạy từ 0 đến n - 1) Duyệt các cặp a[i], a[j] (với i = 0, j = k-1) luôn đảm bảo a[i]<a[j]<a[k] sort(a.begin(), a.end()); // sort to use two pointers</p>

int count = 0;

for (int k = 0; k < n; ++k) {
    int target = a[k];
    int i = 0, j = k - 1;

    while (i < j) {
        int sum = a[i] + a[j];
        if (sum == target) {
            ++count;
            ++i;
            --j;
        } else if (sum < target) 
            ++i;
         else 
            --j;
    }
}

Cách 2 (Nguyễn Huy Bách - Mảng đánh dấu) Đánh dấu xuất của từng phần tử a[i]. Duyệt i,j nếu check[a[i] + a[j]] thì dem++ for (int i = 0; i < n; ++i) { cin >> a[i]; check[a[i]] = true; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (a[i] + a[j] <= 1000000000) { if (check[a[i] + a[j]]) ++cnt; } } }

Bài 7 Xóa kí tự Hướng dẫn:

Bài 8 Tổng mũ chẵn lẻ Hướng dẫn:

Bài 9 Chuyển chữ số