题目描述:
小蓝用黑白棋的n个棋子排成了一行,他在脑海里想象出了一个长度为n的01串T,他发现如果把黑棋当做1,白棋当做0,这一行棋子也是一个长度为n 的01串S。
小蓝决定,如果在S中发现一个棋子和它两边的棋子都不一样,就可以将其翻转变成另一个颜色。也就是说,如果S中存在子串101或者010,就可以选择将其分别变为111和000,这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把S变成和T一模一样。
输入格式:
输入包含多组数据。
输入的第一行包含一个正整数D表示数据组数。
后面 2D 行每行包含一个01串,每两行为一组数据,第2*i-1行为第i组数据的T,第 2*i行为第i组数据的 Si,S¡和T 长度均为ni文章来源:https://www.toymoban.com/news/detail-814653.html
输出格式:
对于每组数据,输出一行包含一个整数,表示答案,如果答案不存在请输出 -1。文章来源地址https://www.toymoban.com/news/detail-814653.html
大体思路 :
1、这个题关键就是读懂题找到谁是T谁是S 2、还有以谁为基准的对应关系即可解题
AC代码如下:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
n = n*2;
string s[n];
for(int i=0;i<n;i++) cin >> s[i];
//这里的i+=2很巧妙,可以手算模拟一下
for (int i = 1; i < n; i +=2 )
{
int k = 0;
int cnt = 0;//计算改变次数
bool is_same = true;
while(k<s[i].size())
{
//我们可以发现 一个规律就是如果前面两个数不一样
//那一定是不行的
if(s[i][0] != s[i-1][0])
{
is_same = false;
break;
}
else
{
k++;
//跟前后去做比较
if(s[i][k] != s[i-1][k])
{
if(s[i][k] != s[i][k-1] && s[i][k] != s[i][k+1] && s[i][k-1] == s[i][k+1])
{
if(s[i][k] == '0')
{
s[i][k] = '1';
cnt++;
}
else
{
s[i][k] = '0';
cnt++;
}
}
}
}
}
if(s[i] != s[i-1]) is_same = false;
if(is_same) cout << cnt << endl;
else cout << "-1" << endl;
}
return 0;
}
到了这里,关于第十四届蓝桥杯省赛PythonA/C组------翻转的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!