CF1063F String Journey
题目大意
对于一个字符串数组 t 1 , t 2 , … , t k t_1,t_2,\dots,t_k t1?,t2?,…,tk?,如果对于每个 t i t_i ti?都是 t i ? 1 t_{i-1} ti?1?的真子串的话(即 t i t_i ti?是 t i ? 1 t_{i-1} ti?1?的子串且 t i ≠ t i ? 1 t_i\neq t_{i-1} ti?=ti?1?),则称这个字符串数组为有序数组。
给定字符串 S S S,要求构造有序串组 t 1 , t 2 , … , t k t_1,t_2,\dots,t_k t1?,t2?,…,tk?和任意字符串组 u 1 , u 2 , … , u k , u k + 1 u_1,u_2,\dots,u_k,u_{k+1} u1?,u2?,…,uk?,uk+1?,使得 S = u 1 + t 1 + ? + u k + t k + u k + 1 S=u_1+t_1+\cdots+u_k+t_k+u_{k+1} S=u1?+t1?+?+uk?+tk?+uk+1?(其中 + + +为字符串的拼接)。求所有构造方案中 k k k的最大值。
1 ≤ n ≤ 5 × 1 0 5 1\leq n\leq 5\times 10^5 1≤n≤5×105
题解
假设答案为 a n s ans ans,那么一定存在使得 t 1 , t 2 , … , t a n s t_1,t_2,\dots,t_{ans} t1?,t2?,…,tans?的长度为 a n s , a n s ? 1 , … , 1 ans,ans-1,\dots,1 ans,ans?1,…,1的构造方法。那么,因为 a n s + ( a n s ? 1 ) + ? + 1 ≤ n ans+(ans-1)+\cdots+1\leq n ans+(ans?1)+?+1≤n,得 a n s ≤ 2 n ans\leq \sqrt{2n} ans≤2n?。
从小到大枚举 a n s ans ans,设 f i f_i fi?表示当答案为 a n s ans ans时 t 1 t_1 t1?以 i i i开头是否可行。
记 s u m = ∑ i = 1 a n s i sum=\sum\limits_{i=1}^{ans}i sum=i=1∑ans?i,则可行的 i i i一定满足 i ≤ n ? s u m + 1 i\leq n-sum+1 i≤n?sum+1。我们从大到小枚举 i i i,并不断向哈希表中加入长度为 a n s ? 1 ans-1 ans?1且不与 [ i , i + a n s ? 1 ] [i,i+ans-1] [i,i+ans?1]重叠的串,对 f i f_i fi?转移的时候查询 [ i , i + a n s ? 2 ] [i,i+ans-2] [i,i+ans?2]或 [ i + 1 , i + a n s ? 1 ] [i+1,i+ans-1] [i+1,i+ans?1]是否在哈希表中出现过即可。
时间复杂度为 O ( n n ) O(n\sqrt n) O(nn?),空间复杂度为 O ( n n + P ) O(n\sqrt n+P) O(nn?+P),其中 P P P为哈希表的大小。
code
#include<bits/stdc++.h>
using namespace std;
const int base=37;
const long long P=19260817;
const int N=500000;
int n,sq,sum,ans;
long long g[N+5];
char s[N+5];
bitset<N+5>f[1005];
bitset<P+5>z;
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
g[i]=s[i]-'a'+1;
}
sq=sqrt(2*n)+1;sum=1;
f[1].set();
for(ans=2;ans<=sq;ans++){
sum+=ans;
for(int i=n-sum+1;i>=1;i--){
int j=i+ans;
if(f[ans-1][j]) z[g[j]]=1;
if(z[g[i]]||z[g[i+1]]) f[ans][i]=1;
}
if(!f[ans].count()){
--ans;break;
}
z.reset();
for(int i=1;i<=n-ans+1;i++){
g[i]=(g[i]*base%P+s[i+ans-1]-'a'+1)%P;
}
}
printf("%d",ans);
return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!