Codeforces 1353E - K-periodic Ga

大概是我很懒的缘故，所以很喜欢看懒懒的猫咪，也许上辈子我是只大懒猫吧。

翻译

K周期花环

给你一个有n个灯的花环，灯的状态用长度为 n 的字符串 s 表示。如果第 i 个灯是开着的，那么 s[i] 就是 '0'，如果第 i 个灯是关着的，那么 s[i] 就是 '1'。当然，也给你一个正整数 k。

每一次移动，你可以选择一个灯，改变它的状态。

如果这个花环每个相邻的开着的灯的距离都是 k，那么他被称为 k 周期花环。注意，这个花环不是一个圈，第一个开着的灯不在最后一个开着的灯后面。

你的任务是找到最少的移动步数，将花环变成 k 周期花环。

输入格式

第一行输入整数 t，表示有 t 组测试用例。

每个测试用例输入两行。

第一行输入整数 n k，用逗号分隔。

第二行输入长度为 n 的字符串，只包含 '0' 和 '1'。

可以保证，所有 n 的和不超过 10^6。

输出格式

输入最小的步数。

分析

这道题是一条动态规划题目，分析起来挺麻烦的，为此还写了很多debug代码。

动态规划需要做两次，分别是从左往右和从右往左，为了复用逻辑，第二遍就是翻转字符串再做一次从左往右的递归。

递推的结果就是，当前位置如果是 0 还有 1 时，分别需要多少步。假设当前位置需要改成 0，那么就为前 k 位也需要是 0 的情况，加上当前需要修改的次数。假设当前位置需要改成 1，那么前 k 位需要是 0 或者是 1 两者的最小值，因为不是循环，前导 0 可以符合条件。这也就是核心的递推公式。

以上需要计算每个位置的前 k - 1 位置有多少个 1，为了加速，会用滚动计算的方式预处理好前 k - 1 位包含 1 的数量。

给出一个很特殊的测试用例。

2
1 1
0
18 2
100000010100000001

答案分别是

0
2

第一个很好理解，第二个就是两边1都为 0 的情况。

代码(PyPy3)

# https://codeforces.com/contest/1353/problem/E

import sys
import os
import heapq

try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass

t = int(input())

def printd(value):
    # print(value)
    pass

for _ in range(t):
    arr = list(map(int, input().split(" ")))
    n, k = arr[0], arr[1]
    str = input()
    count = len(str)
    leftone = [0] * count
    leftzero = [0] * count
    rightone = [0] * count
    rightzero = [0] * count

    one = [0] * count
    # zero = [0] * count

    sum = 0
    for i, c in enumerate(str):
        if i > 0:
            sum += 1 if str[i - 1] == '1' else 0

        if i >= k:
            sum -= 1 if str[i - k] == '1' else 0

        one[i] = sum

    printd(str)
    printd(one)

    for i, c in enumerate(str):
        number = 1 if c == '0' else 0
        numberzero = 0 if c == '0' else 1
        if i >= k:
            number += min(leftone[i - k], leftzero[i - k])
            numberzero += leftzero[i - k]
        leftone[i] = one[i] + number
        leftzero[i] = one[i] + numberzero
    
    printd(leftone)
    printd(leftzero)

    printd("--right---")

    str = str[::-1]
    sum = 0
    for i, c in enumerate(str):
        if i > 0:
            sum += 1 if str[i - 1] == '1' else 0

        if i >= k:
            sum -= 1 if str[i - k] == '1' else 0

        one[i] = sum


    printd(str)
    printd(one)

    for i, c in enumerate(str):
        number = 1 if c == '0' else 0
        numberzero = 0 if c == '0' else 1
        if i >= k:
            number += min(rightone[i - k], rightzero[i - k])
            numberzero += rightzero[i - k]
        rightone[i] = one[i] + number
        rightzero[i] = one[i] + numberzero
    
    printd(rightone)
    printd(rightzero)

    leftone.reverse()
    leftzero.reverse()

    result = 99999999
    for i, c in enumerate(str):
        value = leftone[i] + rightone[i]
        value -= 1 if c == '0' else 0
        result = min(result, value)

        value = leftzero[i] + rightzero[i]
        value -= 0 if c == '0' else 1
        result = min(result, value)

    print(result)

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.22 长春