牛客竞赛第七场 A String

发表于 | 分类于 | 阅读次数：

出题人说是水题。。

题目链接

题意

将原字符串分割，使得每一部分都是一个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';
    }
}