Chuỗi ngày vàng (Đề tự luyện HSG Tin 9 – Bài 3)
Đề bài
Chuỗi ngày vàng. Ngày thứ $i$ câu lạc bộ đọc được $a_i$ trang. Một chuỗi ngày vàng là các ngày liên tiếp $l..r$ có trung bình ít nhất $K$ trang/ngày, tức $a_l + \dots + a_r \ge K \cdot (r - l + 1)$. Tìm chuỗi ngày vàng dài nhất (nếu nhiều chuỗi cùng dài thì lấy chuỗi bắt đầu sớm nhất); in độ dài và ngày bắt đầu, hoặc $-1$ nếu không có.
Dữ liệu vào: dòng 1 gồm $N, K$ $(1 \le N \le 2 \cdot 10^5;\ 0 \le K \le 10^9)$; dòng 2 gồm $a_1, \dots, a_N$ $(0 \le a_i \le 10^9)$.
Kết quả: hai số "độ dài, ngày bắt đầu", hoặc $-1$.
- Subtask 1 (20%): $N \le 300$.
- Subtask 2 (30%): $N \le 5000$.
- Subtask 3 (50%): không ràng buộc thêm.
10 7
4 5 3 9 8 8 9 3 5 97 4Ngày 4 đến ngày 10: tổng $51 \ge 7 \cdot 7 = 49$. Các khoảng 7 ngày khác có tổng $46, 45, 45$; khoảng 8 ngày có tổng $49, 50, 54 < 56$; 9 ngày: $54, 59 < 63$; 10 ngày: $63 < 70$.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Chuỗi ngày vàngLời mở đầu
Bước 1 – bỏ phép chia. Đừng tính trung bình bằng số thực! Điều kiện "trung bình $\ge K$" tương đương $a_l + \dots + a_r \ge K \cdot (r - l + 1)$, và nếu đặt $b_i = a_i - K$ (trừ trước $K$ trang cho mỗi ngày) thì điều kiện trở thành
$b_l + b_{l+1} + \dots + b_r \ge 0$.
Bước 2 – tổng tiền tố. Gọi $P_i = b_1 + \dots + b_i$ (với $P_0 = 0$). Khi đó $b_l + \dots + b_r = P_r - P_{l-1}$, nên đoạn $[l, r]$ là chuỗi ngày vàng khi và chỉ khi
$P_{l-1} \le P_r$.
Bài toán trở thành: tìm hai chỉ số $i < r$ với $P_i \le P_r$ sao cho $r - i$ lớn nhất (khi đó $l = i + 1$). Với ví dụ, $b = (-3, -2, -4, 2, 1, 1, 2, -4, -2, 2)$:
Hình 1. Với $r = 10$, điểm xa nhất về bên trái mà không cao hơn $P_{10}$ là $P_3$: chuỗi ngày 4..10.
Cách 1Thử mọi đoạn, cộng lại từ đầu – O(N³) · 20%
Duyệt mọi cặp $(l, r)$, cộng $a_l + \dots + a_r$ bằng một vòng lặp, so với $K \cdot (r - l + 1)$ (so sánh số nguyên, không chia). $N \le 300$ thì có khoảng $4{,}5 \cdot 10^6$ phép cộng — rất nhanh. Duyệt $l$ tăng dần và chỉ cập nhật khi dài hơn hẳn ($>$) nên tự động chọn được chuỗi bắt đầu sớm nhất.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long K;
cin >> n >> K;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int best = 0, batDau = -1;
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++) {
long long tong = 0; // tinh lai tong cua doan [l, r]
for (int j = l; j <= r; j++) tong += a[j];
int len = r - l + 1;
if (tong >= K * len && len > best) { // so sanh bang so nguyen, khong chia
best = len;
batDau = l;
}
}
if (best == 0) cout << -1 << "\n";
else cout << best << " " << batDau << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, K = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
best = 0; batDau = -1
for l in range(1, n + 1):
for r in range(l, n + 1):
tong = 0 # tinh lai tong cua doan [l, r]
for j in range(l, r + 1):
tong += a[j]
ln = r - l + 1
if tong >= K * ln and ln > best: # so sanh bang so nguyen, khong chia
best = ln; batDau = l
if best == 0:
print(-1)
else:
print(best, batDau)
main()Cách 2Cộng dồn khi kéo dài đoạn – O(N²) · 50%
Với mỗi $l$, khi tăng $r$ thêm $1$ thì tổng chỉ cần cộng thêm $b_r = a_r - K$ — không phải cộng lại từ đầu. Tổng $\ge 0$ là đạt. $N \le 5000$ cho khoảng $1{,}25 \cdot 10^7$ phép: ổn. Lưu ý tổng có thể tới $2 \cdot 10^5 \cdot 10^9$, phải dùng long long.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long K;
cin >> n >> K;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int best = 0, batDau = -1;
for (int l = 1; l <= n; l++) {
long long tong = 0; // tong cua doan [l, r], cong dan khi r tang
for (int r = l; r <= n; r++) {
tong += a[r] - K; // tru san K cho moi ngay
if (tong >= 0 && r - l + 1 > best) {
best = r - l + 1;
batDau = l;
}
}
}
if (best == 0) cout << -1 << "\n";
else cout << best << " " << batDau << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
b = [0] * (n + 1)
for i in range(1, n + 1):
b[i] = int(data[1 + i]) - K # tru san K cho moi ngay
best = 0; batDau = -1
for l in range(1, n + 1):
tong = 0 # tong cua doan [l, r], cong dan khi r tang
for r in range(l, n + 1):
tong += b[r]
if tong >= 0 and r - l + 1 > best:
best = r - l + 1; batDau = l
if best == 0:
print(-1)
else:
print(best, batDau)
main()Cách 3Min tiền tố + tìm kiếm nhị phân – O(N log N) · 100%
Với mỗi $r$, ta cần chỉ số $i$ nhỏ nhất trong $[0, r-1]$ mà $P_i \le P_r$. Đặt $mn_i = \min(P_0, P_1, \dots, P_i)$ (min tiền tố). Nhận xét:
- $mn$ là dãy không tăng: $mn_0 \ge mn_1 \ge \dots$.
- "Có $i' \le i$ với $P_{i'} \le P_r$" $\iff$ $mn_i \le P_r$. Vậy chỉ số nhỏ nhất cần tìm chính là chỉ số nhỏ nhất có $mn_i \le P_r$ (tại đó $mn_i = P_i$).
Vì $mn$ không tăng, các chỉ số có $mn_i \le P_r$ tạo thành một đoạn cuối của dãy — tìm đầu đoạn đó bằng chặt nhị phân. Nếu ngay cả $mn_{r-1} > P_r$ thì không có chuỗi nào kết thúc tại $r$. Duyệt $r$ tăng dần, chỉ cập nhật khi dài hơn hẳn: với cùng độ dài, $r$ nhỏ hơn nghĩa là bắt đầu sớm hơn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long K;
cin >> n >> K;
vector<long long> P(n + 1, 0), mn(n + 1, 0); // P[i] = tong (a_j - K) voi j = 1..i; mn[i] = min(P[0..i])
for (int i = 1; i <= n; i++) {
long long a;
cin >> a;
P[i] = P[i - 1] + (a - K);
}
mn[0] = P[0];
for (int i = 1; i <= n; i++) mn[i] = min(mn[i - 1], P[i]);
int best = 0, batDau = -1;
for (int r = 1; r <= n; r++) {
// doan [l, r] dat yeu cau <=> P[r] - P[l-1] >= 0 <=> P[l-1] <= P[r]; can l-1 nho nhat
if (mn[r - 1] > P[r]) continue; // khong co l nao
int lo = 0, hi = r - 1; // mn giam dan: tim chi so nho nhat co mn <= P[r]
while (lo < hi) {
int mid = (lo + hi) / 2;
if (mn[mid] <= P[r]) hi = mid; else lo = mid + 1;
}
if (r - lo > best) { best = r - lo; batDau = lo + 1; }
}
if (best == 0) cout << -1 << "\n";
else cout << best << " " << batDau << "\n";
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); K = int(data[1])
P = [0] * (n + 1) # P[i] = tong (a_j - K) voi j = 1..i
s = 0
for i in range(1, n + 1):
s += int(data[1 + i]) - K
P[i] = s
am = [0] * (n + 1) # am[i] = -min(P[0..i]): day khong giam, dung duoc bisect
m = 0
for i in range(n + 1):
if P[i] < m: m = P[i]
am[i] = -m
best = 0; batDau = -1
for r in range(1, n + 1):
# doan [l, r] dat yeu cau <=> P[l-1] <= P[r]; tim l-1 nho nhat: min(P[0..l-1]) <= P[r]
x = -P[r]
if am[r - 1] < x:
continue # khong co l nao
lo = bisect_left(am, x, 0, r - 1)
if r - lo > best:
best = r - lo; batDau = lo + 1
if best == 0:
print(-1)
else:
print(best, batDau)
main()long long. (2) Điều kiện là $\ge K$, tức $P_{l-1} \le P_r$; viết nhầm thành $<$ sẽ bỏ sót các chuỗi có trung bình đúng bằng $K$. (3) Khi bằng độ dài phải giữ chuỗi bắt đầu sớm nhất — dùng $>$ chứ không phải $\ge$ khi cập nhật. (4) Hai con trỏ "co giãn" là sai (xem Cách 2). Ví dụ của đề đều cho cả 4 lỗi này ra đúng 7 4!Bộ test chấm "bắt" những lỗi nào?
Bộ test có 32 test: Subtask 1 có 11 test ($N \le 300$: ví dụ, $N = 1$ đạt và không đạt, $K = 0$, mọi ngày đều bằng $K$ trừ một ngày, …), Subtask 2 có 9 test ($N \approx 5000$), Subtask 3 có 12 test ($N \approx 2 \cdot 10^5$). Các kiểu dữ liệu: "đi bộ" bước nhỏ (rất nhiều tổng tiền tố bằng nhau, nhiều chuỗi trung bình đúng bằng $K$), "cao – tụt sâu – cao lại" (bẫy hai con trỏ), giá trị cực lớn (tổng vượt int), lặp một mẫu (nhiều chuỗi dài nhất bằng nhau), đáp án nằm cuối dãy, không có chuỗi nào ($-1$). Một số test nhân mọi độ lệch $a_i - K$ với cùng một hệ số lớn: đáp án giữ nguyên nhưng tổng vượt int. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (11 test) | Sub 2 (9 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Thử mọi đoạn, cộng lại | Đúng 11/11 | TLE 0/9 | TLE 0/12 | 20 |
| Cách 2 – Cộng dồn khi kéo dài | Đúng 11/11 | Đúng 9/9 | TLE 0/12 | 50 |
| Cách 3 – Min tiền tố + chặt nhị phân (chuẩn) | Đúng 11/11 | Đúng 9/9 | Đúng 12/12 | 100 |
Sai: tổng tiền tố kiểu int | WA 9/11 | WA 5/9 | WA 4/12 | 49,7 |
| Sai: so sánh chặt ($P_{l-1} < P_r$) | WA 6/11 | WA 5/9 | WA 7/12 | 56,7 |
| Sai: bằng độ dài lại lấy chuỗi bắt đầu muộn hơn | WA 9/11 | WA 8/9 | WA 7/12 | 72,2 |
| Sai: hai con trỏ "co giãn" | WA 7/11 | WA 2/9 | WA 4/12 | 36,1 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 11/11 test Subtask 1 và quá thời gian (hơn 3 giây) ở toàn bộ 21 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,03 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy tối đa khoảng 0,25 giây với CPython. Ví dụ của đề khá "hiền": chuỗi dài nhất là duy nhất, tổng của nó lớn hơn hẳn $K \times$ độ dài, số nhỏ — nên cả bốn lời giải sai ở bảng trên đều vẫn ra đúng 7 4. Nhớ tự nghĩ thêm test nha!
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét