Nhật ký lập trình

BOOKSORT

Dạng bài này thường được gọi là “Move-to-Front Sorting”.

• Dấu hiệu nhận biết: Bài toán cho phép chọn một phần tử và đưa về đầu (hoặc cuối) và hỏi số bước tối thiểu để sắp xếp.

• Nếu đưa về Đầu: Tìm dãy con tăng dần dài nhất kết thúc bằng giá trị lớn nhất (Suffix của dãy đích).
• Nếu đưa về Cuối: Tìm dãy con tăng dần dài nhất bắt đầu bằng giá trị nhỏ nhất (Prefix của dãy đích).

int main(void) {
    int n; cin >> n;
    int A[n + 1];
    FOR(i, 1, n + 1) {
        cin >> A[i];
    }
    int target = n;
    int fixed = 0;
    for(int i = n; i >= 1; i--) {
        if(A[i] == target) target--, fixed++;
    }
    cout << n - fixed;
}

GCD

Ta cần một cách tính GCD nhanh hơn cho mỗi $b_j$, lý tưởng nhất là $O(\log(\text{giá trị}))$ thay vì $O(n)$.

Tính chất quan trọng nhất của GCD là:

\[GCD(x, y) = GCD(x, y - x)\]

Mở rộng ra nhiều số:

\[GCD(x_1, x_2, x_3, \dots, x_n) = GCD(x_1, x_2 - x_1, x_3 - x_1, \dots, x_n - x_1)\]

Áp dụng vào bài toán, với mỗi $b_j$:

\[G_j = GCD(a_1 + b_j, a_2 + b_j, a_3 + b_j, \dots, a_n + b_j)\] \[G_j = GCD(a_1 + b_j, (a_2 + b_j) - (a_1 + b_j), \dots, (a_n + b_j) - (a_1 + b_j))\] \[G_j = GCD(a_1 + b_j, \mathbf{a_2 - a_1, a_3 - a_1, \dots, a_n - a_1})\]

Nhận xét quan trọng: Các hiệu số $a_i - a_1$ hoàn toàn không phụ thuộc vào $b_j$. Chúng ta có thể tính GCD của các hiệu này một lần duy nhất!

Kinh nghiệm rút ra:

Khi gặp bài toán yêu cầu tính GCD của một dãy số bị biến đổi (cộng cùng một số, hoặc truy vấn đoạn), hãy nhớ:

1. Dùng hiệu (Difference): GCD của một tập hợp bằng GCD của (một phần tử) và (tập hợp các hiệu giữa các phần tử còn lại với nó).

2. GCD và giá trị tuyệt đối: $GCD(a, b) = GCD(a,

   b

   )$. Khi tính hiệu $a_i - a_1$, kết quả có thể âm, hãy lấy abs.

3. Trường hợp đặc biệt: Nếu $n=1$, GCD chính là $

   a_1 + b_j

   $.

ll gcd(ll a, ll b) {
    if(b == 0) return llabs(a); // xử lý số âm!
    return gcd(b, a % b);
}
int main(void) {
    int n, m; cin >> n >> m;
    ll A[n + 1], B[m + 1];
    FOR(i, 1, n + 1) {
        cin >> A[i];
    }
    FOR(j, 1, m + 1) {
        cin >> B[j];
    }
    ll pre = A[2] - A[1];
    FOR(i, 3, n + 1) {
        pre = gcd(pre, A[i] - A[i - 1]);
    }
    FOR(j, 1, m + 1) {
        if(n == 1) {
            cout << llabs(A[1] + B[j]) << ' ';
        } else {
            ll res = llabs(A[1] + B[j]);
            cout << gcd(res, pre) << ' ';
        }
    }
}

NUM13

Đề bài tóm tắt:

• Tìm số có đúng $n$ chữ số.
• Chia hết cho 13.
• Không chứa chữ số 1 và 3.
• $n$ lên tới $10^5$, kết quả chia dư cho $10^9 + 7$.

Subtask 1 ($n$ nhỏ, ví dụ $n \le 7$):

• Tư duy: Duyệt trâu (Brute force) hoặc Đệ quy quay lui để sinh các số thỏa mãn.
• Hạn chế: Số lượng số cần xét là $10^n$, quá lớn khi $n$ tăng.

Subtask 2 ($n \le 10^5$): Quy hoạch động (DP)

• Tư duy: Ta xây dựng số bằng cách thêm từng chữ số từ trái sang phải.
• Trạng thái: Để biết một số có chia hết cho 13 hay không, ta chỉ cần quan tâm đến số dư của nó khi chia cho 13.
• Gọi: $dp[i][rem]$ là số lượng số có $i$ chữ số mà khi chia cho 13 dư $rem$.
• Tập chữ số hợp lệ: $S = {0, 2, 4, 5, 6, 7, 8, 9}$ (loại bỏ 1 và 3).
• Điều kiện số có $n$ chữ số: Chữ số đầu tiên (vị trí 1) không được là số 0.

GIFTS

Sweepline 1D: +1 $\to$ -1 $\to$ -2 (query)

BIRTHDAY

Khi gặp một bài toán có “quy trình tráo đổi” hoặc “di chuyển” với giới hạn $n$ cực lớn ($10^{12}, 10^{18}$):

1. Luôn thử với $n$ nhỏ: Viết một hàm mô phỏng (Brute-force) để tìm ra 10-20 kết quả đầu tiên.
2. Tìm Invariant (Vật bất biến) hoặc Sequence (Dãy số): Kiểm tra xem kết quả có rơi vào các dãy đặc biệt không (Số chính phương, lũy thừa của 2, số Fibonacci, số nguyên tố…).
3. Tư duy tham lam/quy hoạch động: Nếu vị trí hiện tại là $P$, bước tiếp theo quả cherry sẽ nhảy đến đâu? Nếu bước nhảy có quy luật nhân/cộng cố định, đó là chìa khóa.

CONTEST

1. Hai mảng đã được sắp xếp (hoặc có thể sắp xếp) + Cần so sánh/ghép cặp: $\to$ 90% là dùng Hai con trỏ (Two Pointers) hoặc Tham lam (Greedy).
2. Thao tác “thêm/xóa làm thay đổi toàn bộ mảng”: $\to$ Đừng mô phỏng (simulate) thao tác đó. Hãy tìm bất biến hoặc xem xét trạng thái cuối cùng của mảng. Ở bài này, trạng thái cuối là: phần tử cũ bị dịch đi, phần tử lớn bị văng ra.
3. Bài toán hỏi “số thao tác tối thiểu”: $\to$ Thường tương đương với việc tìm “số phần tử lớn nhất không cần thao tác” (ở đây là số bài cũ tối đa giữ lại được).

DOLLS

Dạng bài này thường được gọi là Greedy Pairing (Ghép cặp tham lam). Các dấu hiệu nhận biết:

• Yêu cầu tối ưu tổng, hoặc tối ưu số lượng vật dụng.
• Có điều kiện ràng buộc giữa hai đối tượng (ở đây là $a_i + k \le a_j$).
• Đối tượng này có thể “chứa” hoặc “thay thế” đối tượng kia theo một chuỗi.

Pattern giải quyết:

1. Sắp xếp: Luôn là bước đầu tiên. Tùy bài mà xếp tăng hay giảm.
2. Quản lý đối tượng đợi: Sử dụng queue (nếu chỉ cần so sánh với con lớn nhất/nhỏ nhất) hoặc multiset (nếu cần tìm một con cụ thể thỏa mãn điều kiện).
3. Duyệt một lần: Biến bài toán từ $O(N^2)$ về $O(N \log N)$ hoặc $O(N)$.

CDSUBSEG

Binary Search / Hai con trỏ (Two Pointers) + Sparse Table (GCD)

Tính chất: Nếu $GCD(a_i, \dots, a_j) > 1$, thì khi ta mở rộng đoạn sang phải, GCD chỉ có thể giữ nguyên hoặc giảm đi. Khi ta thu hẹp đoạn, GCD tăng lên hoặc giữ nguyên. Đây là tính chất đơn điệu.

LƯU Ý: Trong toán học, số $0$ là một trường hợp đặc biệt. Với mọi số nguyên $d > 1$, ta luôn có $0$ chia hết cho $d$ (vì $0 = d \times 0$).

• Nếu đoạn con là ${0, 0, 0}$, thì bất kỳ $d > 1$ nào (như $d=2, d=3, d=10^9$) đều là ước chung hợp lệ.

• Kết luận: Đoạn toàn số $0$ là đoạn cực kỳ “thỏa mãn” điều kiện đề bài.

• Dựng Sparse Table để truy vấn $GCD(i, j)$ trong $O(1)$.
• Dùng Hai con trỏ: Với mỗi $L$, ta tìm $R$ xa nhất sao cho $GCD(L, R) > 1$.
• Độ phức tạp: $O(n \log n)$ để dựng Sparse Table và $O(n)$ để chạy hai con trỏ. Tổng là $O(n \log n)$.

SEG

Chiến thuật Sắp xếp: Sắp xếp các đoạn thẳng theo $l$ tăng dần. Nếu $l$ bằng nhau, sắp xếp $r$ giảm dần. Nếu hai đoạn có cùng $l$, đoạn có $r$ lớn hơn sẽ bao trùm đoạn có $r$ nhỏ hơn. Việc để $r$ lớn lên trước giúp việc kiểm tra “bị chứa” dễ dàng hơn.

Lưu ý các đoạn thẳng trùng nhau

Yêu cầu bài toán là: “Đoạn thẳng đó có chứa đoạn thẳng khác hay không?”.

Giả sử ta có 2 đoạn thẳng trùng nhau: $S_1: [1, 5]$ và $S_2: [1, 5]$.

• $S_1$ chứa $S_2$ (vì $S_2$ là đoạn thẳng khác $S_1$).
• $S_2$ chứa $S_1$.
• Cả hai đều “bị chứa” bởi nhau.

3SUM

Công thức đoạn: Mọi bài toán đếm trên đoạn $[i, j]$ thường xoay quanh công thức:

\[dp[l][r] = dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1] + C[l][r]\]

LUNCH

Keyword “Minimize the Max” hoặc “Maximize the Min”: $\rightarrow$ 99% là sử dụng Binary Search on Answer. Hãy lập tức nghĩ đến việc viết một hàm bool check(mid).

Xử lý “Dãy con liên tiếp” kết hợp với điều kiện trần (Limit):

$\rightarrow$ Khi giới hạn các phần tử $\le X$, các phần tử $> X$ sẽ đóng vai trò như các “vách ngăn”. Dãy ban đầu bị chặt thành nhiều dãy con nhỏ hợp lệ. Để tối đa hóa tổng trong các dãy con này (với mảng dương), ta cứ tham lam (greedy) lấy trọn vẹn từng đoạn bị chặn bởi các “vách ngăn” đó.

DOMINO

Khi bạn gặp một bài toán có các đặc điểm sau, hãy nghĩ ngay đến DP Target Sum / Knapsack:

• Lựa chọn nhị phân: Mỗi vật phẩm có 2 trạng thái (Xoay/Không xoay, Chọn/Không chọn, Cộng/Trừ).
• Mục tiêu: Đưa một đại lượng tổng về gần một con số nào đó (thường là 0 hoặc $S/2$).
• Giới hạn: $N$ vừa phải (vài nghìn) và giá trị của vật phẩm nhỏ (để tổng giá trị không quá lớn, làm kích thước mảng DP vừa đủ bộ nhớ).

Mô hình tư duy:

“Tôi đang ở quân thứ $i$, nếu tôi chọn trạng thái A thì tổng thay đổi thế nào? Nếu chọn trạng thái B thì sao? Trạng thái nào tốn ít ‘chi phí’ (số lần xoay) hơn?”

Kinh nghiệm rút ra:

Dùng 1D duyệt ngược khi: Các thay đổi chỉ đi về một phía (chỉ tăng hoặc chỉ giảm chỉ số mảng).

Dùng mảng 2 dòng (hoặc mảng tạm) khi: Các thay đổi có thể đi về cả hai phía (có cả cộng và trừ chỉ số), hoặc khi mỗi bước bắt buộc phải chuyển sang trạng thái mới hoàn toàn.