codeforce：C. Sum of Substrings【边界处理 + 贡献思维 + 灵光一现】

分析

我们想让f最小
边界情况：没有1答案总是0
然后的话每个1，如果在中间的话贡献一定是1 + 10 = 11
唯一可能降低贡献的就是放在一头一尾
放在头：贡献变成10
放在尾：共享变成1
于是我们统计s所有1离头和尾最近的距离d1和d2
然后优先走到尾
判断k的取值是否大于等于d1 + d2, d2, d1分成四个状态
特别地，如果只有一个1的情况下，不可能又去头又去尾巴
所以这种情况当其大于等于d1 + d2就去d2即可

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)

总结

思维 + 贡献 + 边界处理