2023年第十四届蓝桥杯省赛真题_问题A

提交: 6716 解决: 1771

题目描述

小蓝用黑白棋的 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
-1

提示

对于 20% 的评测用例，1 ≤∑^D₁ n_i ≤ 10 ；
对于所有评测用例，保证 1 ≤∑^D₁ n_i ≤ 10⁶，n_i > 0 。

请基地所有同学们认真做题，以后每天发布一套蓝桥杯历年真题。积极备赛，争取省一。加油！