题解：P10069 [CCO2023] Flip it and Stick it
Field_Mouse
·
·
题解
题意简述
给定仅由 0 和 1 构成的字符串 S 和 T，你可以翻转 S 的子串，使得其子串中不包含 T，求最小操作次数，若无解输出 -1。
做法分析
一点思路没有，看数据范围。
发现 \left |T\right | 很小，并且部分分内贴心的给出了特殊的 T。考虑分类讨论。显然我们并不在意哪个是 0 哪个是 1，只关心他们的相对位置。
记 \left |T\right |=l。
显然看是否存在 T，存在即无解，否则输出 0。
形如 10，我们发现最终结果一定可以形如 000\dots0111，一次翻转可以将一个 1 翻转到后方，答案即为 01 串的个数。
形如 11，我们发现最终结果一定形如 1010\dots1000，对于任意两对 11，可以通过一次翻转操作拆散。但如果 1 的数量过半，则一定无解。答案即为 11 串的个数除以二上取整。
发现这类似于 11，答案就是出现次数除以二上取整。
同样，类似于 10，答案即为出现次数。
发现它也具有不对称的特点，同上，答案即为出现次数。
这位更是重量级。
我们发现，问题能够转化为让 S 中不存在连续的三个 1。即通过翻转让 1 翻到 0 的中间去。为了不让 1 与其它的 1 接上，只有 11 中间或者 101 中间可以容纳 1。
那就统计之后再讨论就好了。如果两种操作都不剩了，那就是无解。
细节看代码。
```
#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
}
```