true
Minimax
Codeforces Round #733 (Div. 1 + Div. 2)
提高+ /省选-
#3498db
题目大意是，给定我们一个字符串，我们需要对其进行重排，使得对重排后的字符串跑一遍KMP得到的next数组的最大值最小。如果有多种答案可以使得这个最大值最小，我们需要给出字典序最小的那一个。
大分类讨论中构造题。
首先我们考虑，如何才能让我们得到的next数组最小？
换句话说，我们如何才能让前缀和后缀尽量不匹配？
首先，如果全局只有一种字符，那么我们肯定是无能为力的。
否则我们可以把这个最大值限定在 $1$ 以内。
首先，如果有至少一种字符只出现了一次，我们可以将其中最小的那一个放到开头，剩下的部分排序之后接到后面即可，因为没有任何其他的子串可以和开头的这一个前缀匹配，next数组最大就是 $0$，同时我们做到了字典序最小。
剩下就是所有的字符都出现了两次及以上的情况了。
我们将这些字符按照从小到大的顺序分别重编号为 $a$、$b$、$c$ 等。
后面再说的时候就是按照新的编号了。
为了使得字典序最小，我们肯定是要把 $a$ 拿到串的开头的，然后让其他的后缀与 $a$ 匹配。
观察给的样例的第二个字符串，这给了我们一个关于做法的提示。
如果不是 $a$ 的字符数量足够，我们可以在开头再放一个 $a$，然后在后面交替填充一个非 $a$ 的字符和一个 $a$，直到 $a$ 用完，最后把剩下的部分都填充上非 $a$ 字符就可以了。
同时为了字典序最小，我们在填充非 $a$ 字符的时候需要先排序再填充。
这个方案阻止了连续的 $a$ 匹配上开头的两个 $a$，同时也阻止了后面的 $a$ 与一个非 $a$ 字符组合起来匹配上开头的两个字符，可以把最大值压缩到 $1$ 以内。
如果非 $a$ 字符数量不够呢？
我们这时候肯定不能再在前面放两个 $a$ 了。
我们可以想到把前面的 $aa$ 替换成 $ab$，以防止多余的 $a$ 与 $aa$ 匹配。
然后为了字典序最小，我们把剩下的 $a$ 都追加在后面。
我们这样做的同时还需要防止 $ab$ 被匹配。
一个简单的方法就是在一串 $a$ 后面放一个 $c$，阻止可能的 $ab$ 的出现。
如果找不到 $c$ 呢？
我们就换种思路，把字符串构造成 $abbb \dots bbaa \dots aa$ 的形式。
否则，我们就按照上面的思路，构造形如 $abaa \dots aacbb \dots$ 的字符串。
此时回顾我们的分类讨论，可以发现我们分的这几类已经可以覆盖所有的情况了。
代码如下：
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 300010;
int n;
char s[N];
int cnt[26], tot;
void solve()
{
scanf("%s", s + 1);
n = strlen(s + 1);
for(int i = 1; i <= n; i++)
cnt[s[i] - 'a']++;
for(int i = 0; i < 26; i++)
if(cnt[i])tot++;
int flag = -1;
for(int i = 0; i < 26; i++)
{
if(cnt[i] == 1)
{
flag = i;
break;
}
}
if(flag != -1)
{
string res;
res.push_back('a' + flag);
cnt[flag]--;
for(int i = 0; i < 26; i++)
while(cnt[i]--)
res.push_back('a' + i);
cout << res << endl;
}
else if(tot == 1)
{
printf("%s\n", s + 1);
}
else
{
string res;
vector<int>v;
for(int i = 0; i < 26; i++)
if(cnt[i])
v.push_back(i);
if(n - cnt[v[0]] >= cnt[v[0]] - 2)
{
res.push_back('a' + v[0]);
res.push_back('a' + v[0]);
cnt[v[0]] -= 2;
for(int i = v[1]; i < 26; i++)
{
while(cnt[i]--)
{
res.push_back('a' + i);
if(cnt[v[0]])
{
res.push_back('a' + v[0]);
cnt[v[0]]--;
}
}
}
}
else if(tot == 2)
{
res.push_back('a' + v[0]);
cnt[v[0]]--;
while(cnt[v[1]]--)
res.push_back('a' + v[1]);
while(cnt[v[0]]--)
res.push_back('a' + v[0]);
}
else
{
res.push_back('a' + v[0]);
cnt[v[0]]--;
res.push_back('a' + v[1]);
cnt[v[1]]--;
while(cnt[v[0]]--)
res.push_back('a' + v[0]);
res.push_back('a' + v[2]);
cnt[v[2]]--;
for(int i = v[1]; i < 26; i++)
while(cnt[i]--)
res.push_back('a' + i);
}
cout << res << endl;
}
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
tot = 0;
for(int i = 0; i < 26; i++)
cnt[i] = 0;
solve();
}
return 0;
}
|