Tin học Đặt câu hỏi (C++)

[dmp7106]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Yêu cầu: Cho dãy số nguyên dương a1, a2, ..., an và số dương n. Đếm xem có bao nhiêu bộ chỉ số i, j thỏa mãn:
+) ai+ ai+1+...+aj=k
+) 1<=i<j<=n
Dữ liệu:
- Dòng 1 ghi 2 số nguyên dương n, k (0<n<=2000, k<1018)
- Dòng 2 ghi n số nguyên dương a1, a2, ...an.
Kết quả:
- In ra số lượng cặp (i, j) thỏa mãn yêu cầu

 

[iceghost]

Bạn có thể sử dụng kỹ thuật sliding window, đại khái thế này:

i = j = 1, count = 0;
sum = a_i + a_(i+1) + ... + a_j;
do {
  if (sum == k) count++;
  if (sum <= k) sum += a_(++j); // mở rộng
  if (sum > k) sum -= a_(i++); // thu hẹp
} while (j <= n);
return count;

À, nhớ tối ưu hóa việc tính tổng bằng cách cộng hoặc trừ đi a_i và a_j nhé bạn

 

[dmp7106]

ật sliding window, đại khái

em có thử tìm từ khóa sliding window nhưng nó chỉ có tiếng Anh. Em k giỏi t.anh lắm. Không bt a có tài liệu nào về sliding bằng tiếng Việt cho e xin vs đc k ạ. Em cảm ơn ạ.

 

[dmp7106]

k (0<n<=2000, k<1018)
- Dòng 2 ghi n số nguyên dương a1, a2, ...an.

em có thử với prefix sum thì oke r ạ. dành cho ai cần sau này nè hehe.
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
int n;
long long k;
cin >> n >> k;
//mang cong don - prefix sum
long long a[n+1];
long long f[n+1];
f[0]=0;
long long count = 0;
for (int i = 1;i <=n; i++){
cin >> a;
}
for(int i =1;i<=n;i++){
f=f[i-1]+a;
}
for(int i =1;i<n;i++){
for(int j =i;j<=n;j++){
if (f[j]-f[i-1]==k){
count++;
}
}
}
//end
cout << count;
//system("pause");
return 0;
}