Đếm số lượng dãy con liên tiếp phân biệt 2
Đề bài
Đếm số lượng dãy con liên tiếp phân biệt 2
Cho mảng $A$ gồm $n$ phần tử nguyên. Đếm số lượng dãy con liên tiếp mà không có giá trị nào xuất hiện quá 1 lần.
Ví dụ $3, 2, 3$ không thỏa mãn vì giá trị $3$ xuất hiện 2 lần.
Input:
- Dòng đầu tiên gồm số nguyên $n$.
- Dòng thứ hai gồm $n$ số nguyên $A_i$.
Output: In ra số lượng dãy con thỏa mãn.
Điều kiện: $1 \le n \le 10^6$; $|A_i| \le 10^9$.
Subtask:
- 30% điểm đầu tiên có $n \le 10^2$.
- 30% điểm tiếp theo có $n \le 10^4$.
- 30% điểm tiếp theo có $n \le 10^5$.
- 10% điểm còn lại có $n \le 10^6$.
Giới hạn thời gian: 5 giây, bộ nhớ: 256 MB.
4
1 2 1 27Lời mở đầu
"Dãy con liên tiếp" chính là một đoạn $[l, r]$ của mảng. Với ví dụ $1, 2, 1, 2$: cả 4 đoạn độ dài 1 đều được, 3 đoạn độ dài 2 là $(1, 2)$, $(2, 1)$, $(1, 2)$ cũng được, còn mọi đoạn dài từ 3 trở lên đều chứa hai số giống nhau. Tổng cộng $4 + 3 = 7$ đoạn.
Bài này là một bài "kinh điển" để luyện kỹ thuật hai con trỏ (cửa sổ trượt) kết hợp với set. Mình sẽ đi từ cách vét cạn đơn giản nhất, rồi tối ưu dần qua từng subtask, và chạy thật cả 3 cách trên bộ test chính thức để các bạn thấy rõ mỗi cách được bao nhiêu điểm.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, chia nhóm rất rõ theo $n$:
| Test | n | Giá trị $a_i$ | Số giá trị khác nhau | Đoạn tốt dài nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–20 | 4 … 10 | 1 … 10 | ≈ 71% của n | 7 | 37 |
| 21–30 | 100 | -993.535.854 … 996.323.860 | ≈ 79% của n | 52 | 1.919 |
| 31–60 | 10.000 | -999.958.696 … 999.967.683 | ≈ 76% của n | 574 | 1.643.075 |
| 61–90 | 100.000 | -999.996.950 … 999.999.359 | ≈ 67% của n | 1.192 | 29.387.370 |
| 91–99 | 1.000.000 | -999.986.449 … 999.999.381 | ≈ 55% của n | 1.321 | 315.399.362 |
| 100 | 1.000.000 | 1 … 1.000.000 | ≈ 100% của n | 1.000.000 | 500.000.500.000 |
Một vài điều đáng chú ý:
- Các test 1–20 rất nhỏ ($n \le 10$, giá trị từ 1 đến 10 nên trùng nhau nhiều). Từ test 21 trở đi các số trải khắp $[-10^9, 10^9]$ nhưng vẫn được chọn sao cho có khoảng 1/4 – 1/3 số bị lặp lại.
- Nhờ vậy, ở các test 1–99 đoạn tốt dài nhất chỉ khoảng 1000 phần tử – điều này sẽ giúp cách 2 "lì" hơn mình tưởng.
- Test 100 là test "sát thủ": $n = 10^6$ và các số $1, 2, \ldots, 10^6$ đôi một khác nhau. Mọi đoạn đều tốt nên đáp án là $\frac{n(n+1)}{2}$ $= 500\,000\,500\,000$ – vượt xa
int, biến đếm bắt buộc phải làlong long.
Subtask trong đề khớp đúng với bộ test. Số test đúng của từng cách (chạy thật, giới hạn 5 giây):
| Subtask | Đề ghi | Test | Cách 1 (vét cạn) | Cách 2 (dừng sớm + set) | Cách 3 (hai con trỏ) |
|---|---|---|---|---|---|
| 1 (30%) | $n \le 10^2$ | 1–30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $n \le 10^4$ | 31–60 | 0/30 | 30/30 | 30/30 |
| 3 (30%) | $n \le 10^5$ | 61–90 | 0/30 | 30/30 | 30/30 |
| 4 (10%) | $n \le 10^6$ | 91–100 | 0/10 | 0/10 | 10/10 |
Ý tưởngĐoạn tốt và tính chất "co giãn"
Gọi một đoạn là tốt nếu các số trong đoạn đôi một khác nhau. Có hai nhận xét rất quan trọng:
Nhận xét 1 cho phép dừng sớm: cố định đầu trái $l$, kéo dài $r$ cho tới khi gặp số trùng thì dừng luôn (cách 2).
Vậy ta giữ một "cửa sổ" $[l, r]$ luôn tốt và một set chứa các giá trị trong cửa sổ. Mỗi lần thêm $a_r$: nếu $a_r$ đã có trong set thì bỏ dần phần tử bên trái ($a_l$, rồi $l$++) cho tới khi hết trùng; sau đó thêm $a_r$ vào và cộng $r - l + 1$ vào đáp án. Mỗi phần tử được thêm vào 1 lần và bị xoá tối đa 1 lần nên tổng số thao tác chỉ là $O(n)$ lần thao tác trên set.
Em nhập dãy số rồi bấm Tiếp để xem cửa sổ trượt (ô xanh là cửa sổ $[l, r]$, ô vàng là $a_r$ vừa xét, ô đỏ là phần tử vừa bị đẩy ra):
Cách 1Vét cạn mọi đoạn – Subtask 1
Làm đúng như định nghĩa: duyệt mọi đoạn $[l, r]$, với mỗi đoạn dùng 2 vòng for so sánh mọi cặp phần tử xem có cặp nào bằng nhau không.
- Hàm
phanBiet(l, r)trả vềfalsengay khi thấy một cặp $a_i = a_j$, không cần so tiếp. - Biến
demlàlong longvì đáp án có thể lên tới $5 \cdot 10^{11}$.
Có $\frac{n(n+1)}{2}$ đoạn, mỗi đoạn tốn tới $O(n^2)$ phép so sánh nên tổng cộng $O(n^4)$. Với $n = 100$ chỉ cỡ vài triệu phép tính, nhưng với $n = 10^4$ thì là con số khổng lồ.
Kết quả chạy thật: Bản C++ đúng 30/100 test, quá thời gian ở test 31–100; test đúng chạy lâu nhất 0.00s (máy mình đang bận nên từ test 43 trở đi mình cắt ở 1 giây cho nhanh – với $n \ge 10^4$ thì cách $O(n^4)$ chắc chắn không thể chạy dưới 5 giây). Bản Python đúng 30/40 test (mình chỉ chạy test 1–40), quá thời gian ở test 31–40; test đúng chạy lâu nhất 0.06s. Ăn trọn subtask 1 (30% điểm).
Cách 2Dừng sớm + set – Subtask 2, 3
Dùng nhận xét 1: cố định $l$, cho $r$ chạy từ $l$ sang phải và giữ một set các giá trị đã gặp trong đoạn $[l, r-1]$. Nếu $a_r$ đã có trong set thì đoạn $[l, r]$ hỏng, và mọi đoạn dài hơn cũng hỏng, nên break luôn. Mỗi lần chưa hỏng thì đoạn $[l, r]$ tốt, ta tăng dem.
set<int> skhai báo bên trong vòng $l$ nên mỗi $l$ mới lại bắt đầu vớisetrỗng.s.count(a[r])trả về 1 nếu $a_r$ đã có trongset, 0 nếu chưa – mất $O(\log n)$.
Trường hợp xấu nhất (mọi số khác nhau, như test 100) vòng $r$ luôn chạy tới cuối nên vẫn là $O(n^2 \log n)$. Nhưng để ý: tổng số lần vòng trong chạy đúng bằng đáp án (mỗi lần dem++ là một bước). Ở test 61–90 đáp án chỉ khoảng $3 \cdot 10^7$ nên cách này vẫn qua; còn ở test 91–99 đáp án $\approx 3 \cdot 10^8$ và test 100 là $5 \cdot 10^{11}$ thì chịu.
Kết quả chạy thật: Bản C++ đúng 90/100 test, quá thời gian ở test 91–100; test đúng chạy lâu nhất 3.84s. Bản Python đúng 60/100 test, quá thời gian ở test 61–100; test đúng chạy lâu nhất 0.45s. Bản C++ ăn được subtask 1, 2, 3 (90% điểm).
set, thay bằng vòng for so $a_r$ với $a_l..a_{r-1}$ (vẫn dừng sớm) thì độ phức tạp lý thuyết tệ hơn ($O(n^3)$), nhưng vì đoạn tốt dài nhất trong test chỉ khoảng 1000 nên thực tế lại chạy nhanh ngang ngửa: bản này đúng 90/100 test, quá thời gian ở test 91–100; test đúng chạy lâu nhất 3.27s. Đây là một ví dụ cho thấy dữ liệu ngẫu nhiên đôi khi "nương tay" với lời giải chưa tối ưu – nhưng gặp test như test 100 thì vẫn gục.Cách 3Hai con trỏ + set – Full điểm
Đây là cài đặt của nhận xét 2: con trỏ $r$ chạy từ 1 tới $n$, con trỏ $l$ chỉ tiến chứ không lùi.
- Vòng
while(s.count(a[r])): chừng nào $a_r$ còn trùng với một số trong cửa sổ thì đẩy $a_l$ ra khỏisetvà tăng $l$. Vì các số trong cửa sổ đôi một khác nhau nêns.erase(a[l])xoá đúng phần tử $a_l$. - Sau vòng
while, đoạn $[l, r]$ tốt và $l$ nhỏ nhất có thể, nên có đúng $r - l + 1$ đoạn tốt kết thúc ở $r$. - Tuy có vòng
whilelồng trongfor, nhưng $l$ chỉ tăng tối đa $n$ lần trong cả chương trình, nên tổng số lần chạy thânwhilekhông quá $n$. - Bản Python dùng biến thể "vị trí xuất hiện cuối cùng":
last[x]là vị trí gần nhất của giá trị $x$; nếulast[a[r]] >= lthì nhảy thẳngl = last[a[r]] + 1thay vì xoá từng phần tử. Ý tưởng y hệt, chỉ là nhảy một bước thay vì đi từng bước.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.51s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 1.18s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn mọi đoạn | C++ | 30/100 | > 5s | Qua subtask 1; quá thời gian từ test 31 |
| Python | 30/40 | > 5s | Mình chỉ chạy test 1–40; quá thời gian test 31–40 | |
2. Dừng sớm + set | C++ | 90/100 | > 5s | Quá thời gian test 91–100 |
| Python | 60/100 | > 5s | Quá thời gian test 61–100 | |
| 2'. Dừng sớm, so tuyến tính | C++ | 90/100 | > 5s | Quá thời gian test 91–100 |
3. Hai con trỏ + set | C++ | 100/100 | 0.51s | Full điểm |
| Python | 100/100 | 1.18s | Hai con trỏ + dict vị trí cuối |
set bằng mảng đánh dấu, nhưng với giới hạn 5 giây thì set là quá đủ và code gọn, dễ hiểu hơn.
Nhận xét
Đăng nhận xét