Editorial for Tổng bằng 0
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Mình xin chia sẻ lời giải bài này như sau:
- Ta có: \(a[i]+a[i+1]+...+a[j]=L[j]-L[i-1]\), trong đó \(L[x]\) là tổng các số từ \(1\) đến \(x(x\in \mathbb{N}^{*})\)
- Khi đó \(a[i]+a[i+1]+...+a[j]=0\iff L[j]=L[i-1]\).
- Gọi \(L[]\) là mảng thỏa mãn \(L[i]\) là tổng các số từ \(1\) đến \(i(i\in \mathbb{N}^{*})\) và ta quy ước \(L[0]=0\)
- Khi đó bài toán quy về đếm số cặp \((i,j)\) thỏa mãn \(0\le i<j\le n\) và \(L[i]=L[j]\).
- Để giải quyết bài toán này thì ta chỉ việc, sắp xếp lại mảng \(L[]\) và duyệt một for để xác định giá trị thỏa mãn yêu cầu bài toán.
- Để hiểu rõ hơn, mình sẽ giải ví dụ của bài toán luôn , như sau:
- Ta có mảng \(A[]=\left\{-3,3,-4,4\right\}\implies L[]=\left\{0,-3,0,-4,0\right\}\).
- Sort mảng \(L[]\) theo thứ tự tăng dần ta được \(L[]=\left\{-4,-3,0,0,0\right\}\).
- Ta thấy rằng, mảng \(L\) trên có \(3\) số \(0\) bằng nhau do đó đáp án của bài toán là \(\binom{3}{2}=3\).
- Chú ý: \(\binom{n}{2}=0\) nếu \(n<2\) và bằng \(\frac{n(n-1)}{2}\) nếu \(n\ge 2\)
- Vậy tổng quát lên ta có đáp án của bài toán chính bằng \(\sum \binom{H_i}{2}\). Trong đó \(H[i]\) chính là tần số của phần tử \(L[i]\). (trong đó các \(L[i]\) khác nhau từng đôi một và chỉ tính một lần), nếu bạn thấy đoạn này có vẻ khó hiểu thì hãy xem code dưới đây nhé :
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn (ll)(1e5+5)
ll a[maxn],i,n,b[maxn],res,tmp=1;
int main(){
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=n;i++) b[i]=b[i-1]+a[i];
sort(b,b+n+1);
for(i=0;i<n;i++){
if(b[i]==b[i+1]) tmp+=1;
else{
res+=tmp*(tmp-1)/2;
tmp=1;
}
}
res+=tmp*(tmp-1)/2;
cout<<res;
return 0;
}
- Như vậy ta đã giải quyết xong bài toán, nếu có gì khó hiểu hoặc sai, các bạn cứ comment
Comments