翻转

问题描述

小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n 的 01 串 T，他发现如果把黑棋当做 1，白棋当做 0，这一行棋子也是一个长度为 n 的 01 串 S。

小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 S 中存在子串 101 或者 010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。

小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。

输入格式

输入包含多组数据。

输入的第一行包含一个正整数 D 表示数据组数。

后面 2D 行每行包含一个 01 串，每两行为一组数据，第 2i−1 行为第 i 组数据的 T_i，第 2i 行为第 i 组数据的 S_i，S_i 和 T_i 长度均为 n_i。

输出格式

对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −1。

样例输入

2
1000111
1010101
01000
11000

样例输出

2
-1

评测用例规模与约定

对于 20% 的评测用例：

对于所有评测用例，保证：

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	10s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

来自: 0翻转 – 蓝桥云课

我的题解

def turn_over(strings_list, d):
    """
    检查每对相邻字符串，根据特定规则进行翻转操作，并统计每个字符串所需的操作次数。
    
    :param strings_list: 包含成对字符串的列表。
    :param d: 字符串对的数量。
    :return: 包含每个字符串对操作次数的列表，如果无法完成操作则为-1。
    """
    count = [0] * d  # 初始化操作计数数组
    
    for i in range(1, d * 2, 2):  # 遍历每一对字符串
        prev, curr = strings_list[i - 1], list(strings_list[i])

        # 检查首尾字符是否相同，不相同则标记为-1并跳过当前对
        if prev[0] != curr[0] or prev[-1] != curr[-1]:
            count[i // 2] = -1
            continue

        changes = 0  # 初始化字符变化计数
        for j in range(1, len(curr) - 1):  # 遍历当前字符串中间字符
            # 如果当前字符与两侧字符都不相等，则将其更改为左侧字符，并计数
            if prev[j] != curr[j] and curr[j] != curr[j - 1] and curr[j] != curr[j + 1]:
                curr[j] = curr[j - 1]
                changes += 1

        curr = ''.join(curr)  # 将字符列表转换回字符串
        if prev != curr:  # 如果经过操作后前后字符串不一致，则标记为-1
            count[i // 2] = -1
        else:
            count[i // 2] = changes  # 否则，记录变化次数

    return count


if __name__ == '__main__':
    d = int(input())  # 读取字符串对数量
    strings_list = [input() for _ in range(d * 2)]  # 读取所有字符串
    print(*turn_over(strings_list, d), sep="\n")  # 打印结果

AI 题解

360GPT_V2_S9

以下是用Python解决上述问题的代码：

def flip_count(s, t):
    flip_count = 0
    i = 0
    while i < len(s):
        if s[i] != t[i]:
            if i > 0 and i < len(s) - 1 and s[i-1] == s[i+1]:
                flip_count += 1
                i += 2
            elif i < len(s) - 1 and s[i+1] == t[i]:
                flip_count += 1
                i += 2
            else:
                return -1
        else:
            i += 1
    return flip_count

def solve(d):
    for _ in range(d):
        t = input()
        s = input()
        print(flip_count(s, t))

if __name__ == "__main__":
    d = int(input())
    solve(d)

代码解释：

1. 我们首先定义一个名为flip_count的函数，它接受两个参数：两个01串s和t。这个函数计算将s翻转成t所需的最少次数。
2. 在函数内部，我们使用一个while循环遍历串s。在循环中，我们首先检查当前字符是否与对应位置的字符不同。如果是，我们检查当前位置的前一个字符和后一个字符是否相同，如果是，我们增加翻转计数器，并将索引增加2，以便跳过已经翻转的字符。否则，我们检查下一个字符是否与当前字符相同且与t[i]相同，如果是，则增加翻转计数器，并将索引增加2。如果以上条件都不满足，则返回-1，表示无法将s翻转成t。如果当前字符与对应位置的字符相同，则将索引增加1，继续循环。
3. 我们定义一个名为solve的函数，它接受一个参数d，表示数据组数。这个函数用于解决给定数据组的问题。在函数内部，我们使用一个for循环遍历每个数据组。在循环中，我们分别读取两个01串s和t，然后调用flip_count函数计算将s翻转成t所需的最少次数，并将结果打印到输出。
4. 最后，我们从标准输入读取数据组数d，并调用solve函数解决问题。

---

存档地址：https://www.yuque.com/worthstudy/study/dls1nvgi3sewfee8?singleDoc# 《翻转》