大概是我很懒的缘故，所以很喜欢看懒懒的猫咪，也许上辈子我是只大懒猫吧。
翻译
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 长春
