21.6.21 test

\(NOI\) 模拟赛

字符串滚出 \(OI\)

看到题目名称，\(T1\) 串，\(T2\) 两个串，\(T3\) K个串，我 \(\cdots\)，血压已经上来了。

\(T1\) 写了 \(O(n^2)\) 的暴力15pts，正解是AC自动机上面做dp？？？我还是太菜了，dp没看懂。

\(T2\) 总觉得是在kmp上面修改，但被自己hack了，又加了个小数据跑暴力的部分（貌似数据没有在小数据上卡一般的kmp）40pts。正解是拿出了一个神奇的柿子加上FFT???

\(T3\) \(O(n^2)\) 暴力写挂了，正解是主席树加堆，有想过主席树但是被自己否定了。

update on 21.6.22

发现是BZOJ原题，就不开隐藏了，当题解写一下，放一下代码。

T1:串

这篇Blog写的比老师给的易懂（逃。所以写的是这篇里的思想和我的理解。对字符串不是很会，所以很多地方要感性理解一下。

题意：

给出一个字符串集，求有多少字符串可拆分为非空的两部分，每部分都是集合中某一个字符串的前缀。

题解：

考虑枚举所有不重复的前缀拼接，总前缀数为 \(m\)，如果把重复的都计算，那么答案为 \(m^2\)，于是考虑算出重复的字符串数。

如果一个字符串有重复，那么它一定可以有多种分解方式。如：

有 \((head,a)+(a,end)\) 和 \((haed,b)+(b,end)\) 两种分解。拼接的是前缀，所以我们可以判断 \((head,a),(a,end),(haed,b),(b,end),(a,b)\) 都是出现在字符串集中的前缀，其中 \((a,b)\) 既是 \((head,b)\) 的后缀，又是 \((a,end)\) 的前缀。由于 AC 自动机上的 fail 数组正是 AC 自动机上存在的最长后缀，方便处理题中的后缀，所以把所有的字符串都丢到 AC 自动机上面。考虑枚举 \((a,end)\)，那么它的 fail 就是它的最长后缀，此时即为最近的 b。可以预处理出以 \((a,b)\) 为后缀的字符串数，这就是以 \((a,b)\) 为中间串，\((b,end)\) 为后面串的贡献。枚举所有分割点 \(a,b,c,d,e,\cdots\) 都这样操作，除了最后一个 fail=0 的保留，刚好可以把所有重复的字符串去除。因为只要这个分割点 fail 不等于 0，就说明这种分割方式一定可以被后面 fail 的方式替代。

在实际操作中，我们只需要枚举 \((a,end)\) （也就是所有 fail 不为 0 的节点），它的 fail 为 \((b,end)\) ，那么沿着 a 的 fa 向上找 len[\((b,end)\)] 次后就表示\((a,b)\)，减去以它为后缀的前缀数量。用字典树大小的平方减去所有贡献后即为最终答案。

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n;

string c[10005];

int ch[300005][30],cn=0;

int fail[300005],cnt[300005],dis[300005],fa[300005];//cnt即以它为后缀的前缀数量

void insert(string s){

	int len=s.length(),p=0;

	for(int i=0;i<len;i++){

		int t=s[i]-'a'+1;

		if(!ch[p][t])

			ch[p][t]=++cn;

		dis[ch[p][t]]=dis[p]+1;

		fa[ch[p][t]]=p;

		p=ch[p][t];

	}

}

void getfail(){

	queue<int> q;

	int p=0;

	for(int i=1;i<=26;i++){

		if(ch[p][i]){

			q.push(ch[p][i]);

			fail[ch[p][i]]=0;

		}

	}

	while(!q.empty()){

		p=q.front();

		q.pop();

		for(int i=1;i<=26;i++){

			if(!ch[p][i])continue;

			int v=ch[p][i],j;

			for(j=fail[p];j&&!ch[j][i];j=fail[j]);

			fail[v]=ch[j][i];

			for(j=fail[v];j;j=fail[j])

				cnt[j]++;

			q.push(v);

		}

	}

}

int up(int now,int lenth){

	while(lenth--)now=fa[now];

	return now;

}

signed main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		cin>>c[i];

		insert(c[i]);

	}

	getfail();

	int ans=cn*cn;

	for(int i=1;i<=cn;i++)

		if(fail[i])ans-=cnt[up(i,dis[fail[i]])];

	cout<<ans;

	return 0;

}

T2：两个串

学了FFT再来看。

T3：K个串

题意：

求第K大的子串和。（以下和均为重复只算一次）

题解：

考虑每个点作为左端点对应的答案，将1为左端点时的答案：\(1\) 到 \(i\) 的和\((1\leq i\leq n)\)，建一棵线段树，可以维护最大值。对于2为左端点的答案，发现只需要在第一颗线段树的基础上，将1节点改为-inf，并在[2,next[1]-1]（next[i]表示i之后第一次出现a[i]的位置,没有出现则记为n+1）的节点全部减掉a[1]。后面的线段树都可以像这样构建，于是用可持久化线段树，有区间修改所以再写一个懒标记。

维护出每棵树后将他们的最大值插进堆里，取出其中最大值后，在对应线段树中删去最大值，也就是将对应节点改为-inf，再将此时的最大值插入堆中，循环k次就可以找到第K大值了。

时间复杂度大概是\(O((n+k)\log n)\)，神犇hrj对它的常数略有研究，%%%。

代码：

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n,k;

const int maxn=100005;

const int maxk=200005;

map<int,int> M;//仅用于求和时判重

int a[maxn],next[maxn];

int f[maxn];

priority_queue<pair<int,int> >Q;

//segment_tree----

#define ls(x) t[x].ls

#define rs(x) t[x].rs

#define mx(x) t[x].mx

#define tag(x) t[x].tag

int rt[maxn],tn=1;

struct node{

	int ls,rs;

	int mx,tag;

}t[maxn<<8];

int built(int l,int r,int p){//初始线段树

	if(l==r){mx(p)=f[l];return p;}

	int mid=(l+r)>>1;

	ls(p)=built(l,mid,++tn);

	rs(p)=built(mid+1,r,++tn);

	mx(p)=max(mx(ls(p)),mx(rs(p)));

	return p;

}

void cover(int &x,int d){//在x基础上新建节点

	int y=++tn;

	ls(y)=ls(x);

	rs(y)=rs(x);

	mx(y)=mx(x)+d;

	tag(y)=tag(x)+d;

	x=y;

}

void pushdown(int p){

	if(!tag(p))return ;

	cover(ls(p),tag(p));

	cover(rs(p),tag(p));

	tag(p)=0;

}

void make(int &now,int pre,int l,int r,int ml,int mr,int d){//now为新节点，pre为基础，l，r为范围，ml，mr为修改范围，d为加上的值，以这些数据新建线段树

	now=++tn;

	ls(now)=ls(pre);

	rs(now)=rs(pre);

	mx(now)=mx(pre);

	tag(now)=tag(pre);

	if(ml>mr)return ;

	if(l>=ml&&r<=mr){

		mx(now)+=d;

		tag(now)+=d;

		return ;

	}

	pushdown(now);

	int mid=(l+r)>>1;

	if(ml<=mid)make(ls(now),ls(now),l,mid,ml,mr,d);

	if(mr>mid)make(rs(now),rs(now),mid+1,r,ml,mr,d);

	mx(now)=max(mx(ls(now)),mx(rs(now)));

}

int getposition(int p,int l,int r){//找到这棵线段树中最大值的位置

	if(l==r)return l;

	int mid=(l+r)>>1;

	if(mx(ls(p))>mx(rs(p)))return getposition(ls(p),l,mid);

	else return getposition(rs(p),mid+1,r);

}

//----------------

signed main(){

	scanf("%lld%lld",&n,&k);

	for(int i=1;i<=n;i++){

		scanf("%lld",&a[i]);

		f[i]=f[i-1];

		if(M.count(a[i]))next[M[a[i]]]=i;

		else f[i]+=a[i];

		M[a[i]]=i;

	}

	rt[1]=1;

	built(1,n,1);

	Q.push(make_pair(mx(rt[1]),1));

	for(int i=2;i<=n;i++){

		make(rt[i],rt[i-1],1,n,i,next[i-1]?next[i-1]-1:n,-a[i-1]);

		make(rt[i],rt[i],1,n,i-1,i-1,0xb0b0b0b0b0b0b0b0LL);

		Q.push(make_pair(mx(rt[i]),i));

	}

	int maxa;int kth;

	for(int i=1;i<=k;i++){

		maxa=Q.top().first;

		kth=Q.top().second;

		Q.pop();

		int p=getposition(rt[kth],1,n);

		make(rt[kth],rt[kth],1,n,p,p,-100000000000000000LL);

		Q.push(make_pair(mx(rt[kth]),kth));

	}

	printf("%lld",maxa);

	return 0;

}

巴特西

21.6.21 test

\(NOI\) 模拟赛

T1:串

题意：

题解：

代码：

T2：两个串

T3：K个串

题意：

题解：

代码：

最新文章

热门文章