自动搬运

查看原文

来自洛谷，原作者为

	henryhu2006 **

搬运于2025-08-24 22:30:53，当前版本为作者最后更新于2021-09-11 12:37:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意概括

定义字符串一个位置的魔力值等于下标的约数个数，字符串的一个连续子串的魔力值为各个位置的魔力值之和。

定义字符串的一个连续子串是纯净的，当且仅当可以将这个子串分为等长的 $x$ 段，每段长度为 $len$，任意两段的相同位置的字符不同，且要求 $x\ge S$, $len\in [l,r]$。

求纯净的连续子串中最大魔力值。

数据范围：$n\le 5\times 10^5$，$r-l\le10$，字符集大小为 $52$。

题解

发现 $r-l\le10$，因此可以枚举段的长度。

考虑以 $l$ 为左端点的连续子串，对于任意 $r_1,r_2$，$l\le r_1<r_2$，当 $[l,r_1]$ 和 $[l,r_2]$ 均纯净时，$[l,r_1]$ 的代价必然小于 $[l,r_2]$，因为约数个数不可能是非正的。

对于每个位置，无论它处于哪个子串，导致不纯净的一定是在模 $len$ 意义下和它同模的坐标。

定义 $suf_i=\min \{j|j>i,j \equiv i\ (\text{mod} \ len) ,s_j=s_i\}$。

$suf$ 可用一个 $len\times 52$ 的二维数组来预处理，不多赘述。

接着枚举 $l$，则最大段数为 $x=\lfloor \frac{\min_{i=l}^{n}suf_i}{len} \rfloor$，如果 $x\ge S$，那么以 $[l,l+x\times len-1]$ 更新答案。

一开始预处理一下约数个数的前缀和，总时间复杂度 $\Theta((r-l)\times 52n)$，精细实现可以做到 $\Theta((r-l)\times n)$。

代码

细节：不能将 $len$ 和 $S$ 无脑相乘，会爆 int。

#include<bits/stdc++.h>
#define rint register int
using namespace std;
const int N=5e5+5;
int n,l,r,S,ans;
int num[N],vis[N],sum[N];
int now[N][52],suf[N];
char s[N];
int main(){
	cin>>n>>l>>r>>S;
	scanf("%s",s+1),num[1]=1;
	for(rint i=1;i<=n;++i)
		if(s[i]>='a') s[i]-='a'-26;
		else s[i]-='A'; // 压缩字符集
	for(rint i=2;i<=n;++i){
		if(!vis[i]) vis[i]=i;
		rint cnt=0,j=i;
		while(j%vis[i]==0) j/=vis[i],++cnt;
		num[i]=num[j]*(cnt+1);
		if(num[i]>2) continue;
		for(j=i*2;j<=n;j+=i) vis[j]=i; // 处理约数个数
	}
	for(rint i=1;i<=n;++i)
		sum[i]=sum[i-1]+num[i];
	for(rint len=l;len<=r;++len){
		if(1ll*len*S>n) break;
		memset(now,0,208*(len+1)); // memset 乘以 52 也跑得飞快
		memset(suf,0,sizeof(suf));
		for(rint j=n,mo=n%len,res=n+1;j>=1;--j,--mo){
			if(mo<0) mo=len-1;
			if(now[mo][s[j]]) suf[j]=now[mo][s[j]];
			else suf[j]=n+1;
			res=min(res,suf[j]);
			int zq=(res-j)/len;
			if(zq>=S) ans=max(ans,sum[j+zq*len-1]-sum[j-1]);
			now[mo][s[j]]=j;
		}
	}
	cout<<ans;
	return 0;
}