Dãy 2-Sum
Xem dạng PDFMột dãy các số nguyên không âm ~A_{1 \dots N}~ được gọi là 2-Sum nếu ta có thể tách dãy đó làm ~2~ dãy có tổng các giá trị bằng nhau. Nghĩa là tồn tại một số ~k~ trong đoạn ~[1 \dots N-1]~ sao cho tổng ~A_{1} + A_{2} + \dots + A_{k} = A_{k + 1} + A_{k + 2} + \dots + A_{N}~.
Cho ~1~ dãy gồm ~N~ số nguyên không âm. Hãy tìm dãy con gồm các phần tử liên tiếp dài nhất mà cũng là dãy 2-Sum.
Input
Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 5000)~.
~N~ dòng tiếp theo, dòng thứ ~i~ chứa giá trị của phần tử ~A_{i}~ của dãy. ~(0 \le A_{i} \le 200000)~
Output
Xuất ra độ dài lớn nhất của dãy 2-Sum tìm được. Nếu không có kết quả thì in ra ~0~.
Sample Input
6
2
10
3
2
5
1
Sample Output
4
Note
Giải thích: dãy 2-Sum dài nhất tìm được là A[2..5] = {10, 3, 2, 5}. Có thể tách dãy này thành 2 phần {10} và {3, 2, 5} có tổng bằng 10.
Bình luận
include <bits/stdc++.h>
define ll long long
define pb push_back
define pol LLONG_MAX
define pel LLONG_MIN
define ull unsigned long long
define rep(i,a,b) for(int i=a;i<b;i++)
define fope(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
using namespace std; const ll MOD = 1e9+7; const ll INF = 1000005; ll n,m,k,x=0,d1=0,z,ans,res; ll a[INF],f[INF]; void input(){ cin >> n; f[0]=0; for(ll i=1;i<=n;i++){ f[i]=f[i-1]; cin >> a[i]; f[i]+=a[i]; } } void output(){
ans=0; for(ll k=1;k<=n;k++){ ll i=k,j=k+1; ll st=a[i],ss=a[j]; while(true){ if(st==ss) ans=max(ans,j-i+1); if(st>ss){ if(j<n){ j++; ss=ss+a[j]; } else break; } else{ if(i>1){ i--; st+=a[i]; } else break; } } } cout << ans; } int main(){ ios::syncwithstdio(0);
cin.tie(0); fope("day2sum"); input(); output(); return 0;
}
Ý tưởng với mỗi giá trị k ta mở rộng từ trung tâm
code tham khảo:
với mỗi k, hai con trỏ đối xứng rộng ra là được, áp dụng với 2 * p[k] = p[l] + p[r] cho đoạn [l + 1...r], O(n^2) ok rồi, làm có 0,07s hà
Bài này prefix sum vẫn ac được!
ai hd mik lam bai nay vs mik cam on
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
mình code 2 pointer bth AC xong vào thấy các ngài code chặt nhị phân tự nhiên thấy hoang mang ghê @@
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.