Codeforces Round #545 (Div. 2)（D. Camp Schedule）

题目链接：http://codeforces.com/contest/1138/problem/D

题目大意：给你两个字符串s1和s2（只包含0和1），对于s1中，你可以调换任意两个字符的位置。问你最多能在s1中构造出几个s2（可重叠）。

具体思路：首先找到字符串s2的最小循环节，比如说1101，我们找到的最小循环节就是101，这样的话，我们每次在后面加上101就能构造出一个新的1101了，最小循环节是最小的代价。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 6e5+100;
 4 char str1[maxn],str2[maxn];
 5 char str[maxn];
 6 int nex[maxn];
 7 void getnex(int len){
 8 nex[0]=-1;
 9 int i=0,j=-1;
10 while(i<len){
11 if(j==-1||str2[i]==str2[j]){
12 i++;
13 j++;
14 nex[i]=j;
15 }
16 else {
17 j=nex[j];
18 }
19 }
20 }
21 int main(){
22 scanf("%s %s",str1,str2);
23 int len1=strlen(str1);
24 int len2=strlen(str2);
25 getnex(len2);
26 int len=0;
27 int tmp=len2-nex[len2];
28 for(int i=len2-tmp;i<=len2-1;i++){
29 str[len++]=str2[i];
30 }
31 //cout<<str<<endl;
32 int s0=0,s1=0;
33 for(int i=0;i<len1;i++){
34 if(str1[i]=='1')s1++;
35 if(str1[i]=='0')s0++;
36 }
37 int t0=0,t1=0;
38 for(int i=0;i<len2;i++){
39 if(str2[i]=='1')t1++;
40 if(str2[i]=='0')t0++;
41 }
42 if(s0<t0||s1<t1){
43 printf("%s
",str1);
44 return 0;
45 }
46 t0=0,t1=0;
47 for(int i=0;i<len;i++){
48 if(str[i]=='1')t1++;
49 if(str[i]=='0')t0++;
50 }
51 for(int i=0;i<len2-tmp;i++){
52 printf("%c",str2[i]);
53 if(str2[i]=='1')s1--;
54 else s0--;
55 }
56 while(s0>=t0&&s1>=t1){
57 s0-=t0;
58 s1-=t1;
59 printf("%s",str);
60 }
61 while(s0>0)printf("0"),s0--;
62 while(s1>0)printf("1"),s1--;
63 printf("
");
64 }