Editorial for Kệ Trà Cân Bằng
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Kệ Trà Cân Bằng
Chủ đề: từ điển (dict) với khóa là tuple, kỹ thuật "tiền tố"
Tóm tắt đề
Cho chuỗi \(s\) gồm chữ cái in hoa, độ dài tới \(2 \times 10^5\). Đếm số đoạn con liên tiếp có số chữ A = số chữ B = số chữ C \(\geq 1\).
Cách ngây thơ
Duyệt mọi đoạn \((l, r)\), với mỗi \(l\) cộng dồn số A, B, C khi \(r\) tăng dần. Có \(\dfrac{n(n+1)}{2} \approx 2 \cdot 10^{10}\) đoạn → TLE. Còn tệ hơn nữa nếu mỗi đoạn lại cắt chuỗi rồi gọi count (\(O(n^3)\)).
Bước 1: biến "đoạn" thành "cặp tiền tố"
Gọi \(a_i, b_i, c_i\) là số chữ A, B, C trong \(i\) ký tự đầu tiên (gọi là tiền tố độ dài \(i\), với \(a_0 = b_0 = c_0 = 0\)). Đoạn từ ký tự \(l + 1\) đến ký tự \(r\) có:
- số
Alà \(a_r - a_l\), sốBlà \(b_r - b_l\), sốClà \(c_r - c_l\).
Đoạn này có ba số bằng nhau khi và chỉ khi
\(a_r - a_l = b_r - b_l = c_r - c_l\)
\(\Leftrightarrow (a_r - b_r,\; b_r - c_r) = (a_l - b_l,\; b_l - c_l)\)
Nghĩa là: hai tiền tố có cùng bộ hiệu số (A - B, B - C). Bài toán trở thành: đếm số cặp \(l < r\) có cùng khóa.
Bước 2: đếm cặp trùng khóa bằng dict
Giống hệt bài Combo Hai Ly: duyệt các tiền tố từ trái sang phải, với mỗi tiền tố cộng vào đáp án số tiền tố đứng trước có cùng khóa, rồi mới tăng bộ đếm của khóa đó.
dem = {(0, 0): 1} # tiền tố rỗng
for ch in ke:
... cập nhật a, b, c ...
khoa = (a - b, b - c)
tong += dem.get(khoa, 0)
dem[khoa] = dem.get(khoa, 0) + 1
Khóa là một tuple hai số. Không thể gộp thành một số kiểu (a - b) * 10 + (b - c) vì các hiệu số có thể rất lớn và âm, hai khóa khác nhau sẽ bị trùng (ví dụ \((1, 0)\) và \((0, 10)\) cùng cho \(10\)).
Bước 3: cái bẫy "ba số cùng bằng 0"
Đếm ở bước 2 cho ra số đoạn có A = B = C, bao gồm cả các đoạn mà cả ba đều bằng \(0\), tức là các đoạn chỉ chứa đồ uống khác (như X, ZZ ở Sample 2). Đề bài yêu cầu mỗi loại trà có ít nhất một chai, nên phải trừ các đoạn này đi.
Đếm số đoạn không chứa A, B, C nào rất dễ: một dãy liên tiếp \(L\) chai "khác" chứa \(\dfrac{L(L+1)}{2}\) đoạn. Cài đặt gọn hơn: duyệt từ trái sang, giữ độ dài chuoi_khac của dãy chai "khác" kết thúc tại vị trí hiện tại, rồi cộng nó vào tổng (vì có đúng chừng ấy đoạn "rỗng" kết thúc tại đây).
Đáp án là (kết quả bước 2) - (kết quả bước 3).
Độ phức tạp
\(O(n)\) thời gian và bộ nhớ.
Code mẫu
def dem_doan_can_bang(ke):
dem = {(0, 0): 1}
a = b = c = 0
tong = 0
for ch in ke:
if ch == "A":
a += 1
elif ch == "B":
b += 1
elif ch == "C":
c += 1
khoa = (a - b, b - c)
tong += dem.get(khoa, 0)
dem[khoa] = dem.get(khoa, 0) + 1
return tong
def dem_doan_rong(ke):
tong = 0
chuoi_khac = 0
for ch in ke:
if ch in "ABC":
chuoi_khac = 0
else:
chuoi_khac += 1
tong += chuoi_khac
return tong
n = int(input())
ke = input().strip()
print(dem_doan_can_bang(ke) - dem_doan_rong(ke))
Comments