Đoạn đường cao tốc êm ái

Arrays Buổi 14 — Two Pointers & Sliding Window Buổi 21 — DP 1D cổ điển Dynamic Programming Mathematics
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions

Mảng con tốt

Một mảng con được định nghĩa là tốt nếu tổng các phần tử của nó bằng đúng độ dài của nó: \[\sum_{i=l}^r a_i = r - l + 1\]

Cho một mảng gồm $n$ chữ số từ $0$ đến $9$, hãy tính số lượng mảng con liên tiếp tốt.

Dữ liệu vào

  • Dòng 1: Số nguyên $t$ ($1 \le t \le 1000$) — số lượng bộ test.
  • Với mỗi bộ test:
    • Dòng 1: Số nguyên $n$ ($1 \le n \le 10^5$) — độ dài mảng.
    • Dòng 2: Chuỗi gồm $n$ chữ số $a_1 a_2 \dots a_n$ ($0 \le a_i \le 9$).
  • Đảm bảo tổng $n$ trên tất cả bộ test không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ test, in ra số lượng mảng con liên tiếp tốt trên một dòng.

Draft saved