Hướng dẫn cho Tổng bằng 0
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
- 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
Bình luận
Vì mảng bắt đầu từ 1 nha bạn nên phần tử a[0]=0
em không hiểu tại a[0] lại bằng 0 ạ không có được không ạ