Codeforce:c. sum of substrings

analysis

We want to make f Minimum
Boundary situation ： No, 1 The answer is always 0
Then each 1, If in the middle, the contribution must be 1 + 10 = 11
The only way to reduce the contribution is to put it on one end
Put it on your head ： Contribution becomes 10
Put at the end ： Sharing becomes 1
So we count s all 1 The closest distance from the head and tail d1 and d2
Then go to the end first
Judge k Whether the value of is greater than or equal to d1 + d2, d2, d1 It is divided into four states
Specially , If only one 1 Under the circumstances , It's impossible to go head and tail again
So this situation should be greater than or equal to d1 + d2 Just go to d2 that will do

ac code

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    s = input()
    cnt_1 = 0
    for c in s:
        if c == '1':
            cnt_1 += 1

    if cnt_1 == 0:
        print(0)
        continue

    d1, d2 = 0, 0 # d1 from head, d2 from tail
    for i in range(n):
        if s[i] == '1':
            d1 = i
            break

    for i in range(n):
        if s[n - 1 - i] == '1':
            d2 = i
            break

    # 1: not change
    # 2: go to head
    # 3: go to tail
    # 10: go to tail and head
    # we are delighted to go to tail first, and secondly go to head
    flag = 1
    if k >= d1 + d2:
        flag = 10
    elif k >= d2:
        flag = 3
    elif k >= d1:
        flag = 2
    else:
        flag = 1

    # different cases
    ans = 0
    if flag == 10:
        if cnt_1 >= 2:
            ans = 1 + 10 + 11 * (cnt_1 - 2) # cnt_1 >= 2
        else:
            ans = 1
    elif flag == 3:
        ans = 1 + 11 * (cnt_1 - 1)
    elif flag == 2:
        ans = 10 + 11 * (cnt_1 - 1)
    else:
        ans = 11 * cnt_1

    print(ans)

summary

thinking + contribution + Boundary treatment