首页 > 代码库 > 【bzoj4310】跳蚤 后缀数组+二分
【bzoj4310】跳蚤 后缀数组+二分
题目描述
很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
现在他想找一个最优的分法让“魔力串”字典序最小。
输入
第一行一个整数 k。
接下来一个长度不超过 105 的字符串 S。
输出
输出一行，表示字典序最小的“魔力串”。
样例输入
13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba
样例输出
cbc
题解
后缀数组+二分
先使用后缀数组求出sa、rank和height，然后预处理出ST表，用倍增RMQ求LCP（再次偷改height的定义，height[i][j]表示sa[i]与sa[i-(1<<j)]的LCP）
然后我们二分答案串在S的所有子串中的排名。
这里用到了一个挺好理解的结论：一个串的本质不同的子串的个数为$\sum\limits_{i=1}^nn-sa[i]-height[i]$，就是某个字符开头的串的个数-重复出现过的串的个数。
有个这个结论可以做点什么？首先我们可以确定二分边界。
然后我们还可以根据子串的排名mid来求出对应的子串。
怎么求？我们从前往后枚举i，算出以sa[i]开头的本质不同的子串个数n-sa[i]-height[i]，如果mid大于这个数就将mid减去这个数，否则对应的子串就是sa[i]开头，sa[i]+height[i]-1+mid结尾的字符串。退推一下，应该不是很难想。
那么有了子串以后，我们在原串上从后往前贪心，每次找到一个字符，就比较当前串和二分的子串的字典序大小关系，如果当前的子串字典序较大，则在这个找到的字符后面分割一下。最后比较分割次数与k的关系即可。
需要注意的是二分的子串必须大于等于单个的最大字符，否则无论怎样分割都不可能分割出小于等于该串的字符串。
#include <cstdio>#include <cstring>#include <algorithm>#define N 100010using namespace std;typedef long long ll;int sa[N] , r[N] , ws[N] , wa[N] , wb[N] , rank[N] , height[N][20] , n , m = 27 , log[N] , k , L , R;char str[N];void getsa(){ int i , j , p , *x = wa , *y = wb; for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ; for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i; for(p = j = 1 ; p < n ; j <<= 1 , m = p) { for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i; for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j; for(i = 0 ; i < m ; i ++ ) ws[i] = 0; for(i = 0 ; i < n ; i ++ ) ws[x[y[i]]] ++ ; for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i]; for(swap(x , y) , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ ) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = p - 1; else x[sa[i]] = p ++ ; } } for(i = 1 ; i < n ; i ++ ) rank[sa[i]] = i; for(p = i = 0 ; i < n - 1 ; height[rank[i ++ ]][0] = p) for(p ? p -- : 0 , j = sa[rank[i] - 1] ; r[i + p] == r[j + p] ; p ++ );}void query(ll mid){ int i; for(i = 1 ; i <= n ; i ++ ) { if(n - sa[i] - height[i][0] < mid) mid -= n - sa[i] - height[i][0]; else { L = sa[i] , R = sa[i] + height[i][0] + mid - 1; return; } } L = 0 , R = n - 1;}int lcp(int x , int y){ if(x == y) return n; x = rank[x] , y = rank[y]; if(x > y) swap(x , y); int k = log[y - x]; return min(height[y][k] , height[x + (1 << k)][k]);}bool cmp(int l1 , int r1 , int l2 , int r2){ int t = lcp(l1 , l2) , len1 = r1 - l1 + 1 , len2 = r2 - l2 + 1; if(len1 <= len2 && len1 <= t) return 1; if(len1 > len2 && len2 <= t) return 0; if(len1 <= t && len2 <= t) return len1 <= len2; return r[l1 + t] <= r[l2 + t];}bool judge(){ int i , cnt = 1 , last = n - 1; for(i = n - 1 ; ~i ; i -- ) { if(r[i] > r[L]) return 0; if(!cmp(i , last , L , R)) cnt ++ , last = i; if(cnt > k) return 0; } return 1;}int main(){ int i , j; ll lp = 1 , rp = 0 , mid , ans; scanf("%d%s" , &k , str) , n = strlen(str); for(i = 0 ; i < n ; i ++ ) r[i] = str[i] - ‘a‘ + 1; n ++ , getsa() , n -- ; for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1; for(i = 1 ; (1 << i) <= n ; i ++ ) for(j = (1 << i) ; j <= n ; j ++ ) height[j][i] = min(height[j][i - 1] , height[j - (1 << (i - 1))][i - 1]); for(i = 1 ; i <= n ; i ++ ) rp += n - sa[i] - height[i][0]; while(lp <= rp) { mid = (lp + rp) >> 1 , query(mid); if(judge()) ans = mid , rp = mid - 1; else lp = mid + 1; } query(ans); for(i = L ; i <= R ; i ++ ) putchar(str[i]); return 0;}
【bzoj4310】跳蚤 后缀数组+二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。