出题人说是水题。。
题目链接
题意
将原字符串分割，使得每一部分都是一个Perfect串，一个perfect串满足它是它的各种循环串中字典序最小的那个。
思路
既然尽量分割的少一些，我们从最后一个字符遍历，r = len , l = 0,看看行不行， 不行就往前扫，直到可以，那么这时候我们就更新为l = index, r = len，同时输出满足的串，这样就将原序列化简为了一个更小的串了。更重要的是我们需要会写判断这个串是不是最小字典序。我们知道这个串的长度为len， 那么它所形成的的循环串一共有len个，因此我们的外层循环为len, 然后内层也为len,内层枚举的是这个字符串的每个字符，如果s[j] > s[(i + j)%len],就说明这个串不是最小的。
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
|
#include<bits/stdc++.h>
using namespace std;
bool panduan(string s)
{
int sz = s.size();
for(int i = 0; i < sz; ++i)
{
for(int j = 0; j < sz; ++j)
{
if(s[j] > s[(i + j) % sz])
return 0;
if(s[j] < s[(i + j) % sz])
break;
}
}
return 1;
}
int main()
{
int T;
cin >> T;
while(T--)
{
string s;
cin >> s;
int len = s.size();
int head = 0;
while(head < len)
{
for(int j = len; j >= 0; --j)
{
string t = s.substr(head, j - head);
if(panduan(t))
{
cout << t ;
head += j - head;
if(j < len)
cout <<" ";
break;
}
}
}
cout << '\n';
}
}
|