Nhận xét chung

Mình đọc ngược từ bài 4 về 1, tâm trạng của mình thế này:

  • hmm bài 4 nhận xét hay đấy
  • hmm bài 3 cũng được, nhưng hai bài DP luôn á?
  • hmm bài 2 cũng được, phát biểu giới hạn dở quá
  • ủa wtf bài 1 phát biểu kiểu gì thế này?

Xét độ khó, mình thấy đề vừa tầm với trình độ top đầu của học sinh Đà Nẵng cũ. Mình không rõ map của Quảng Nam cũ như nào. Tuy nhiên, ngay từ bài 1 đã là lồng sàng + tổng tiền tố, các bài còn lại kể cả cài trâu cũng năng; điều này đòi hỏi thí sinh cần phải đưa ra chiến thuật hợp lý để tránh làm 3KK phiên bản rớt Lê.

Về cấu trúc, mình thấy bài 1 hơi phức tạp quá như mình mới nói trên, bài 2 oki, hai bài cuối DP hơi lệch nhẹ; có thể thay bài 3 bằng một bài tham lam thuần túy. Dở nhất là phát biểu bài 1 bị sai hoàn toàn, bài 2 gây hoang mang cho bạn nào ít thi đấu online (nơi thường xuyên có kiểu phát biểu đề tổng dữ liệu)

Bộ đề này mình cho 6.5 điểm chất lượng. (có lẽ cần phải dựng bộ tiêu chí chấm điểm cho đỡ cảm tính)

Chữa bài

Bài 1

Tóm tắt: Một số nguyên tố \(X\) được gọi là đẹp nếu (1) \(X\) là số nguyên tố, (2) khi lần lượt bỏ các chữ số từ phải sang thì từng số tạo thành cũng là số nguyên tố, (3) và TỒN TẠI một chữ số \(y\) sao cho \(\overline{Xy}\) cũng là số nguyên tố. Cho một mảng \(A\) gồm \(n \leq 10^5\) phần tử dương có giá trị không quá \(10^6\), hãy trả lời \(q\) truy vấn: từ vị trí \(u \rightarrow v\) trên mảng \(A\) có bao nhiêu số nguyên tố đẹp?

Bài này phát biểu đề sai ở vế số 3, nguyên văn gốc là:

Thêm vào bên phải \(X\) một chữ số bất kỳ thì số thu được cũng là số nguyên tố

Có một cái stereotype mà mình tới giờ mình vẫn chưa thể phủ định, là bọn học chuyên Toán sang Tin rất giỏi là vì chúng nó vừa có trực giác của bọn Tin, vừa biết phương pháp tư duy có đường lối và rành mạch từ việc phải chứng minh tất tần tật mọi thứ. Nhìn quả phát biểu đề này là mình biết người ra đề cũng tay ngang thôi.

Quay trở lại bài toán, vì mảng \(A\) cố định nên ta có thể tạo hàm estBelle(X) để kiểm tra tính đẹp của \(X\), sau đó gán \(a'_i = \texttt{estBelle}(a_i)\), mỗi truy vấn chính là \(\sum_{i=u}^v a'_i = s'_v - s'_{u-1}\), với \(s'\) là mảng cộng dồn của \(a'\). Vì vậy, bài toán còn lại cần giải quyết là kiểm tra tính nguyên tố của \(a_i\).

Vì \(X \leq 10^6\), nên \(10X+y \leq 10^7\), vừa bằng giới hạn thường thấy của sàng nguyên tố \(\mathcal{O}(n \log \log n)\). Hàm kiểm tra cũng đơn giản (đoạn dưới đây viết Python tại pseudo đẹp, chứ tất nhiên chạy trên CPython không AC được):

def estBelle(x: int) -> bool:
    x2 = x
    while x2 > 0:
        if x2 is not prime: return False
        x2 //= 10

    for y in [1, 3, 5, 7, 9]:
        if 10*x+y is prime: return True
    return False

Độ phức tạp: Gọi \(M = 10 \max X \leq 10^7\).

  • Sàng: \(\mathcal{O}(M \log \log M)\) tổng thể
  • Kiểm tra: \(\mathcal{O}(1)\) trên thực tế cho mỗi số
  • Mảng cộng dồn: \(\mathcal{O}(n)\) xây dựng, \(\mathcal{O}(1)\) truy vấn
  • Tổng:
    • Thời gian: \(\mathcal{O}(M \log \log M+n)\)
    • Bộ nhớ: \(\mathcal{O}(M+n)\)

Bài 2

Tóm tắt: Cho mảng \(D\) có \(n \leq 3000\) từ, tổng(?) độ dài không quá \(10^6\) ký tự. Trả lời \(m \leq 10^4\) truy vấn có dạng: cho từ \(W\) độ dài không quá \(1000\) và \(k\), hỏi từ thứ \(k\) theo thứ tự từ điển nhận \(W\) là tiền tố trong mảng \(D\) là từ nào (hoặc thông báo không tồn tại)?

(?) là vì đề gốc không có chữ “tổng”, mà như thế thì chương trình nuốt \(10^{10}\) ký tự là đã hết giới hạn thời gian rồi:

và độ dài các từ không vượt quá 10^6.

Cách nghĩ cơ bản nhất nhìn chung là tìm kiếm nhị phân từ đầu tiên nhận \(W\) là tiền tố, rồi cộng vị trí thêm \(k\) xem thử có còn là tiền tố không. Mỗi so sánh mất tối đa \(\|W\|=1000\) phép tính, cộng với \(\mathcal{O}(\log n)\) của tìm kiếm nhị phân.

Độ phức tạp thời gian: \(\mathcal{O}(m \times \|W\| \log n)\).

Bài 3

Tóm tắt: Cho mảng \(A\) có \(n \leq 10^6\) phần tử, tìm dãy con sao cho không tồn tại ba phần tử được chọn đứng liên tiếp nhau, và tổng là lớn nhất.

Các subtask của bài 3 khá vô nghĩa, tại từ subtask 1 đã là \(n \leq 100\) và \(n \leq 10^5\) thì cũng không có thuật toán nào ý nghĩa lắm, ít ra cũng phải để \(n \leq 30\) để các cháu tối ưu việc chọn trạng thái và nhánh cận.

Bài này Quy hoạch động cũng cơ bản, chỉ cần thêm một chiều đánh dấu đã có bao nhiêu phần tử được chọn trước đấy, và thiết lập logic chuyển trạng thái.

# init f to -oo

def dp(n: int, state: int) -> int:
    if state > n: return VIOLATED
    if f[n][state] is calculated: return f[n][state]

    if n == 1:
        return f[1][state] = a[1] if state else 0
        
    if state == 0:
        return f[n][state] = max(dp(n-1, i) for i in [0, 1, 2])
    else:
        return f[n][state] = dp(n-1, state-1) + a[n]

ans = max(
    dp[n][0],
    dp[n][1],
    dp[n][2]
)

Bài 4

Tóm tắt: Cho tổng \(N\), tìm một mảng \(A\) sao cho:

  • tổng các phần tử bằng \(N\)
  • \(\text{lcm}\) của các phần tử là lớn nhất

Khác với bài trước, bài này đã có subtask trâu được đàng hoàng.

Bài này cần đưa ra một nhận xét khá hay: phát biểu nôm na là các số không nên có ước chung, còn cụ thể là không việc gì phải dựng ra các số có dạng \(p_1^{k_1} \times p_2^{k_2} > p_1^{k_1} + p_2^{k_2}\).

Vì thế, gọi $P$ là danh sách các số nguyên tố \(\leq N\), ta gọi \(dp[i][\Sigma]\) là khi đã xét tới \(P_i\), và tổng tạo thành đang là \(N\), thì tích lớn nhất có thể là bao nhiêu.

P = [x, 2, 3, 5, 7, ..., 97]
def dp(i: int, sum: int) -> int:
    if f[i][sum] is calculated: return f[i][sum]

    if i == 0 or sum == 0:
        return f[i][sum] = 1 # bậy nhưng đằng nào đáp án cũng >= 1

    ans = dp(i-1, sum)
    p = P[i]; prod = p
    while prod <= sum:
        ans = max(ans, dp(i-1, sum - prod) * prod)
        prod *= p

    return f[i][sum] = ans

Cuối cùng việc truy vết đơn giản là sửa code để nhận biết trạng thái nào tác động lên đáp án của trạng thái hiện tại thôi.

Dự đoán

Năm ngoái điểm chuẩn 38.64, cứ cho Toán-Văn-Anh 9-6-8 thì tầm 5 điểm là đậu.

Đề năm nay khó hơn, nhưng mình nghĩ phổ điểm dịch xuống tầm 0.5đ thôi. Nghe bảo đề thi TS10 chung dễ hơn, mình nghĩ điểm chuẩn vẫn sẽ vào độ 38-dưới 40.