Binary Strings
发布时间
阅读量：
阅读量
Binary Strings
题目描述：
这个题目讲述的是，给定两个字符串
和
这些二进制字符串由0与1构成，并定义了两个基本的操作：第一个操作是将字符串末尾的字符移动至首位位置；第二个操作是翻转相邻的两个字符。本题假设首尾字符被视为相邻，并询问最少需要执行多少次第二种操作才能达到目标状态。
变成
，如果不能通过以上两个操作使字符串
变成
的话，那么输出-1。
题目分析：
首先
中0的数量与字符串
中0的数量奇偶性不一样的话，输出-1。
接下来，我们要求出从字符串
变成
的最少操作次数，首先我们要知道，不同位置实行第二个操作来使字符串
变成
，操作次数是不一样的，因此我们要对字符串
遍历每一个字符的位置，在该位置上执行第一个操作；接着对该位置执行后续操作；使得字符串完成相应的处理过程
变成
，求出最少的操作次数。
代码：
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#define reg register
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-3
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define lowbit(x) (x&(-x))
using namespace std;
const int Maxn=5005;
char A[Maxn*2],B[Maxn];
int n,ans;
void solve(char *s,int cnt)
{
for (int i=0;i<n-1;i++)
if (s[i]!=B[i])
{
s[i]='1'-(s[i]-'0');
s[i+1]='1'-(s[i+1]-'0');
cnt++;
}
if (s[n-1]==B[n-1]) ans=min(ans,cnt);
}
int main()
{
scanf("%s%s",A,B);
int num1=0,num2=0;
n=strlen(A);
for (int i=0;i<n;i++)
if (A[i]=='0') num1++;
for (int i=0;i<n;i++)
if (B[i]=='0') num2++;
if ((num1&1)!=(num2&1))
{
printf("-1\n");
return 0;
}
for (int i=0;i<n;i++) A[i+n]=A[i];
ans=INF;
for (int i=0;i<n;i++)
{
char c[Maxn];
memcpy(c,A+i,sizeof(char)*n);
solve(c,0);
memcpy(c,A+i,sizeof(char)*n);
c[0]='1'-(c[0]-'0');
c[n-1]='1'-(c[n-1]-'0');
solve(c,1);
}
printf("%d\n",ans);
return 0;
}全部评论 (0)
还没有任何评论哟~