Camp Schedule
Camp Schedule
CF 1137 B
题目来源：Codeforces
分析
题目给出两个01串s和t，要求对s进行重新排列，令其含有尽可能多的t的子串。最简单的看，我们只需要令s被尽可能多的t的子串构成即可。
但实际上，如果t中存在部分前缀和部分后缀相同的情况的话就会非常麻烦。此外，还有可能t本身就是由数个重复串组成的。这时，我们可以用KMP中的fail[]数组来解决这个问题。
首先，我们需要先找出t中的循环节。注意，这时我们考虑的循环节，包括了t中的最后的后缀是循环节的一部分但并不是一个完整的循环节的情况（譬如，ababa的循环节即为ab，因为a也是ab的前缀，只是不是一个完整的循环节）。找出该循环节，我们其实可以用以下代码实现(参考于Cyclic Nacklace [KMP变型])：
1
2
| for (int i = t.length(); i>0; i = fail[i])
x = max(x, i - fail[i]);
|
这样，我们其实只需要看s中有多少个t的循环节就好了。然后我们减去t本身有多少个循环节再加一即为答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <iostream>
#include <algorithm>
#include <string>
#define MAXN 500100
using namespace std;
string s, t;
int fail[MAXN];
void getFail(string s)
{
fail[0] = 0;
for (int i = 1; i<s.length(); i++)
{
int j = fail[i];
while (j && s[i]!=s[j])
j = fail[j];
fail[i+1] = s[i]==s[j]? j+1 : 0;
}
}
int cnt[2];
int sum[2];
string str;
int main()
{
cin >> s;
cin >> t;
getFail(t);
str = "";
int lent = t.length();
int lens = s.length();
int x = t.length();
for (int i = t.length(); i>0; i = fail[i])
x = max(x, i - fail[i]);
for (int i = 0; i<lent; i++)
cnt[ t[i] - '0' ] ++;
for (int i = 0; i<lens; i++)
sum[ s[i] - '0' ] ++;
if (sum[0] >= cnt[0] && sum[1] >= cnt[1])
{
cout << t;
sum[0] -= cnt[0];
sum[1] -= cnt[1];
cnt[0] = 0;
cnt[1] = 0;
for (int i = fail[lent]; i<lent; i++)
{
cnt[ t[i] - '0' ] ++;
str += t[i];
}
while (sum[0] >= cnt[0] && sum[1] >= cnt[1])
{
cout << str;
sum[0] -= cnt[0];
sum[1] -= cnt[1];
}
while (sum[0]--)
cout << 0;
while (sum[1]--)
cout << 1;
cout << endl;
}else
cout << s << endl;
}
|