「洛谷P5108」仰望半月的夜空

发表于 | 分类于 | | 浏览量： 次

这是一个标算与瞎搞的故事…

传送门

洛谷P5108

题解

蒟蒻我人生的第一道1次过样例并AC的黑题。（然而写的并不是标算，这题貌似也没有达到黑题的难度）

这题的标算是后缀数组，然鹅蒟蒻我选择了瞎搞QwQ。

此题瞎搞的关键点在于找出题目中隐藏的单调性。（大雾）

首先，如果先考虑长度为$1$的子串，再考虑长度为$2$的，长度为$3$的…那么分别一共有$n$个、$n-1$个、$n-2$个。

并不好搞。

所以倒着来处理。（汗

长度为$n$的子串可以由$1$开头、长度为$n-2$的子串可以由2开头…每次可能的开头增加一个。

并且其中有一定的单调性：对于合法的开头$i,j$，如果当前$i$比$j$优，那么之后$j$永远不可能比$i$优。

所以构造一个单调栈$stk[]$，每次直接把新增的合法开头扔进栈顶，然后不断比较当前长度下$stk[top]$和$stk[top-1]$。如果此时$stk[top]$不比$stk[top-1]$优，直接弹掉它，维护栈的单调性。

维护操作结束后，栈顶就是当前最优解。

但是还有一个关键问题没有解决：如何快速比较两个较长字符串的大小？

既然原字符串是静态的，那么可以通过Hash+二分找出两个字符串的最长相同前缀，然后比较下一位即可。

瞎搞完成 ，总时间复杂度为$\Theta(n\log n)$。

然后…

ZS：嗯哼？后缀数组的题让你Hash+二分过了？看我拍一宿造数据卡掉你！！！

蒟蒻我：老师我写了双Hash！！！

ZS：嗯哼！喂？是中国人民解放军国防科技大学吗？麻烦你们把天河二号借我用一宿…

然后就没有然后了QwQ…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=300005;
int sig,n,S[maxn],top,stk[maxn],ans[maxn];char tep[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct Hash
{
	int Base,TT,Pow[maxn],Val[maxn];
	void init(int b,int m)
	{
		Base=b;TT=m;Pow[0]=1;
		for(int i=1;i<=n;i++) Pow[i]=(LL)Pow[i-1]*Base%TT;
		for(int i=1;i<=n;i++) Val[i]=((LL)Val[i-1]*Base+S[i])%TT;
	}
	inline int GetHashValue(int L,int R){return ((Val[R]-(LL)Val[L-1]*Pow[R-L+1])%TT+TT)%TT;}
}H1,H2;
inline bool IsStringSame(int L,int R,int S,int T){return H1.GetHashValue(L,R)==H1.GetHashValue(S,T)&&H2.GetHashValue(L,R)==H2.GetHashValue(S,T);}
inline bool StrCmp(int S1,int S2,int len)
{
	int L=0,R=len,mid;
	while(L<=R)
	{
		mid=L+R>>1;
		IsStringSame(S1,S1+mid-1,S2,S2+mid-1)?L=mid+1:R=mid-1;
	}
	if(R==len) return true;
	return S[S1+R]>=S[S2+R];
}
int main()
{
	sig=read();n=read();
	if(sig==26)
	{
		scanf("%s",tep+1);
		for(int i=1;i<=n;i++) S[i]=tep[i]-'a';
	}
	else
		for(int i=1;i<=n;i++)
			S[i]=read();
	H1.init(19630217,1000000007);H2.init(19260817,1000000009);
	for(int len=n;len;len--)
	{
		top++;stk[top]=n-len+1;
		while(top>1&&StrCmp(stk[top],stk[top-1],len)) top--;
		ans[len]=stk[top];
	}
	for(int i=1;i<=n;i++)
		printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}