Hint 1: Đừng nhìn vào hình vuông trước

Hãy nhìn các đoạn đất được tạo ra.

Ví dụ:

Chiều cao = 6

Có đường ngang tại hàng 3

Ta có:

1 ----- 3 ----- 7

Các đoạn:

3 - 1 = 2
7 - 3 = 4

Vậy chiều cao đã bị chia thành:

2 và 4

Hint 2: Hình vuông cạnh k phải thế nào?

Giả sử có đoạn dài:

4

Muốn lát kín bằng hình vuông cạnh:

k = 2

thì:

4 = 2 + 2

Lát được.

Nếu:

k = 3

thì:

4 không chia hết cho 3

Sẽ bị dư.

Không lát kín được.

Hint 3: Điều kiện của k

Nếu đoạn dài:

2
4
6

thì:

k phải chia hết cho 2
k phải chia hết cho 4
k phải chia hết cho 6

Tức là:

k là ước chung của tất cả các đoạn

Hint 4: Học sinh THCS nhớ tới gì?

Khi nghe:

Ước chung

thì nghĩ tới:

UCLN

Ví dụ:

2
4
6

Ta có:

UCLN(2,4,6)=2

Hint 5: Sau khi có UCLN

Giả sử:

UCLN = 12

Các giá trị k hợp lệ là:

1
2
3
4
6
12

vì tất cả đều là ước của 12.

Hint 6: Vì sao chỉ cần tìm UCLN?

Ví dụ:

2
4
6

Ước của 2:

1 2

Ước của 4:

1 2 4

Ước của 6:

1 2 3 6

Ước chung:

1 2

Mà:

UCLN = 2

Ước của 2:

1 2

Giống hệt.

Hint 7: Các đoạn lấy ở đâu?

Đừng quên thêm biên.

Ví dụ:

n = 6

có đường ngang:
3

Ta thêm:

1
7

được:

1 3 7

Các đoạn là:

3 - 1 = 2

7 - 3 = 4

Hint 8: Làm tương tự cho cột

Ví dụ:

m = 8

đường dọc:
3

Ta có:

1 3 9

Các đoạn:

2
6

Hint 9: Tính UCLN tất cả đoạn

Ví dụ:

ngang:
2
4

dọc:
2
6

Ta lấy:

UCLN(2,4,2,6)

Kết quả:

2

Hint 10: Tìm mọi ước của UCLN

Nếu:

g = 2

Ước:

1
2

Output:

2
1 2

Công thức cuối cùng

Bước 1

Tạo các đoạn:

doan = vi_tri_hien_tai - vi_tri_truoc

Bước 2

Tính:

g = gcd(g, doan)

Bước 3

Tìm:

i là ước của g

khi:

g % i == 0

Câu thần chú để nhớ khi đi thi

Chia đất
→ tính độ dài các đoạn

Các hình vuông phải lát kín
→ cạnh hình vuông phải chia hết mọi đoạn

Chia hết mọi đoạn
→ tìm UCLN

Các đáp án
→ tất cả các ước của UCLN

Chỉ cần nhớ 4 dòng trên là tự suy ra được lời giải của bài.

Bước 1: Tổng lớn nhất

Chọn 2 số lớn nhất là n và n - 1.

M = 2 * n - 1

Ví dụ n = 50:

M = 2*50 - 1 = 99

Bước 2: Tìm số dạng 10^k

Ta cần tìm p = 10^k lớn nhất sao cho:

p <= M

Code:

p = 1

while p * 10 <= M:
    p = p * 10

Ví dụ:

M = 299
p = 100

Khi đó tổng tốt nhất sẽ kết thúc bằng:

p - 1 = 99

Bước 3: Các tổng cần xét

Nếu p = 100, các tổng tốt nhất là:

99, 199, 299, 399, ...

Công thức:

S = p - 1
S = S + p

Code:

S = p - 1

while S <= M:
    # đếm cặp có tổng S
    S = S + p

Bước 4: Đếm số cặp có tổng S

Ta cần:

a + b = S
1 <= a < b <= n

Vì:

b = S - a

Điều kiện b <= n:

S - a <= n
=> a >= S - n

Vậy a nhỏ nhất:

L = max(1, S - n)

Điều kiện a < b:

a < S - a
2a < S
a <= (S - 1) // 2

Vậy a lớn nhất:

R = (S - 1) // 2

Số cặp:

if L <= R:
    ans = ans + R - L + 1

Code gợi ý gần hoàn chỉnh

T = int(input())

for i in range(T):
    n = int(input())

    if n < 2:
        print(0)
        continue

    M = 2 * n - 1

    p = 1
    while p * 10 <= M:
        p = p * 10

    if p == 1:
        print(n * (n - 1) // 2)
        continue

    ans = 0
    S = p - 1

    while S <= M:
        L = max(1, S - n)
        R = (S - 1) // 2

        if L <= R:
            ans = ans + R - L + 1

        S = S + p

    print(ans)

Câu nhớ nhanh:

M = 2n - 1
p = 10^k lớn nhất <= M
Tổng tốt nhất: p-1, 2p-1, 3p-1, ...
Đếm a từ L đến R

Hint 1

Đề bài cho chúng ta 3 điều kiện về cấu trúc xâu:

• \(X\) có dạng *A*B* (Nghĩa là: chuỗi \(A\) nằm trọn vẹn ở phía trước chuỗi \(B\))
• \(Y\) có dạng *C*A* (Nghĩa là: chuỗi \(C\) nằm trọn vẹn ở phía trước chuỗi \(A\))
• \(Z\) có dạng *B*C* (Nghĩa là: chuỗi \(B\) nằm trọn vẹn ở phía trước chuỗi \(C\))

Dấu * đại diện cho các ký tự thừa có thể bỏ qua. Từ cấu trúc trên, ta có thể tưởng tượng việc cắt mỗi xâu ra làm 2 nửa bằng 3 "vách ngăn" ảo tại các vị trí \(i, j, k\):

1. Cắt xâu \(X\) tại vị trí \(i\) (\(0 \le i \le n\)):
2. Nửa trái \(X[1 \dots i]\) sẽ dùng để chứa \(A\).

3. Nửa phải \(X[i+1 \dots n]\) sẽ dùng để chứa \(B\).

4. Cắt xâu \(Y\) tại vị trí \(j\) (\(0 \le j \le n\)):

5. Nửa trái \(Y[1 \dots j]\) sẽ dùng để chứa \(C\).

6. Nửa phải \(Y[j+1 \dots n]\) sẽ dùng để chứa \(A\).

7. Cắt xâu \(Z\) tại vị trí \(k\) (\(0 \le k \le n\)):

8. Nửa trái \(Z[1 \dots k]\) sẽ dùng để chứa \(B\).
9. Nửa phải \(Z[k+1 \dots n]\) sẽ dùng để chứa \(C\).

Lắp ráp các nửa lại với nhau, ta rút ra bản chất cốt lõi của bài toán:

• Chuỗi \(A\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(X[1 \dots i]\) và \(Y[j+1 \dots n]\).
• Chuỗi \(B\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(X[i+1 \dots n]\) và \(Z[1 \dots k]\).
• Chuỗi \(C\) lớn nhất chính là Chuỗi con chung dài nhất của đoạn \(Y[1 \dots j]\) và \(Z[k+1 \dots n]\).

Nhiệm vụ bây giờ là tìm ra bộ ba \((i, j, k)\) sao cho tổng độ dài của \(A + B + C\) đạt giá trị Max.

Hint 2: Xây dựng mảng Quy hoạch động (DP) \(O(n^2)\)

Nếu với mỗi bộ ba \((i, j, k)\) ta lại viết một hàm chạy vòng lặp tìm chuỗi con chung, độ phức tạp sẽ vượt quá \(O(n^3)\) và chắc chắn bị Time Limit Exceeded (TLE). Giải pháp là ta sẽ tính trước (tiền xử lý) 3 mảng DP 2 chiều:

• F[i][j]: Chứa độ dài xâu \(A\) dài nhất.
• G[i][k]: Chứa độ dài xâu \(B\) dài nhất.
• H[j][k]: Chứa độ dài xâu \(C\) dài nhất.

Lấy mảng F[i][j] làm ví dụ, ta sẽ tính nó qua 3 bước như sau:

• Bước 2.1 - DP Cơ bản: Dùng mảng phụ dp[u][v] để tính độ dài chuỗi con chung kết thúc đúng tại ký tự thứ \(u\) của \(X\) và thứ \(v\) của \(Y\). Nếu \(X[u] == Y[v]\) thì dp[u][v] = dp[u-1][v-1] + 1.
  Khi đó, chuỗi chung này có độ dài là \(L\), nó sẽ chiếm một khoảng trong \(Y\) bắt đầu từ vị trí \((v - L + 1)\) đến \(n\). Ta cập nhật: F[u][v - L] = max(F[u][v - L], L).
• Bước 2.2 - Lan truyền độ dài: Nếu có một chuỗi con chung độ dài \(L\), hiển nhiên bên trong nó sẽ chứa các chuỗi con độ dài \(L-1\). Ta cần lan truyền giá trị này xuống bằng cách xóa bớt ký tự ở cuối \(X\) hoặc đầu \(Y\):
  F[i-1][j] = max(F[i-1][j], F[i][j] - 1)
F[i][j+1] = max(F[i][j+1], F[i][j] - 1)
• Bước 2.3 - Nới lỏng ranh giới (Mở rộng vùng tìm kiếm): Nếu ta có kết quả tốt nhất trong đoạn nhỏ, thì khi mở rộng đoạn đó ra, kết quả chỉ có thể lớn hơn hoặc bằng.
  F[i][j] = max(F[i][j], F[i-1][j], F[i][j+1])

(Các bạn áp dụng logic tương tự để xây dựng mảng G cho nửa sau X / nửa đầu Z; và mảng H cho nửa đầu Y / nửa sau Z nhé).

Hint 3: Tuyệt chiêu Cắt tỉa (Pruning) biến \(O(n^3)\) thành \(O(n^2)\)

Sau khi có 3 mảng F, G, H, công thức tìm đáp án là:
Ans = max( F[i][j] + G[i][k] + H[j][k] )

Duyệt 3 vòng lặp for i, for j, for k từ 1 đến \(n\) sẽ mất \(2000 \times 2000 \times 2000 = 8 \times 10^9\) phép toán. Trong môi trường thi đấu thực tế, C++ sẽ chạy mất khoảng 8 giây, còn Python thì sẽ sập nguồn (TLE).

Đây là lúc thuật toán Cắt tỉa nhánh (Pruning) thể hiện sức mạnh:

Hãy suy luận một chút trước khi bước vào vòng lặp \(k\) (vòng lặp trong cùng):

• Đứng tại vị trí \(i\) hiện tại, mảng \(G\) chứa \(B\) đạt giá trị lớn nhất khi nào? Đó là khi ta lấy toàn bộ xâu \(Z\) (tức là \(k = n\)). Vậy Max lý tưởng của nhánh này là G[i][n].
• Đứng tại vị trí \(j\) hiện tại, mảng \(H\) chứa \(C\) đạt giá trị lớn nhất khi nào? Đó là khi ta cũng lấy toàn bộ xâu \(Z\) (tức là \(k = 0\)). Vậy Max lý tưởng của nhánh này là H[j][0].

Từ đó ta suy ra: Tất cả các giá trị thực tế của vòng lặp \(k\) đều không bao giờ vượt qua được tổng F[i][j] + G[i][n] + H[j][0].

Mã giả áp dụng:

```text
Cho i chạy từ 0 đến n:
Cho j chạy từ 0 đến n:
Tổng_Lý_Tưởng_Nhất = F[i][j] + G[i][n] + H[j][0]

    NẾU (Tổng_Lý_Tưởng_Nhất <= Kỷ_Lục_Ans_Hiện_Tại):
        Bỏ qua luôn vòng lặp k! (continue)
        // Vì dù k có hoàn hảo đến mấy cũng không thể phá vỡ kỷ lục

    NẾU (Có tiềm năng phá kỷ lục):
        Cho k chạy từ 0 đến n:
            Ans = max(Ans, F[i][j] + G[i][k] + H[j][k])