题目: https://codeforces.com/contest/1137/problem/B

题目大意:给一个01字符串S和T,不改变S中0,1的数目,重组S使得T为其子串并且尽可能多的出现

最开始以为T不能重叠,以为是个傻逼题,wa了后发现T可以重叠,就相当于让T的前缀与后缀尽可能多的重合,比如当T为101时 构造的S尽可能为10101… 观察一下不难发现,我们只需要求T的最小循环节t,然后在S中不断重复构造t就行.

T的最小循环节长度为 T.size()-next[T.size()]

代码写的很丑 不想改了()

#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef unsigned long long ll; string s,t; int nex[500005]; void init() { int k=-1,j=0; nex[0]=-1; while(j<=t.size()) { if(k==-1||t[k]==t[j]) { ++k; ++j; nex[j]=k; } else k=nex[k]; } // for(int i =0;i<=t.size();i++) // cout<<nex[i]<<" "; // cout<<endl; } int main() { ios::sync_with_stdio(0); cin>>s>>t; init(); int x=0,y=0,a=0,b=0; for(int i =0;i<s.size();i++) if(s[i]=='0') x++; else y++; int tmp=t.size()-nex[t.size()]; for(int i=0;i<tmp;i++) { if(t[i]=='0') a++; else b++; } int j=0,aa=a,bb=b; for(int i =0;i<s.size();i++) { if(j==tmp) aa=a,bb=b,j=0; if(t[j]=='0'&&x>0&&aa>0) { x--; aa--; j++; cout<<0; } else if(t[j]=='1'&&y>0&&bb>0) { y--; bb--; j++; cout<<1; } else if(x>0) { x--; cout<<0; } else if(y>0) { y--; cout<<1; } } return 0; }