XSYOJ 1133 兔子的字符串

@OceanEye7年前

08/9

21:10

XSYOJ 1133 兔子的字符串

OceanEye 撰写后缀数组字符串无回复

题面大意是：
给一个长度为N的串

\( N \leq 100000 \)
最多分割k次
问若干分割方法中
字典序最大的子串最小是什么

问了一下ZJT大佬……
原来是建出SA之后
先二分后缀
后二分长度

有一些细节要注意，除此之外就很simple了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000

#define For(i,a,b) for(int i=a;i<=b;++i)

#define  p(x) ('0'<=x&&x<='9')
char cc; int C;
template <class T>
void read( T &x )
{
	x=0; C=1; cc=getchar();
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}
#undef p
using namespace std;
#define N 100010
char s[N];
int a[N],set[N],n;
int SA[N],rk[N],h[N];
int buc[N],fir[N],sec[N],tmp[N];

void make_SA()
{
	copy(s+1,s+1+n,set+1);
	sort(set+1,set+1+n);
	For(i,1,n) a[i]=lower_bound(set+1,set+1+n,s[i])-set;
	fill(buc,buc+1+n,0);
	For(i,1,n) buc[a[i]]++;
	For(i,1,n) buc[i]+=buc[i-1];
	For(i,1,n) rk[i]=buc[a[i]-1]+1;
	bool unique;
	for(int p=1;p<=n;p<<=1)
	{
		For(i,1,n) fir[i]=rk[i],sec[i]=i+p>n?0:rk[i+p];
		fill(buc,buc+1+n,0);
		For(i,1,n) buc[sec[i]]++;
		For(i,1,n) buc[i]+=buc[i-1];
		For(i,1,n) tmp[n- --buc[sec[i]]]=i;
		fill(buc,buc+1+n,0);
		For(i,1,n) buc[fir[i]]++;
		For(i,1,n) buc[i]+=buc[i-1];
		for(int j=1,i;j<=n;++j)
		{
			i=tmp[j]; SA[buc[fir[i]]--]=i;
		}
		unique=true;
		for(int j=1,i,last=0;j<=n;++j)
		{
			i=SA[j];
			if(!last) rk[i]=1;
			else if(fir[i]==fir[last]&&sec[i]==sec[last]) rk[i]=rk[last],unique=false;
			else rk[i]=rk[last]+1;
			last=i;
		}
		if(unique) break;
	}
	for(int j=1,i,k=0;j<=n;j++)
	{
		if(rk[j]==1) k=0;
		else
		{
			k>0?--k:k;
			i=SA[rk[j]-1];
			while(i+k<=n&&j+k<=n&&a[j+k]==a[i+k])++k;
		}
		h[rk[j]]=k;
	}
}

int k;

int solve1()
{
	int L[N],Len;
	int l=1,r=n,mid,cnt,last;
	for(;r!=l;)
	{
		mid=(l+r)>>1; cnt=0; last=n;
		fill(L,L+1+n,INF);
		Len=n;
		For(i,mid+1,n)
		{
			Len=min(Len,h[i]);
			L[SA[i]]=Len;
		}
		if(Len==0) cnt=INF;
		else For(i,1,n)
		{
			last=min(last,i+L[i]-1);
			if(i==last) { cnt++; last=n; }
		}
		if(cnt>k) l=mid+1;
		else r=mid;
	}
	return l;
}

int solve2(int x)
{
	int L[N],Len;
	int l=h[x]+1,r=n-SA[x]+1,last,cnt,mid;
	for(;r!=l;)
	{
		mid=(l+r)>>1; cnt=0; last=n;
		fill(L,L+1+n,INF);
		Len=mid;
		For(i,x+1,n)
		{
			Len=min(Len,h[i]);
			L[SA[i]]=Len;
		}
		L[SA[x]]=mid;
		For(i,1,n)
		{
			last=min(last,i+L[i]-1);
			if(i==last) { cnt++; last=n; }
		}
		if(cnt>k) l=mid+1;
		else r=mid;
	}
	return l;
}

int main()
{
	read(k); scanf("%s",s+1);
	n=strlen(s+1);
	make_SA();
//	For(i,1,n) printf("%d ",SA[i]); puts("");
//	For(i,1,n) printf("%d ",rk[i]); puts("");
	int x=solve1(),ans=solve2(x);
//	printf("%d",x);
	For(i,0,ans-1) putchar(s[SA[x]+i]); puts("");
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

#define For(i,a,b) for(int i=a;i<=b;++i)

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; C=1; cc=getchar();

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

#undef p

using namespace std;

#define N 100010

char s[N];

int a[N],set[N],n;

int SA[N],rk[N],h[N];

int buc[N],fir[N],sec[N],tmp[N];

void make_SA()

{

copy(s+1,s+1+n,set+1);

sort(set+1,set+1+n);

For(i,1,n) a[i]=lower_bound(set+1,set+1+n,s[i])-set;

fill(buc,buc+1+n,0);

For(i,1,n) buc[a[i]]++;

For(i,1,n) buc[i]+=buc[i-1];

For(i,1,n) rk[i]=buc[a[i]-1]+1;

bool unique;

for(int p=1;p<=n;p<<=1)

{

For(i,1,n) fir[i]=rk[i],sec[i]=i+p>n?0:rk[i+p];

fill(buc,buc+1+n,0);

For(i,1,n) buc[sec[i]]++;

For(i,1,n) buc[i]+=buc[i-1];

For(i,1,n) tmp[n- --buc[sec[i]]]=i;

fill(buc,buc+1+n,0);

For(i,1,n) buc[fir[i]]++;

For(i,1,n) buc[i]+=buc[i-1];

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

{

i=tmp[j]; SA[buc[fir[i]]--]=i;

}

unique=true;

for(int j=1,i,last=0;j<=n;++j)

{

i=SA[j];

if(!last) rk[i]=1;

else if(fir[i]==fir[last]&&sec[i]==sec[last]) rk[i]=rk[last],unique=false;

else rk[i]=rk[last]+1;

last=i;

}

if(unique) break;

}

for(int j=1,i,k=0;j<=n;j++)

{

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

else

{

k>0?--k:k;

i=SA[rk[j]-1];

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

}

h[rk[j]]=k;

}

int k;

int solve1()

{

int L[N],Len;

int l=1,r=n,mid,cnt,last;

for(;r!=l;)

{

mid=(l+r)>>1; cnt=0; last=n;

fill(L,L+1+n,INF);

Len=n;

For(i,mid+1,n)

{

Len=min(Len,h[i]);

L[SA[i]]=Len;

}

if(Len==0) cnt=INF;

else For(i,1,n)

{

last=min(last,i+L[i]-1);

if(i==last) { cnt++; last=n; }

}

if(cnt>k) l=mid+1;

else r=mid;

}

return l;

}

int solve2(int x)

{

int L[N],Len;

int l=h[x]+1,r=n-SA[x]+1,last,cnt,mid;

for(;r!=l;)

{

mid=(l+r)>>1; cnt=0; last=n;

fill(L,L+1+n,INF);

Len=mid;

For(i,x+1,n)

{

Len=min(Len,h[i]);

L[SA[i]]=Len;

}

L[SA[x]]=mid;

For(i,1,n)

{

last=min(last,i+L[i]-1);

if(i==last) { cnt++; last=n; }

}

if(cnt>k) l=mid+1;

else r=mid;

}

return l;

}

int main()

{

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

n=strlen(s+1);

make_SA();

// For(i,1,n) printf("%d ",SA[i]); puts("");

// For(i,1,n) printf("%d ",rk[i]); puts("");

int x=solve1(),ans=solve2(x);

// printf("%d",x);

For(i,0,ans-1) putchar(s[SA[x]+i]); puts("");

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

XSYOJ 1133 兔子的字符串

XSYOJ 1133 兔子的字符串

撤销评论

近期文章

标签