自动搬运

查看原文

来自洛谷，原作者为

	Field_Mouse 待灯灭，穷其一生跟随

搬运于2025-08-24 22:54:22，当前版本为作者最后更新于2024-05-25 20:00:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

给定仅由 $0$ 和 $1$ 构成的字符串 $S$ 和 $T$，你可以翻转 $S$ 的子串，使得其子串中不包含 $T$，求最小操作次数，若无解输出 $-1$。

做法分析

一点思路没有，看数据范围。

发现 $\left |T\right |$ 很小，并且部分分内贴心的给出了特殊的 $T$。考虑分类讨论。显然我们并不在意哪个是 $0$ 哪个是 $1$，只关心他们的相对位置。

记 $\left |T\right |=l$。

• $l=1$

显然看是否存在 $T$，存在即无解，否则输出 $0$。

• $l=2$ 且 $T_1\ne T_2$

形如 $10$，我们发现最终结果一定可以形如 $000\dots0111$，一次翻转可以将一个 $1$ 翻转到后方，答案即为 $01$ 串的个数。

• $l=2$ 且 $T_1=T_2$

形如 $11$，我们发现最终结果一定形如 $1010\dots1000$，对于任意两对 $11$，可以通过一次翻转操作拆散。但如果 $1$ 的数量过半，则一定无解。答案即为 $11$ 串的个数除以二上取整。

• $l=3$ 且形如 $101$

发现这类似于 $11$，答案就是出现次数除以二上取整。

• $l=3$ 且形如 $100$

同样，类似于 $10$，答案即为出现次数。

• $l=3$ 且形如 $110$

发现它也具有不对称的特点，同上，答案即为出现次数。

• $l=3$ 且形如 $111$

这位更是重量级。

我们发现，问题能够转化为让 $S$ 中不存在连续的三个 $1$。即通过翻转让 $1$ 翻到 $0$ 的中间去。为了不让 $1$ 与其它的 $1$ 接上，只有 $11$ 中间或者 $101$ 中间可以容纳 $1$。

$11$ 能容纳 $2$ 个，$101$ 只能容纳 $1$ 个。在操作次数相等的情况下，我们自然想要尽可能多的使用 $11$，所以可以想到一个贪心策略：尽可能的使用 $11$，在剩余不到 $2$ 个或没有 $11$ 后再使用 $101$。正确性是显然的。

那就统计之后再讨论就好了。如果两种操作都不剩了，那就是无解。

细节看代码。

#include<bits/stdc++.h>
#define AC return 0;
#define pr(n) printf("%d",(n))
#define hh puts("")
#define kg printf(" ")
using namespace std;
namespace fr{
	int read()
	{
		int x=0,flag=1;
		char ch=getchar();
		for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')flag=-1;
		for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
		return flag*x;
	}
}
using namespace fr;
string s,t;
bool cmp(int a,int b){return a>b;}
void sol1()//1
{
	char a=t[0];
	for(auto i:s)if(i==a){puts("-1");return ;}
	puts("0");
}
void sol2()//10
{
	int res=0;
	for(int i=0;i<s.size()-1;++i)
	{
		if(s.substr(i,2)==t)++res;
	}
	pr(res);
}
void sol3()//11
{
	char a=t[0];
	int cnt=0,res=0;
	for(int i=0;i<s.size();++i)
	{
		if(s[i]==a)
		{
			++cnt;
			if(i>0)
			{
				if(s[i-1]==s[i])++res;
			}
		}
	}
	if(cnt>(s.size()+1)>>1)pr(-1);
	else pr(res);
}
void sol4()//111
{
	vector<int> p;
	int res1=0,res2=0,cnt=0,now=0;
	bool flag1=0,flag2=0;
	string s1,s2;
	if(t[0]=='0')s1="11",s2="101";
	else s1="00",s2="010";
	for(int i=0;i<(int)s.size();i++)
	{
		if(s[i]==t[0])++now;
		else 
		{
			p.push_back(now);now=0;
			if(i==0)res1+=1,flag1=1;
			if(!flag1&&i==1)res2+=1;
			if(i==(int)s.size()-1)
			{
				flag2=1,res1+=1;
			}
			if(!flag2&&s[(int)s.size()-2]!=t[0])res2+=1;
			if(i+1<s.size())
			{
				if(s.substr(i,2)==s1)res1++;
				else if(i+2<s.size())
				{
					if(s.substr(i,3)==s2)res2++;
				}
			}
		}
	}
	p.push_back(now);
//	cout<<res1<<" "<<res2<<endl;

	sort(p.begin(),p.end(),cmp);
	for(auto i:p) 
	{
		if(i<3)continue;
		//if(i%2)continue;
		i-=2;
	//	if(i==1&&res2){res2--;cnt++;continue;}
		if(res1>=(i>>1)){res1-=(i>>1);cnt+=(i>>1);i%=2;}
		else if(res1){i-=2*res1;cnt+=res1;res1=0;}
		if(!res2){res1-=(i+1)>>1;res2+=(i+1)>>1;}//没有101了可以尝试兑换一点11（
		cnt+=i;
		res2-=i;
		if(res2<0||res1<0){puts("-1");return;}
	}
	pr(cnt);
}
void sol5()//101
{
	int res=0;
	for(int i=0;i<(int)s.size()-2;++i)
	{
		if(s.substr(i,3)==t)++res;
	}
	res=(res+1)>>1;
	pr(res);
}	
void sol6()//100&&110
{
	int res=0;
	for(int i=0;i<(int)s.size()-2;i++)
	{
		if(s.substr(i,3)==t)++res;
	}
	pr(res);
}
int main()
{
	cin>>s;cin>>t;
	if(t.size()==1)sol1();
	if(t.size()==2&&t[0]==t[1])sol3();
	if(t.size()==2&&t[0]!=t[1])sol2();
	if(t.size()==3&&t[0]==t[1]&&t[1]==t[2])sol4();
	if(t.size()==3&&t[0]==t[2]&&t[0]!=t[1])sol5();
	if(t.size()==3&&t[0]==t[1]&&t[1]!=t[2])sol6();
	if(t.size()==3&&t[1]==t[2]&&t[0]!=t[1])sol6();
	AC
}