題目鏈接：點擊查看

題目大意：給出一個主字符串s，再給出一個子字符串ss，主串和子串都是只由0或1所組成的字符串，現(xiàn)在要求重組主串s，要求重組后的字符串：

所包含的0與1的個數(shù)與之前保持一致

盡可能多的包含子串ss

求出重組后滿足上述條件的字符串

題目分析：這個題目一開始我想簡單了，就用貪心去構(gòu)造了，是可以過掉樣例，以及寥寥幾個測試點的，后來隊友提醒我了才知道，原來子串ss在新構(gòu)造的字符串中是可以重疊的！也就是說若給出的主串是111000，子串是1010，我們需要構(gòu)造成101010，這樣可以包含兩個子串，大概就是因為可以重疊的原因，所以就不能直接貪心構(gòu)造了，或者說貪心的話情況比較難討論，因為涉及到了重疊問題，我們可以想到KMP中next數(shù)組的定義了，next數(shù)組的定義就是前綴和后綴的最大匹配度，當(dāng)我們構(gòu)造完一個子串s后，我們接下來不用從頭再開始構(gòu)造子串，而是尋找一下最大前綴和后綴所匹配的地方，然后在這個地方后面的一個單位繼續(xù)構(gòu)造即可，因為都匹配了，所以上一個構(gòu)造好的子串的后綴，就可以充當(dāng)下一個需要構(gòu)造的子串的前綴，這樣構(gòu)造的話，最后答案一定是最優(yōu)解

對了，這個題目記得用char字符串，用stirng類會超時

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;char a[N],b[N],ans[N];int nx[N];int cnt[2];void getnext()//得到子串的next數(shù)組 {nx[0]=-1;int i=0,j=-1;int len=strlen(b);while(i<len){if(j==-1||b[j]==b[i])nx[++i]=++j;elsej=nx[j];} }int main() { // freopen("input.txt","r",stdin);scanf("%s%s",a,b);int lena=strlen(a);int lenb=strlen(b);for(int i=0;i<lena;i++)cnt[a[i]-'0']++;getnext();for(int i=0,j=0;i<lena;i++,j++){if(j==lenb)//若當(dāng)前子串的指針到頭了，就回到前綴后的位置j=nx[j];if(cnt[b[j]-'0'])//如果需要構(gòu)造的元素還有，就直接用{ans[i]=b[j];cnt[b[j]-'0']--;}else//否則就只能用另一種元素了{ans[i]='0'+(b[j]-'0')^1;cnt[(b[j]-'0')^1]--;}}printf("%s\n",ans);return 0; }

?

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1137B Camp Schedule(KMP的next数组+构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。