[BZOJ4278] [ONTAK2015]Tasowanie 贪心+后缀数组

最近做题目好像有点东一榔头西一棒。好吧其实订正模拟题的时候需要用到什么感觉不太熟的就写一下吧。

显然直接贪心，比较两个点后面的串的字典序，小就选谁就可以了。

可以把两个串接起来，加一个\(inf\)分隔。然后用\(SA\)的\(rank\)数组就可以比较大小了。

也可以用哈希+二分比较。

#include<bits/stdc++.h>

using namespace std;

#define fec(i,x,y) (int i=head[x],y=g[i].to;i;i=g[i].ne,y=g[i].to)

#define dbg(...) fprintf(stderr,__VA_ARGS__)

#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)

#define isin(x,S) (((S)>>((x)-1))&1)

#define fi first

#define se second

#define pb push_back

template<typename I>inline void read(I&x){int f=0,c;while(!isdigit(c=getchar()))c=='-'?f=1:0;x=c&15;while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);f?x=-x:0;}

template<typename A,typename B>inline char SMAX(A&a,const B&b){return a<b?a=b,1:0;}

template<typename A,typename B>inline char SMIN(A&a,const B&b){return a>b?a=b,1:0;}

typedef long long ll;typedef unsigned long long ull;typedef pair<int,int>pii;

const int N=400000+7;

int n,m,a[N],b[N],ans[N];

int sa[N],rk[N],sec[N],tax[N];

inline void MakeSA(){

	int n=::n+::m+1,m=1001,*rnk=rk,*sc=sec;

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

	for(int i=1;i<=n;++i)tax[rnk[i]=a[i]]++;

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

	for(int i=n;i;--i)sa[tax[rnk[i]]--]=i;

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

		int p=0;

		for(int i=n-k+1;i<=n;++i)sc[++p]=i;

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

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

		for(int i=1;i<=n;++i)tax[rnk[sc[i]]]++;

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

		for(int i=n;i;--i)sa[tax[rnk[sc[i]]]--]=sc[i];

		swap(rnk,sc);p=rnk[sa[1]]=1;

		for(int i=2;i<=n;++i)rnk[sa[i]]=(sc[sa[i]]==sc[sa[i-1]]&&sc[sa[i]+k]==sc[sa[i-1]+k]?p:++p);

		if(p>=n)break;else m=p;

	}

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

}

int main(){

	#ifdef hzhkk

	freopen("hkk.in","r",stdin);

	#endif

	read(n);for(int i=1;i<=n;++i)read(a[i]);

	a[n+1]=1001;

	read(m);for(int i=1;i<=m;++i)read(b[i]),a[i+n+1]=b[i];

	MakeSA();

	for(int i=1,j=1,k=1;i<=n||j<=m;++k){

		if(j>m||(i<=n&&rk[i]<rk[j+n+1]))ans[k]=a[i++];

		else ans[k]=b[j++];

	}

	for(int i=1;i<=n+m;++i)printf("%d%c",ans[i]," \n"[i==n+m]);

}

巴特西

[BZOJ4278] [ONTAK2015]Tasowanie 贪心+后缀数组

最新文章

热门文章