CF1422E Minlexes

发表于 | 阅读数

可以删除相邻的元素，求每个后缀的字典序最小

需要耐心分析。

  • aabb，显然不删
  • bbaa，显然删
  • aaabb，显然不删
  • bbbaa，显然删

我们需要倒过来分析。

归类$s[i]==s[i+1]$

  • $s[i]>s[i+1]$以及$s[i]<s[i+1]$
  • $s[i]=s[i+1]$就是第一个不同的$ch$与$s[i]$的大小。注意$aaaaabbb$是不删，$bbbbbaa$是删。
  • 每次先继承上一个的第一个不同的$ch$与$s[i]$的大小，只有插入不等的时候再去判断，第一个不同的$ch$与$s[i]$的大小关系！，相等的时候始终继承之前的判断。
代码 
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


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

char s[N];

string ans[N], suf[N];
int le[N];
bool z[N];

void add(int x, char c)
{
    if (le[x] == 0)
        z[x] = false;
    else if (c < ans[x][0])
        z[x] = true;
    else if (c > ans[x][0])
        z[x] = false;
    if (suf[x].size() < 2)
        suf[x] = c + suf[x];
    ans[x] = c + ans[x];
    if (ans[x].size() > 10)
        ans[x].pop_back();
    le[x]++;
}
int main()
{
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    s[len + 1] = 0;
    for (int i = len; i >= 1; i--)
    {
        if (s[i + 1] == s[i])
        {
            ans[i] = ans[i + 2];
            suf[i] = suf[i + 2];
            le[i] = le[i + 2];
            z[i] = z[i + 2];
            if (ans[i].size() != 0 && ((ans[i][0] > s[i]) || (ans[i][0] == s[i] && z[i])))
            {

                add(i, s[i]);
                add(i, s[i]);
            }
        }
        else
        {
            suf[i] = suf[i + 1];
            ans[i] = ans[i + 1];
            le[i] = le[i + 1];
            z[i] = z[i + 1];
            add(i, s[i]);
        }
    }
    for (int i = 1; i <= len; i++)
    {

        cout << le[i] << " ";
        if (le[i] > 10)
        {
            cout << ans[i].substr(0, 5) << "..." << suf[i] << endl;
        }
        else
            cout << ans[i] << endl;
    }
}