CSES - One Bit Positions | Các vị trí bit 1 - LQDOJ: Le Quy Don Online Judge

CSES - One Bit Positions | Các vị trí bit 1

Tác giả:

Dạng bài

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu nhị phân có độ dài \(n\). Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\) đếm số cách chọn \(i\) và \(j\) sao cho \(i - j = k\) và cả hai vị trí đều chứa bit \(1\).

Input

Một dòng duy nhất chứa một xâu chỉ bao gồm kí tự \(0\) và \(1\).

Output

Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\), in ra số cách có thể chọn được hai vị trí như vậy.

Constraints

\(2 \ \leq \ n \ \leq \ 2 \times 10^5\)

Example

Sample input

1001011010

Sample output

1 2 3 0 2 1 0 1 0

Bình luận

0

tk22NguyenMinhPhuc 12:01 p.m. 5 Tháng 11, 2023

có ai giản bài này cho mình được ko ?
python nha

ĐÂY LÀ ĐOẠN MÃ TLE:

def count_ways(binary_string):
    n=len(binary_string);ones_positions=[i for i in range(n) if binary_string[i] == '1'];count=[0]*n
    for i in range(len(ones_positions)):
        for j in range(i+1, len(ones_positions)):k = ones_positions[j] - ones_positions[i];count[k] += 1
    return count[1:n]
binary_string = input().strip()
result = count_ways(binary_string)
print(' '.join(map(str, result)))

2 bình luận nữa