跳蚤 BZOJ 4310

跳蚤

【问题描述】

很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。

首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。

现在他想找一个最优的分法让“魔力串”字典序最小。

【输入格式】

第一行一个整数 k。接下来一个长度不超过 105 的字符串 S。

【输出格式】

输出一行，表示字典序最小的“魔力串”。

【样例输入】

13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba

【样例输出】

cbc

【数据范围】

S的长度<=100000

题解：

首先我们通过后缀数组可以知道原串本质不同的子串(长得不一样的子串)个数为∑(n + 1 - height[i] - sa[i]) （实际上就是后缀的长度（长度即为后缀的子串个数）减去重复的个数，实例看下图）

顺便结合RMQ求个lcp（最长公共前缀）

那么在这些子串上二分

当我们二分出排名时，找出对应的子串

举个例子：

ababa

排名后缀及对应子串：

a a 5 + 1 - 0 - 5 = 1

aba a ab aba 5 + 1 - 2 - 3 = 1

ababa a ab aba abab ababa 5 + 1 - 3 - 1 = 2

ba b ba 5 + 1 - 0 - 4 = 2

baba b ba bab baba 5 + 1 - 2 - 2 = 2

那么我们只要一个个后缀枚举过去，就能找出对应排名的字符串，这也能解释本质不同的子串个数

合法答案肯定是以串中最大字符开头的，将这个情况加入判断

然后贪心，当当前分出的段未大于枚举出的子串时，继续增添字符，不然将其作为分出的一段

判断段数与要求段数的大小，继续二分

#include<algorithm>
#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

using namespace std;

const int me = ;

int k;

int n;

int ansl;

int ansr;

int w[me];

int x[me];

int sa[me];

int he[me];

int rank[me];

int lg[me];

int f[][me];

char s[me];

inline void Sa()

{

    int m = ;

    for(int i = ; i <= n; ++i) ++w[x[i] = s[i] - 'a' + ];

    for(int i = ; i <= m; ++i) w[i] += w[i - ];

    for(int i = n; i >= ; --i) sa[w[x[i]]--] = i;

    for(int k = ; k <= n; k <<= )

    {

        int t = ;

        for(int i = n; i >= n - k + ; --i) rank[++t] = i;

        for(int i = ; i <= n; ++i)

            if(sa[i] > k)

                rank[++t] = sa[i] - k;

        for(int i = ; i <= m; ++i) w[i] = ;

        for(int i = ; i <= n; ++i) ++w[x[i]];

        for(int i = ; i <= m; ++i) w[i] += w[i - ];

        for(int i = n; i >= ; --i) sa[w[x[rank[i]]]--] = rank[i];

        m = ;

        for(int i = ; i <= n; ++i)

        {

            int u = sa[i], v = sa[i - ];

            if (x[u] != x[v] || x[u + k] != x[v + k]) rank[u] = ++m;

            else rank[u] = m;

        }

        if (n == m) break;

        for(int i = ; i <= n; ++i) swap(x[i], rank[i]);

    }

    int tot = ;

    for(int i = ; i <= n; ++i)

    {

        if(tot) --tot;

        int e = sa[rank[i] - ];

        while (s[e + tot] == s[i + tot]) ++tot;

        he[rank[i]] = tot;

    }

}

inline void Log()

{

    lg[] = ;

    for(int i = ; i <= n; ++i)

        lg[i] = (i == (i & (-i))) ? lg[i - ] +  : lg[i - ];

}

inline void Rmq()

{

    for(int i = ; i <= n; ++i) f[][i] = he[i];

    for(int i = ; i <= lg[n]; ++i)

        for(int j = ; j <= n; ++j)

            f[i][j] = min(f[i - ][j], f[i - ][j + ( << (i - ))]);

}

inline void Get(const long long &mi, int &u, int &v)

{

    long long e, pre;

    e = ;

    for(int i = ; i <= n; i ++)

    {

        pre = e;

          e += n +  - he[i] - sa[i];

        if (e >= mi)

        {

            u = sa[i];

            v = sa[i] + mi - pre + he[i] - ;

            return;

        }

    }

}

inline int Lcp(const int &x, const int &y)

{

    if (x == y) return n - x;

    int a = rank[x], b = rank[y];

    if (a > b) swap(a, b);

    int e = lg[b - a];

    return min(f[e][a + ], f[e][b - ( << e) + ]);

}

inline bool Com(const int &l1, const int &r1, const int &l2, const int &r2)

{

    int len1 = r1 - l1 + , len2 = r2 - l2 + , lcp = Lcp(l1, l2);

    if (len1 <= len2 && lcp >= len1) return true;

    if (len1 > len2 && lcp >= len2) return false;

    if (lcp >= len1 && lcp >= len2) return len1 <= len2;

    return s[l1 + lcp] <= s[l2 + lcp];

}

inline bool Check(const long long &mi, int &u, int &v)

{

    Get(mi, u, v);

    int num = , last = n;

    for(int i = n; i >= ; --i)

    {

        if (s[u] < s[i]) return false;

        if (!Com(i, last, u, v)) ++num, last = i;

          if (num >= k) return false;

    }

    return true;

}

inline void Two()

{

    long  long l, r, mi;

    int u, v;

    l = ;

    r = ;

    for(int i = ; i <= n; ++i) r += n +  - sa[i] - he[i];

    while(l <= r)

    {

        mi = (l + r) >> ;

        if(Check(mi, u, v))

        {

            ansl = u;

            ansr = v;

            r = mi - ;

        }

        else l = mi + ;

    }

}

int main()

{

    scanf("%d%s", &k, s+);

    n = strlen(s+);

    Sa();

    Log();

    Rmq();

    Two();

    for(int i = ansl; i <= ansr; ++i) printf("%c", s[i]);

}

巴特西

跳蚤 BZOJ 4310

最新文章

热门文章