首页 > 其他分享 >ABC240Ex Sequence of Substrings

ABC240Ex Sequence of Substrings

时间:2024-02-06 17:23:56浏览次数:41  
标签:子串 ABC240Ex Sequence int rep long Substrings include define

题意简述

有长度为 \(n\) 的 01 串,你现在要选出 \(k\) 个两两无交子串,使得将 \(k\) 个子串按照出现位置排序后,后者的字典序严格比前者大。最大化 \(k\)。

\(\bm{n\le 2\times10^4}\)。

分析

首先的首先观察数据范围可知此题应该是个线性根号对数的时间复杂度

首先有个显然的 \(O(n^2\log n)\) 的做法:

将 \(n^2\) 个子串排序,然后设 \(f_i\) 为考虑了排名前 \(i\) 的子串的最大答案,\(s_i\) 为排名为 \(i\) 的子串。转移显然有 \(f_i=\max_{j<i,s_j<s_i}f_j+1\),也显然可以通过树状数组维护下标维度支持单点修改、前缀查询最值的方式优化。

怎么进一步优化?

发现它是最优化问题而不是计数问题,考虑能否剪掉必定不优的一些决策。

通过合理的胡猜可得:存在最优解使得选出的子串长度 \(\le \sqrt{2n}\)。

证明可以考虑若存在选出的子串中相邻的两个子串长度差 \(\ge 2\) 的话,设较短串的长度为 \(len\),我们可以通过删掉较长串 \(len+2\) 之后的部分,这样也是合法的,因为出现不同的那一位必定在 \(len+1\) 之前。显然贪心的选更短的串是不劣的。

在最优方案中,即使再不济我们也能使选出来的串相邻之间长度 \(=1\),这样总长就是 \(\frac{k(k+1)}{2}\) 了,\(\frac{k(k+1)}{2}\le n\rightarrow k(k+1)\le 2n\rightarrow k\le \sqrt{2n}\),我们只需要取出长度 \(\le \sqrt{2n}\) 的子串排序即可。时间复杂度 \(O(n\sqrt n\log n)\)。

由于我做 SA 做傻了,排序我使用的是 SA+ST 表判断大小关系的,而不是较为简单的 Trie 树。

点击查看代码
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define FlushIn fread(Fread::ibuf,1,1<<21,stdin)
#define FlushOut fwrite(Fwrite::obuf,1,Fwrite::S-Fwrite::obuf,stdout)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define lowb lower_bound
#define uppb upper_bound
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=d)
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
typedef long long i64;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
bool smallingll(long long x,long long y){return x<y;}
namespace Fread {
	const int SIZE=1<<21;
	char ibuf[SIZE],*S,*T;
	inline char getc(){if(S==T){T=(S=ibuf)+fread(ibuf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite{
	const int SIZE=1<<21;
	char obuf[SIZE],*S=obuf,*T=obuf+SIZE;
	inline void flush(){fwrite(obuf,1,S-obuf,stdout);S=obuf;}
	inline void putc(char c){*S++=c;if(S==T)flush();}
	struct NTR{~NTR(){flush();}}ztr;
}
/*#ifdef ONLINE_JUDGE
#define getchar Fread::getc
#define putchar Fwrite::putc
#endif*/
inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=25005,maxm=2e7+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,B;
int len; 
char s[maxn];
struct str{
	int l,r;
}q[maxm];
int sa[maxn],rk[maxn],hi[maxn];
int id[maxn],prk[maxn<<1],nrk[maxn],cnt[maxn];
int g[maxn][20];
bool qwq(int x,int y,int z){
	return prk[x]==prk[y]&&prk[x+z]==prk[y+z];
}
void SA(){
	int m=127;
	rep(i,1,n)cnt[rk[i]=s[i]]++;
	rep(i,2,m)cnt[i]+=cnt[i-1];
	per(i,n,1)sa[cnt[rk[i]]--]=i;
	for(int j=1,p;j<n;j<<=1,m=p){
		p=0;rep(i,n-j+1,n)id[++p]=i;
		rep(i,1,n)if(sa[i]>j)id[++p]=sa[i]-j;
		rep(i,1,m)cnt[i]=0;
		rep(i,1,n)cnt[nrk[i]=rk[id[i]]]++;
		rep(i,2,m)cnt[i]+=cnt[i-1];
		per(i,n,1)sa[cnt[nrk[i]]--]=id[i];
		rep(i,1,n)prk[i]=rk[i];
		p=0;rep(i,1,n)rk[sa[i]]=qwq(sa[i],sa[i-1],j)?p:++p;
		if(n==p)break;
	}
	int w=0;
	rep(i,1,n){
		if(w)w--;
		while(s[i+w]==s[sa[rk[i]-1]+w])w++;
		hi[rk[i]]=w;
	}
	rep(i,1,n)g[i][0]=hi[i];
	int M=log2(n);
	rep(j,1,M)rep(i,1,n-(1<<j)+1)g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
	if(l>r)return inf;
	int p=log2(r-l+1);
	return min(g[l][p],g[r-(1<<p)+1][p]);
}
bool cmp(str x,str y){
	int rx=rk[x.l],ry=rk[y.l];
	if(rx>ry)swap(rx,ry);
	int lcp=query(rx+1,ry);
	if(lcp>=min(x.r-x.l+1,y.r-y.l+1))return x.r-x.l<y.r-y.l;
	return s[x.l+lcp]<s[y.l+lcp];
}
bool awa(str x,str y){
	if(x.r-x.l!=y.r-y.l)return 0;
	int rx=rk[x.l],ry=rk[y.l];
	if(rx>ry)swap(rx,ry);
	int lcp=query(rx+1,ry);
	return lcp>=x.r-x.l+1;
}
int c[maxn];
int f[maxm];
void add(int x,int y){while(x<=n)c[x]=max(c[x],y),x+=lowbit(x);}
int qry(int x){int res=0;while(x)res=max(res,c[x]),x-=lowbit(x);return res;}
void solve_the_problem(){
	n=rd(),B=sqrt(2*n);scanf("%s",s+1);SA();
	rep(i,1,n)rep(j,i,min(i+B,n))q[++len]=(str){i,j};
	sort(q+1,q+len+1,cmp);
//	rep(i,1,len)write(q[i].l,32),write(q[i].r,10);
	int lst=1,ans=0;
	rep(i,1,len){
		if(!awa(q[i],q[i-1])){
			rep(j,lst,i-1)add(q[j].r,f[j]);
			lst=i;
		}
		f[i]=qry(q[i].l-1)+1,ans=max(ans,f[i]);
//		write(lst,32);
	}
	write(ans);
}
bool Med;
signed main(){
//	freopen(".in","r",stdin);freopen(".out","w",stdout);
//	fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
	int _=1;while(_--)solve_the_problem();
}
/*

*/

标签:子串,ABC240Ex,Sequence,int,rep,long,Substrings,include,define
From: https://www.cnblogs.com/dcytrl/p/18010059

相关文章

  • CodeCraft-22 and Codeforces Round 795 (Div. 2)C. Sum of Substrings(分类讨论、贪
    感觉分类讨论的能有点弱。遇到复杂一点的分类讨论的题目,代码就写的巨长。首先观察到处在中间位置的1对答案的贡献是11,具体在中间哪个位置是没有关系的。只有两端的两个位置是比较特殊的\(1位置处的1对答案的贡献是10\)\(2位置处的1对答案的贡献是1\)所有我们考虑将最左端第一......
  • [AGC024E] Sequence Growing Hard 题解
    题目链接点击打开链接题目解法考虑如何添加数,使得\(\{a_1,...,a_i\}\)到\(\{a_1,...,x,a_j,...,a_i\}\)是合法的需要手玩一会才能发现合法条件很简单:\(x>a_j\)考虑对这个进行计数一个一个添元素是难维护的,现在假设有最终的序列,每个位置有\((v,dfn)\),分别为值和添加的次......
  • CF1924D Balanced Subsequences
    题意简述有\(n\)个左括号和\(m\)个右括号,求最长合法括号子序列长度为\(2k\)的括号序列的数量,对\(10^9+7\)取模。多组数据。\(T\le3\times10^3,n,m,k\le2\times10^3\)分析可能需要的前置知识:如何求一个字符串的最长合法括号子序列?维护一个括号栈,若遇到左括号则直接......
  • CodeForces 1924D Balanced Subsequences
    洛谷传送门CF传送门发现去掉匹配的\(2k\)个括号后,剩下的串一定形如\())\ldots)((\ldots(\),其中右括号数量为\(a=m-k\),左括号数量为\(b=n-k\)。考虑把剩下的串像\())\ldots)\mid((\ldots(\)一样分成两半。枚举左半边加入了\(\frac{i}{2}\)对匹配,则......
  • [ARC170C] Prefix Mex Sequence
    给定\(n,m,S_1\simS_n\),当\(S_i=0\)时\(A_i\neq\mathrm{mex}(A_1\simA_{i-1})\),反之\(A_i=\mathrm{mex}(A_1\simA_{i-1})\),求值域为\([0,m]\)的\(A\)的数量\(\bmod\998244353\)。\(1\len\le5000,0\lem\le10^9\)。看到题目就会想到......
  • ARC170C Prefix Mex Sequence
    题意简述有长度为\(n\)的\(s_i=0/1\),求满足下列条件的长度为\(n\)的序列\(a\)的个数,对\(998244353\)取模:\(\foralli,0\lea_i\lem\)当\(s_i=0\)时,\(a_i\not=\operatorname{mex}(a_1,a_2,\cdots,a_{i-1})\)当\(s_i=1\)时,\(a_i=\operatorname{mex}(a_1,a_2,\......
  • B - Arithmetic Progression Subsequence
    B-ArithmeticProgressionSubsequenceProblemStatementYouaregivenasequence$A$oflength$N$consistingofintegersbetween$1$and$\textbf{10}$,inclusive.Apairofintegers$(l,r)$satisfying$1\leql\leqr\leqN$iscalledagoodpairif......
  • RK3566 Boot Sequence
     IntroductionThispagedescribesthebootsequenceofrockchiplinuxGeneralBootSequence(Linuxsystem)BootsequenceSocpowersupandinitializes.BootRomcoderunsinSRAM,loadsandverifiesbootloader'sbootstrapcodefromstoragedevice.......
  • Beautiful Bracket Sequence (easy version)
    传送门。题意一个含未知字符的括号序列,一个括号序列的权值是这个括号序列的最大深度。问所有可能的括号序列的权值和为多少。分析我们寻找一下深度的快速计算方式。可以发现两个巧妙的性质。以某一个位置分割,左边的左括号数量和右边的右括号数量的较小值就是这个位置的最大......
  • 解决latex在使用lstlisting环境时的Undefined control sequence.错误
    错误描述,如题,Undefinedcontrolsequence.\begin{lstlisting},查了不少的资料,起始就是一句话,缺了宏包的导入。先看代码:\documentclass[11pt,a4paper]{ctexart}\usepackage{listings}%插入代码要引入的宏包\author{gsc}\title{sample}\lstset{columns=fixed,......