Solutions of Average

Select solution language

hovuviettruong Created at 16 likes

$\frac{(A_{l} + A_{l+1} +... + A_{r})}{(r - l + 1)} = k $ $=> \frac{(A_{l} + A_{l + 1} + .. + A_{r})}{(r - l + 1)} - k = 0 $ $=> \frac{(A_{l} + A_{l + 1} + .. + A_{r})}{r - l + 1} - \frac{k * (r - l + 1)}{r - l + 1} = 0 $ (Quy Đồng) $=> \frac{( A_{l} + A_{l + 1} + ... + A_{r}) - k * (r - l + 1) }{r - l + 1} = 0 $ $=> \frac{(A_{l} - k + A_{l + 1} - k + ... + A_{r} - k)}{r - l + 1} = 0 $ $=> A_{l} - k + A_{l + 1} - k + ... + A_{r} - k = 0 $ (Nhân 2 vế cho $r - l + 1$) Đến Đây chỉ cần dùng $Prefixsum$, đếm dãy có tổng = 0 $Pre_{i} = Pre_{i - 1} + A_{i} - k $

nhanzzzz Created at 11 likes

***phân tích*** + gọi x là độ dài của đoạn con + $(A_1 + A_2 + A_3 + A_4 + ... + A_x) / x = k$ + $(A_1 + A_2 + A_3 + A_4 + ... + A_x) = k*x$ + $(A_1 - k + A_2 - k + A_3 - k + A_4 - k + ... + A_x - k) = 0$ ***thực hiện*** + trừ k vào tất cả các phần tử + đếm các đoạn con có tổng bằng 0 ***code mẫu*** ``` #include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int n,k; cin >> n >> k; vector<int> arr(n); for(int i=0;i<n;i++){ cin >> arr[i]; arr[i] -= k; } // int cs = 0, t = 0; unordered_map<int,int> d; d[0] = 1; for(int i: arr){ cs += i; if(d.find(cs) != d.end()){ t += d[cs]; } d[cs]++; } // cout << t; return 0; } ```

Real_BeeYT Created at 0 likes

# Lời giải (C++) ## Chỉ nên tham khảo ### Hướng giải - Nhận thấy theo bài, ta tóm gọn bài thành biểu thức sau: + Tìm cặp l, r (l <= r) sao cho $\frac{A_l + A_{l+1} + A_{l+2} + \dots + A_r}{r - l + 1} = k (1)$ - Ở tử ta nhận thấy đó chính là tổng từ l ==> r trong mảng, áp dụng công thức của mảng cộng dồn tổng (prefix sum). Từ đó ta có + $A[l...r] = A_l + A_{l+1} + A_{l+2} + \dots + A_r$ <=> $A[l...r] = pre[r] - pre[l-1]$ Thay vào (1) => $\frac{pre[r] - pre[l-1]}{r - l + 1} = k (1)$ Vậy bài toán thành **tìm cặp l,r (l <= r) sao cho $\text{pre}[r] - k \cdot r = \text{pre}[l-1] - l \cdot k + k$** Áp dụng mảng đếm để tính cặp phù hợp ```cpp int res = 0; # Khởi tạo biến đáp án for(int r = 1; r <= n; r++) { // Áp dụng công thức lùa bò, vì l <= r nên ta sẽ cập nhập l trước và cộng r cnt[pre[r-1] - k*(r-1)]++; res += cnt[pre[r] - k*r]; } ```