翻转（蓝桥杯2023大学C组试题E）

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

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

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

     输入：输入包含多组数据。输入的第一行包含一个正整数D，表示数据的组数。后面2D行，每行包含一个01串，每两行为一组数据，第2i-1行为第i组数据的Ti(i)为下标，第2i行为第i组数据的Si(i为下标)，Si(i为下标)和Ti(i)为下标的长度均为ni（i为下标）。

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

【输入样例】

2

1000111

1010101

01000

11000

【输出样例】

2

-1

【试题解析】

       这是一道思维题。

      什么时候无解？如果第一颗或最后一颗棋子不同，无解。因为第一颗和最后一颗棋子不能翻转。

      每颗能翻动的棋子只能翻一次，因为翻过之后，它和相邻棋子一样不能再翻了。要使S和T最终一样，那么每颗不同的棋子都要翻一次。所以一种简单且正确的方法是从左到右枚举，从S的第2颗棋子开始，与T比较，如果不同，就尝试翻动。如果能翻成一样，就继续翻，如果不能翻成一样，就无解。

【参考程序如下】

#include <stdio.h>
#include <string.h>
using namespace std; 
char s[1000010],t[1000010];
int main(int argc, char** argv)
 {
int D;
scanf("%d",&D);
while(D--)
{
scanf("%s",s + 1);
scanf("%s",t + 1);
int n = strlen(s + 1);
if(s[1] != t[1] || s[n] != t[n]) {
       puts("-1");
       continue;}
   int ans = 0;
   for(int i = 2; i < n; i++)
    if(s[i] != t[i])
{
    if(t[i] != t[i - 1] && t[i] != t[i + 1])  //中间的棋子和两边不同 
    {
    t[i] = t[i + 1];
    ans++;
}
else
{
ans = -1;
break;
}

   printf("%d\n",ans);
}
return 0;
  }
}

原文地址：https://blog.csdn.net/2401_84379088/article/details/144652377

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！