[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
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; }
Tôi đã bất cẩn khi phức tạp hóa vấn đề.
đề 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.