[Mảng 1 Chiều Cơ Bản]. Bài 44. Dãy con chẵn lẻ
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng A[] gồm N phần tử, bạn hãy đếm số lượng dãy con liên tiếp mà số lượng số chẵn bằng số lượng số lẻ.
Đầu vào
Dòng 1 là N : số phần tử trong mảng
Dòng 2 là N phần tử cách nhau 1 khoảng trắng
Giới hạn
1<=N<=1000
0<=A[i]<=1000
Đầu ra
In ra đáp án của bài toán
Ví dụ :
Input 01
7
3 2 1 6 4 0 0
Output 01
4
Giải thích :
Các dãy con thỏa mãn {3, 2}, {3, 2, 1, 6}, {1, 6}, {2, 1}
Bình luận
Bài này cũng thú vị. Cách làm của mình là ta sẽ xét mỗi phần tử trong mảng (1). Với mỗi phần tử đang xét, ta mở rộng sang phải để tạo dãy con bằng một vòng for nửa. Bạn để ý thì để điều kiện đếm thỏa mãn thì số chẵn phải bằng số lẽ (2). Mình nghĩ code mình khá dễ hiểu, không map không vector.
Source code:
include <iostream>
using namespace std;
int main() { int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i];
}
include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll countBalancedSubarrays(const vector<int>& arr) { unordered_map<int, int> freq; freq[0] = 1;
}
int main() { iosbase::syncwith_stdio(false); cin.tie(nullptr);
}
.
include <iostream>
ae tham khảo ^_^
include<bits/stdc++.h>
using namespace std; mp;
long long tong=0;
int dem=0;
mp[0].pushback(1);
int n;cin>>n;
for(int i=0;i<n;i++)
{
int x;cin>>x;
if(x%2==0) tong=tong+1;
else tong=tong-1;
if(mp.count(tong)!=0)
int main() { map
{ dem=dem+mp[tong].size(); mp[tong].pushback(i); } else mp[tong].push_back(i); } cout<<dem; }
include <iostream>
include <math.h>
include <set>
include <map>
include <bits/stdc++.h>
using namespace std; long long gt(int n) { long long sum = 0; for (int i = 0;i <= n;i++) sum += i; return sum; } int main() { int n;cin >> n; int a[n]; for (int i = 0;i < n;i++) cin >> a[i]; int tong = 0; long long demt = 0; map <int,int> mp; for (int i = 0;i < n;i++) { if (a[i] % 2 == 0) a[i] = 1; else a[i] = -1; } for (int i = 0;i < n;i++) { tong += a[i]; mp[tong]++; } for (auto it : mp) { if (it.first == 0) demt += gt(it.second); else { demt += gt(it.second - 1); } } cout << demt << endl; }
anh giải thích ý tưởng code của anh được không :((
Nếu là số chẵn, gán thành -1
Nếu là số lẻ, gán thành +1
Như vậy:
Một dãy con có số lẻ = số chẵn ⇨ tổng của dãy con sau biến đổi sẽ bằng 0.
Dùng một map lưu số lần xuất hiện của mỗi prefix_sum.
Nếu tại một thời điểm nào đó, tổng prefix_sum = x, thì số lần ta đã gặp x trước đó chính là số dãy con kết thúc tại vị trí hiện tại có tổng = 0.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
đề bài nói là dãy liên tiếp nhé, ae cẩn thận. tôi làm hết tất cả dãy con muốn sảng luôn mới biết.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.