Solutions of Average

Select solution language

hovuviettruong Created at 2 likes

``` (Al + Al+1 +... + Ar) / (r - l + 1) = k => (Al + Al + 1 + .. + Ar)/ (r - l + 1) - k = 0 => (Al + Al + 1 + .. + Ar)/ (r - l + 1) - k * (r - l + 1)/(r - l + 1) = 0 <=> (( Al + Al + 1 + ... + Ar) - k * (r - l + 1) ) / (r - l + 1) = 0 <=> ( Al - k + A(l + 1) - k + ... Ar - k) / (r - l + 1) = 0 <=> ( Al - k + A(l + 1) - k + ... Ar - k) = 0 Đế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 0 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; } ```