Description

现在有一个长度为 \(n\) 的字符串，将其划分为 \(k\) 段，使得这 \(k\) 段每一段的字典序最大子串中字典序最大的字符串字典序尽量小。求出这个字符串。

\(n\le 10^5,k\le 15\)

Solution1 \(\Theta(nk)\)

我们可以设 \(f_{i,j}\) 表示从右到左第 \(i\) 个字符已经划分成 \(j\) 段的最小答案。

我们可以得到转移式：

\[f_{i,j}=\min\{\max(\max\{[n\to k],i\le n\le k\},f_{k+1,j-1})\}
\]

不难看出，\(f_{k+1,j-1}\) 从右到左单调不减，\(\max\{[n\to k],i\le n\le k\}\) 从右到左单调不升，也就是说存在一个临界点使得临界点及其左边都是 \(f_{k+1,j-1}\) 转移，临界点右边都是 \(\max\{[n\to k],i\le n\le k\}\) 转移。可以想到，真正会产生贡献的只有临界点和临界点右边一个点，而且，临界点一定是随着 \(i\) 往左移一起往左移。

考虑如何同时维护 \(\max\{[n\to k],i\le n\le k\}\)，可以想到即使临界点右移，以前大的还是大，小的还是小，所以我们可以在每次 \(i\) 左移的取一个较大值即可。

所以我们就可以 \(\Theta(nk)\) 维护了。

Code1 by Reanap

#include <cstdio>

#include <cstring>

#include <algorithm>

#define pii pair <int , int>

#define mp make_pair

#define fs first

#define sc second

using namespace std;

const int MAXN = 1e5 + 5;

int sa[MAXN] , x[MAXN] , y[MAXN] , t[MAXN] , cnt[MAXN] , n , rk[MAXN];

char s[MAXN];

void make_suffix() {

	int m = 256;

	for (int i = 1; i <= n; ++i) cnt[x[i] = s[i]] ++;

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

	for (int i = 1; i <= n; ++i) sa[cnt[x[i]] --] = i;

	for (int k = 1; k <= n; k *= 2) {

		int tot = 0;

		for (int i = n - k + 1; i <= n; ++i) y[++tot] = i;

		for (int i = 1; i <= n; ++i) if(sa[i] > k) y[++tot] = sa[i] - k;

		for (int i = 1; i <= m; ++i) cnt[i] = 0;

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

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

		for (int i = n; i >= 1; --i) sa[cnt[x[y[i]]] --] = y[i];

		tot = 1;

		t[sa[1]] = 1;

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

			if(x[sa[i - 1]] != x[sa[i]] || x[sa[i - 1] + k] != x[sa[i] + k]) tot ++;

			t[sa[i]] = tot;

		}

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

		m = tot;

		if(tot >= n) break;

	}

}

int _min[MAXN][21] , height[MAXN] , Log[MAXN];

void get_height() {

	for (int i = 1; i <= n; ++i) rk[sa[i]] = i;

	int k = 1;

	Log[0] = -1;

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

		if(k) k --;

		int j = sa[rk[i] - 1];

		while(s[i + k] == s[j + k]) k ++;

		height[rk[i]] = k;

		Log[i] = Log[i >> 1] + 1;

	}

	for (int i = 1; i <= n; ++i) _min[i][0] = height[i];

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

		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {

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

		}

	}

}

int get_min(int l , int r) {

	if(l > r) swap(l , r);

	l ++;

	int t = Log[r - l + 1];

	return min(_min[l][t] , _min[r - (1 << t) + 1][t]);

}

int k;

pii dp[MAXN][20];

bool Comp(int l1 , int r1 , int l2 , int r2) {

	int len1 = r1 - l1 + 1 , len2 = r2 - l2 + 1;

	int LCP = get_min(rk[l1] , rk[l2]);

	if(l1 + LCP > r1 || l2 + LCP > r2) return len1 > len2;

	return rk[l1] > rk[l2];

}

int main() {

	scanf("%d" , &k);

	scanf("%s" , s + 1);

	n = strlen(s + 1);

	make_suffix();

	get_height();

	int cur = n;

	dp[n][1] = mp(n , n);

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

		if(rk[cur] < rk[i]) cur = i;

		dp[i][1] = mp(cur , n);

	}

	for (int j = 2; j <= k; ++j) {

		int r = n - j + 1 , cur = 0 , cur2 = 0;

		for (int i = n - j + 1; i >= 1; --i) {

			if(!cur || !Comp(cur , r , i , r)) {

				cur = i;

				if(!cur2) cur2 = cur;

				while(r > i && Comp(cur , r , dp[r + 1][j - 1].fs , dp[r + 1][j - 1].sc)) r -- , cur2 = cur;

				if(cur2 != cur && !Comp(cur2 , r + 1 , cur , r + 1)) cur2 = cur;

			}

			pii now = dp[r + 1][j - 1];

			if(!Comp(now.fs , now.sc , cur , r)) dp[i][j] = mp(cur , r);

			else if(Comp(cur2 , r + 1 , now.fs , now.sc) || !dp[r + 2][j - 1].fs) dp[i][j] = now;

			else dp[i][j] = mp(cur2 , r + 1);

		}

	}

	for (int i = dp[1][k].fs; i <= dp[1][k].sc; ++i) putchar(s[i]);

	return 0;

}

Solution2 \(\Theta(n\log n)\)

可以想到，我们可以二分最后答案的字典序，每次从右到左贪心地选，每次选不动了就划分。

时间复杂度显然是 \(\Theta(n\log n)\)。

Code2

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define ll long long

#define MAXN 100005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

char s[MAXN];

int n,m,K,num,len,nowl,nowr,x[MAXN],y[MAXN],c[MAXN],h[MAXN],sa[MAXN],rk[MAXN],st[MAXN][21];

int query (int l,int r){

	if (l == r) return n - sa[l] + 1;

	if (l > r) swap (l,r);++ l;

	int k = log2 (r - l + 1);

	return min (st[l][k],st[r - (1 << k) + 1][k]);

}

void getwhe (ll k){

	for (Int i = 1;i <= n;k -= n - sa[i] - h[i] + 1,++ i)

		if (n - sa[i] - h[i] + 1 >= k){

			nowl = sa[i],nowr = sa[i] + h[i] + k - 1,len = nowr - nowl + 1;

			return ;

		}

}

bool cmp (int l,int r){//判断[l,r]是否小于等于[nowl,nowr]

	int lcp = min (query (rk[l],rk[nowl]),min (len,r - l + 1));

	if (lcp == r - l + 1 && lcp <= len) return 1;

	if (lcp == len) return 0;

	return s[l + lcp] <= s[nowl + lcp];

}

bool check (){

	int cnt = 0;

	for (Int i = n;i >= 1;){

		int j = i + 1;

		while (j > 1 && cmp(j - 1,i)) -- j;

		if (j > i) return 0;

		cnt ++,i = j - 1;

	}

	return cnt <= K;

}

signed main(){

	read (K),scanf ("%s",s + 1),n = strlen (s + 1);

	m = 26;for (Int i = 1;i <= n;++ i) x[i] = s[i] - 'a' + 1,c[x[i]] ++;

	for (Int i = 1;i <= m;++ i) c[i] += c[i - 1];

	for (Int i = 1;i <= n;++ i) sa[c[x[i]] --] = i;

	for (Int k = 1;k <= n;k <<= 1){

		num = 0;for (Int i = n - k + 1;i <= n;++ i) y[++ num] = i;

		for (Int i = 1;i <= n;++ i) if (sa[i] > k) y[++ num] = sa[i] - k;

		for (Int i = 1;i <= m;++ i) c[i] = 0;for (Int i = 1;i <= n;++ i) c[x[i]] ++;for (Int i = 1;i <= m;++ i) c[i] += c[i - 1];

		for (Int i = n;i >= 1;-- i) sa[c[x[y[i]]] --] = y[i];swap (x,y),x[sa[1]] = num = 1;

		for (Int i = 2;i <= n;++ i) num += !(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]),x[sa[i]] = num;

		m = num;if (m == n) break;

	}

	for (Int i = 1;i <= n;++ i) rk[sa[i]] = i;

	for (Int i = 1,k = 0;i <= n;++ i){

		if (rk[i] == 1) k = 0;

		else{

			if (k) -- k;

			int j = sa[rk[i] - 1];

			while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++ k;

		}

		h[rk[i]] = k;

	}

	for (Int i = 1;i <= n;++ i) st[i][0] = h[i];

	for (Int j = 1;(1 << j) <= n;++ j) for (Int i = 1;i + (1 << j) - 1 <= n;++ i) st[i][j] = min (st[i][j - 1],st[i + (1 << j - 1)][j - 1]);

	ll l = 1,r = 0,ans;for (Int i = 1;i <= n;++ i) r += n - sa[i] - h[i] + 1;

	while (l <= r){

		ll mid = (l + r) >> 1;getwhe (mid);

		if (check ()) ans = mid,r = mid - 1;

		else l = mid + 1;

	}

	getwhe (ans);

	for (Int i = nowl;i <= nowr;++ i) putchar (s[i]);putchar ('\n');

	return 0;

}

巴特西

题解「BZOJ4310」跳蚤

Description

Solution1 \(\Theta(nk)\)

Code1 by Reanap

Solution2 \(\Theta(n\log n)\)

Code2

最新文章

热门文章