Codeforces 1363B - Subsequence H

日常一道算法题。

翻译

有一个二进制字符串 s，字符串内只有两种字符 "0" 和 "1"

你可以执行任意次数的以下操作：

• 选择一个字符，翻转它的值。意思就是，可以将它从 "0" 变成 "1"，或者从 "1" 变成 "0"。

如果一个字符串的子串不包括 010 或者 101，那么它被称为好字符串。子串是从原串删除任意字符的结果。

请问，让一个字符串变成好字符串的最小操作次数。

输入格式

输入整数 t 表示测试用例数。

每个测试用例输入一行字符串 s

输出格式

输出最小操作次数

分析

题目就是要求将字符串变成没有交替的 0 和 1，得到的结果就是四种，全 0，全 1，左 0 右 1，左 1 右0。

可以想到，没有第五种情况。

为了加快效率，需要预处理每个位置的左边有多少个 0 和 1，右边有多少个 0 和 1。

这样一组合就能算出四种情况，然后得出最小值。

这个题目思路好像遇见过。

代码(Python 3)

image.png

# https://codeforces.com/problemset/problem/1363/B

import sys
import os
import heapq
import math

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

def case():
    s = input()

    leftzero = [0] * len(s)
    leftone = [0] * len(s)

    for index in range(len(s)):
        if index > 0:
            leftzero[index] = leftzero[index - 1]
            leftone[index] = leftone[index - 1]
        
            if s[index - 1] == '1':
                leftone[index] += 1
            else:
                leftzero[index] += 1

    rightzero = [0] * len(s)
    rightone = [0] * len(s)

    for index in range(len(s) - 1, -1, -1):
        if index < len(s) - 1:
            rightzero[index] = rightzero[index + 1]
            rightone[index] = rightone[index + 1]
        
            if s[index + 1] == '1':
                rightone[index] += 1
            else:
                rightzero[index] += 1

    result = len(s)
    for index, c in enumerate(s):
        result = min(result, leftone[index] + rightone[index] + int(s[index]))
        result = min(result, leftzero[index] + rightzero[index] + 1 - int(s[index]))
        result = min(result, leftzero[index] + rightone[index])
        result = min(result, leftone[index] + rightzero[index])
    
    print(result)

for _ in range(t):
    case()

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

by 费城的二鹏 2020.06.05 长春