Dải số
Xem PDF
Điểm:
150
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.
Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.
Input
- Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
- Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)
Output
- Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.
Example
Test 1
Input
4
1 2 2 1Output
1Note
Có \(1\) cách cắt là \([1, 2]\) / \([2, 1]\)
Test 2
Input
6
1 1 1 3 -3 3Output
2Note
Có \(2\) cách cắt là:
- \([1, 1, 1]\) / \([3, -3, 3]\)
- \([1, 1, 1, 3, -3]\) / \([3]\)
Bình luận
bài này test yếu quá có mấy bạn kiểm tra như này if(b[i] == b[n] / 2) mà vẫn ac
-
0
VoBaThongL921
4:27 p.m. 16 Tháng 10, 2021
←
chỉnh sửa 2
→
-
3
LeQuangMinh0903
7:52 p.m. 21 Tháng 10, 2021
-
1
vancongnam
10:19 p.m. 20 Tháng 10, 2021
-
3
PhanHuyKhang
5:44 p.m. 16 Tháng 10, 2021
-
0
VoBaThongL921
5:57 p.m. 16 Tháng 10, 2021
-
1
dang7rickroll
4:30 p.m. 16 Tháng 10, 2021
-
0
VoBaThongL921
4:39 p.m. 16 Tháng 10, 2021
←
chỉnh sửa 2
→
-
0
dang7rickroll
5:11 p.m. 16 Tháng 10, 2021
-
6
nvatuan
3:45 p.m. 16 Tháng 10, 2021
- \(b[i]\) là tổng là từ \(1\) đến \(i\)
- \(b[n]-b[i]\) là tổng từ \(i+1\) đến \(n\)
-
0
PhanHuyKhang
5:45 p.m. 16 Tháng 10, 2021
-
2
nvatuan
6:07 p.m. 16 Tháng 10, 2021
-
2
PhanHuyKhang
6:18 p.m. 16 Tháng 10, 2021
5 bình luận nữamình dùng 2 biến tính tổng rồi xét nếu sum2 * 2 == sum1 thì tăng biến dem lên là xong
mình để điều kiện là b[i] == b[n] - b[i] khỏi phải ktra
b[n] / 2 c++ là chia lấy nguyên bạn nhé nên phải kt b[n] chia hết cho 2 hay ko chưa. Code bạn kt rồi thì mình ko nói gì nhưng có code chưa kt nên mình nói.
à ok bạn, nếu không kiểm tra tổng mảng lẻ hay chẵn thì sai thật:>
sao tôi làm mà vẫn không ac :))
vòng for thứ 2 để check của ông đó, ông phải cho nó chạy đến n - 1 thôi. Tui mới nộp lại code của ông (tui sửa lại for thứ 2 chạy đến n - 1) thì ac mà. Trước tui cũng bị như này:> Vì giả sử tổng của cả mảng là 0, nếu xét đến i = n thì thấy s[i] = s[n] - s[i] = 0 nên bị sai, vì không thể cắt dãy ở cuối cùng của mảng được !
a ;))
Nếu \(b\) là mảng Tổng cộng dồn thì đếm từng vị trí \(i\) mà \(b[i] == b[n]/2\) chính là solution đó bạn.
Giả sử \(b[i] = b[n]/2\),
\(⇔ 2*b[i] = b[n] ⇔ b[i] = b[n] - b[i]\)
Với,
Vậy, \(b[i]=b[n]/2\) sẽ tương đương với yêu cầu đề bài.
dạ anh b[n] / 2 c++ là chia lấy nguyên nên phải kt b[n] chia hết cho 2 hay ko chưa. Có code chưa kt nên e nói.
OK mình thấy bài đó rồi, bộ test thiếu trường hợp tổng là số lẻ, để mình thêm vào. Cảm ơn em
dạ anh