Dãy con liên tiếp có tổng bằng k
Xem dạng PDF
Gửi bài giải
Điểm:
12,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho 2 số nguyên N, K và dãy gồm N số nguyên ~a_1, a_2,…,a_N~.
Yêu cầu: Hãy đếm số lượng các dãy con gồm các phần tử liên tiếp nhau có tổng bằng K tìm được.
Input:
- Dòng 1. Ghi 2 số nguyên N, K
- Dòng 2. Ghi N số nguyên mỗi số cách nhau ít nhất 1 dấu cách.
Output:
- Dòng 1. Ghi số nguyên dương d là số lượng các dãy con có tổng bằng K tìm được thỏa mãn các yêu cầu trên.
(Lưu ý: 1 phần tử cũng tính là 1 dãy)
Example:
Input:
4 5
1 4 2 3
Output:
2
Constraints:
~0 < n < 2.10^4, -2.10^9 < k < 2.10^9; -10^7 \le a_i \le 10^7~
Bình luận
include <bits/stdc++.h>
using namespace std; long long n,f[1000009],a[1000009]; map<int,int> mp; map<int,int>::iterator it; //------------------------------------ int main() { long long k,kq=0; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; f[i]=f[i-1]+a[i]; } mp[0]=1; for(int i=1;i<=n;i++) { kq+=mp[f[i]-k]; mp[f[i]]++; } cout<<kq;
}
con xin lỗi đảng,con xin lỗi nhà nước,em xin lỗi thầy vì em đã if với test.Nhưng em cay quá nên phải làm vậy :))