Codeforces Round #545 (Div. 2)-Camp Schedule
题目要求，给定一个s序列，一个p序列，问能不能对s做相应的调整，使得s序列中，有尽可能多的p子串（可以重复）
最开始我拿到这个题目，也是一点头绪都没有，如何做调整呢？
首先考虑如何会有尽可能多的子串，可以相交那种？
貌似我们要找的就是子串后缀和前缀匹配度
这里再次补充一下KMP中next数组的意义
首先要理解next数组的含义：https://www.cnblogs.com/chenxiwenruo/p/3546457.html
那么我们通过求next数组，很容易知道知道，t的最小循环长度是k=len_t-next[len_t]
但是最小循环长度是k，我们需要尽量多的构造这个最小循环，并且放在一起，余下的尽量按照最小循环进行往后匹配
当时补题的时候，我自己在想，我们已经把尽量多的最小循环个数的构造出来了，余下的是不是不用再安装最小循环进行
匹配呢？事实上是不行的，我们知道最小循环的意思是，把原本长度数组，可以用它的某个前缀进行循环表示。所以构造的字符，最后k个仍然只是前缀，如果匹配完的1,0仍然剩余，我们需要把1,0安装原来序列继续匹配，如果数量够的话，是会增加子串个数的。。。
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace std; const int maxx = 500000+5; char s[maxx]; char t[maxx]; int net[maxx]; int len_s; int len_t; void get_next() { net[1]=0; for (int i=2,j=0; i<=len_t; i++) { while(j>0 && t[i]!=t[j+1])j=net[j]; if(t[i]==t[j+1])j++; net[i]=j; } } int main() { int n,cnt_s,k,p,a,b,time; while(~scanf("%s",1+s)) { scanf("%s",1+t); len_s=strlen(s+1); len_t=strlen(t+1); a=0; for (int i=1; i<=len_s; i++) { a+=s[i]-'0'; } b=len_s-a; len_t=strlen(t+1); get_next(); k=len_t-net[len_t];//最小循环节长度 cout<<k<<endl; p=0; for (int i=1; i<=k; i++) { p+=t[i]-'0'; } if(p==0) { time=b; }else if (p==k){ time=a; } else { time=min(a/p,b/(k-p)); } for (int i=1;i<=time;i++){ for (int j=1;j<=k;j++){ printf("%c",t[j]); } } a-=time*p,b-=time*(k-p); int g=1; while(a||b){ if(b){ printf("0"); b--; } if(a){ printf("1"); a--; } } printf("\n"); } return 0; }
腾讯公司福利 467人发布
